Linked List in Details

What is linked list ?

Linked List is a data structure that contains group of nodes connected in a sequential manner with a pointer. Linked list and arrays are similar since they both store collections of data in a sequential manner.

Original object
Linked list can behave as a dynamic array. The size of an array is fixed, so to use more than its capacity, one may have to resize the array or create large enough array to fit in all elements which could result in wasting unused memory space. An array allocates memory for all its elements lumped together as one block of memory. In contrast, a linked list allocates space for each element separately in its own block of memory called a "linked list element" or "node". The list gets is overall structure by using pointers to connect all its nodes together like the links in a chain.

Each node contains two fields: a "data" field to store whatever element type the list holds for its client, and a "next" field which is a pointer used to link one node to the next node.

Advantages of Linked list over array:

  1. Dynamic sizing of linked list is possible. Create new element in linked list as needed
  2. Same linked list can contain elements of different type.
  3. Insertion or deleteion of an element is efficient. Its about moving the pointers.

Disadvantages of linked list:

  1. Finding an element takes O(n) time
  2. Consume more memory than array for storing same number of elements

In linkedlist, each object coud lbe referred as a node. For simplicity sake, we could consider a Linkedlist storing integer object.

class Node {
	int data;	 // store the integer value
	Node next;  // store the pointer to the next element
}

Most commonly used Linkedlists are Singly LinkedList and Doubly LinkedList. Above code example represents a Single Linkedlist. Doubly Linkedlist - Singly linkedlist has a forward pointer and moves in one direction. Doubly linkedlist has an extra pointer generally referred as previous and the list could move in either direction.

class Node {
	int data;	 // store the integer value
	Node next;  // store the pointer to the next element
	Node prev; //store the previous pointer to the next element 
}
When to use singly vs doubly linked list
  1. Doubly linked has 2 pointers , which means it easier to move in forward and backward direction. This can make things simpler for scenarios where updating or deleting is frequent
  2. Add 2 pointers to doubly linked list means more memory to hold an extra pointer compare to singly linked list
  3. Insetion in doubly linked list gets tricker as compare to singly linked list
  4. If data structure is immutable, singly-linked lists offer another really useful property: they allow structure-sharing. A singly-linked list can happily be the tail of multiple heads, something which is impossible for a doubly-linked list. For this reason, singly-linked lists have traditionally been the simple datastructure of choice for functional languages.
  5. Use doubly linked list if a data structure is needed to work as a Queue and a Stack at the same time
  6. Use doubly linked list if LRU cache is needed

Operations on linkedlist

  1. Create a linkedlist.
  2. Add an element to list.
  3. Find an element.
  4. Remove an element.
  5. Print elements of linkedlist.

Here is the code Operations on Linkedlist