Cheatography

### Definition

 Definition It's a linear data structure which stores data sequen­tially, but not in contiguous memory locations

### Types

 Single Linked List Each node has a pointer to the next node. Last node is always points to null Double Linked List Each node has 2 references :1 to previous node, the other to next node. Prev element of head is always null, next reference of tail node always points to null Circular LinkedList It could be a single or a double linked­list. The difference is that instead of having the last node point to null, it points to head node. It is useful in implem­enting round-­robin algorithms

### append( int data)

 ``````Node newNode = new Node(data); while(head.next != null){ head=head.next; } head.next = newNode;``````

### prepend( data )

 ``````Node newHead = new Node(data); newHead.next = head; head = newHead; return head;``````

 ``````if(head == null) return; if(head.next = null)    head = null; else{   head.data = head.next.data;   head.next = head.next.next; }``````

### Note

1. Always check for null pointers when traversing linked­Lists
2. When traversing in place, consider using 2 points - slow, fast :
1. to compare each element with another
2. to go to the middle element when size of list is unknown
3. to find kth element from last when size of list if unknown
4. to determine if linkedlist has a cycle, or to find the cycle element

### delete­Tail( )

 ``````while(node.next.next!=null){ node = node.next; } node.next = null;``````

### delete­Node( data )

 ``````while(head.next !=null){   if(head.next.data == data){      head.next = head.next.next;      break;   }  head = head.next; }``````