Linked list

  • Linear data structure representing ordered sequence of elements.
  • Elements in it are not stored in contiguous location as arrays, rather linked through the pointers.
  • Advantage over array
    • Dynamic size. Not fixed one as array.
    • Ease of insertion or deletion which are expensive in array.
  • Drawbacks over array
    • Random access not allowed.
    • Extra memory space for maintaining pointers between elements.
    • Memory are not continuous and  hence might not leverage CPU cache.
  • Linked list preferred over arraylist when size of the list changes drastically with situation and lots of write operation involved.
  • Single linked list
    • Each node of it has pointer to the next node and hence allow only forward access.
  • Doubly linked list
    • Each node of it has pointer to the next and previous nodes and hence allow forward and backward access.
    • Java implementation LinkedList is doubly linked list.
    • JDK collections also include LinkedHashSet and LinkedHashMap – both maintain insertion order.
    • Links in doubly linked list can be memory optimized using XOR based list.
  • A variant of the list called Skip list which provides less than O(n) for search operations. Read more.
  • Another variant is called self organizing list which optimizes the search by placing the frequently visited nodes in the beginning of the list and hence reducing the time complexity.
  • Problems on singly linked list, leverage the following strategy
    • Recursion – Can be subsitute for the stack.
    • Fast and slow pointers.
    • Iteration – Previous, current, next pointers.
    • Making changes in the node.
    • Using hash.
    • In case of 2 linked lists, take traversal head of both.
    • For reversing, you could use recursion or traversal. In case of traversal, assign current.next to previous.
    • In singly linked list, if the value of the current node depends on the rest of the nodes, reverse the list first, operate on it and then reverse it back.
    • Quick sort is possible with singly linked list.
  • Doubly linked list.
    • Reversing requires just swapping of previous and next pointers.

Problems on linked list

 

Leave a Reply

Your email address will not be published. Required fields are marked *