Show Menu
Cheatography

LinkedList ADT Cheat Sheet by

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;

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 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;
}
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Eclipse Cheat Sheet
          Selenium WebDriver Cheat Sheet Cheat Sheet

          More Cheat Sheets by evanescesn09