Linked List

Linked list is a data structure for storing a collection of data but in a different way compared to array.

We can visualize an array as a box partitioned to store data. It's a continuous block of data , But linked list is many boxes that are not continuous but connected to each other.

boxWithThreePartition.png

[continuous block of data]

Not_Continous_Link.png [not continuous but connected to each other]

Consider memory as a long tape with compartments, where each compartment is represented by an unique address and can hold a byte of data.

We cannot extend the size of the array dynamically and the solution to the problem is instead of storing as a continuous block we can store one unit of data at time across the tape and link the block together.

So a linked list is a sequence of elements and each element in the linked list points to the adjacent elements in the sequence. Each element of the Linked List is called a Node. A Linked List is formed by connecting multiple nodes.

A node consist of two parts

  • Data(The actual raw information we are trying to store. It can be of any datatype.)
  • Address to the next data in the sequence.(The memory address of the next node in the sequence. Only by reading this address can we traverse to the next node in the sequence.)

LinkedList.PNG

By Vectorization: Lasindi - Own work based on: Singly linked list.png by Derrick Coetzee, Public Domain, commons.wikimedia.org/w/index.php?curid=224..

Advantage of Linked list over Array.

  • Once the size of the array is defined we cannot modify. But in Linked list we can dynamically control their size by link and unlink the node even at runtime.

  • It is possible to store linked lists in noncontiguous fashion, whereas arrays require a continuous block of memory. A 5 mb of free space in a system cannot be used to store an array size of the same 5 mb if the available free space is not continuous . Since Linked list is noncontiguous we can use system space to its full potential.

  • To ensure that array data is stored contiguously in memory, we must shift right or shift left the entire remaining values in the array to insert/delete a value. This operation is costly. Shifting the entire value in an array is O(N). To insert a new element in the link list no element shift is required. So Inserting and deleting is much faster in the linked list.

Types of Linked List

Singly linked list

Singly linked list is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).
We maintain a special pointer called HEAD, which stores the address of the first node of the linked list. Since the last node cannot have the next element, we assign NULL to its next element.

SinglyLinkedList.png

class Node{
  int data;
  Node next;
}

Doubly linked list

A Doubly linked list is bidirectional, that is each node contains a pointer to both the previous and next nodes.

  • Doubly Linked List Element contains pointers to the next and previous elements, as well as the data field.
  • For the First Element, the Previous pointer will be Null, marking the start of the List.
  • The Last Element will have its Next pointer as Null, to mark the end of the List.

Doubly-linked-list.png By Lasindi - Own work, Public Domain, commons.wikimedia.org/w/index.php?curid=224..

The following is the code representation

class Node {
   Node previous;  // Pointer to the Previous Element
   int value;      // Value stored in this element.
   Node next;      // Pointer to the Next Element
}

Circular linked list

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.

CircularLinkedList.png

class Node{
    int value;
    Node next; // Points to the next node.
}