Cheatography
https://cheatography.com
Definition
Definition |
It's a linear data structure which stores data sequentially, 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 linkedlist. The difference is that instead of having the last node point to null, it points to head node. It is useful in implementing 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;
|
deleteHead
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 linkedLists
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
|
|
deleteTail( )
while(node.next.next!=null){
node = node.next;
}
node.next = null;
|
deleteNode( data )
while(head.next !=null){
if(head.next.data == data){
head.next = head.next.next;
break;
}
head = head.next;
}
|
|
Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets
More Cheat Sheets by evanescesn09