Linked List - Dynamic Data Structure

---

Introduction - 

         Linked list is a dynamic data structure i.e. data structure that grows and shrinks at run time. Linked List is a series of connected nodes where each node contains atleast 2 things -

1. A piece of data
2. Pointer (link) to the next node in the list

Figure - Linked List

Remark - Self - Referential structures (also referred as linked list) is a structure that contains a pointer to the structure of same type.

  Linked list are among the simplest and the most common data structures (and can be used to implement several other data structures such as stacks, queue which will discussed later on). Linked list allows insertion and removals anywhere in the list as compared to other data structures such as stacks which allows insertion and deletion only at the top of stack, queue where insertion take place at the back and removal from the front. Linked list uses a pointer variable header which stores the address of first node of the list and the last node pointer contains NULL value to show that there are no more elements in this list as shown in Figure above.

Benefits of Linked List (compared to an array) - 

1. Linked do not need contiguous blocks of memory and Linked list storage need to be preallocated.
2. Inserting or removing an element into a linked list requires one data update whereas in array it requires more updates. For Example -  Consider there are 10 elements in an array and currently 9 elements are present in the array and an element need to be inserted at 3 location. So, all the elements from array subscript 2 need to copied to the next location requiring 7 updates + one insertion at 3 location.

Note - Array Index starts from 0 not 1. So, 10 elements means that array subscript would be from 0 - 9.

---

Types of Linked List -

Singly Linked List - Begins with a pointer to the first node (header) and ends with a NULL in the pointer field of the last node. One of the limitation that singly list imposes over other linked list is that it can be traversed only in one direction.

Figure  - Singly Linked List

Circular Singly List - In circular singly linked list the pointer in the last node stores the address of the first node but still can be traversed only in one direction. However, in cases the linked list is empty we need a pointer to show that list is empty by setting its value to NULL.

Figure - Circular Singly Linked List

Doubly Linked List - Instead of using a single pointer doubly linked list make use of two start pointers, one to point the first element of the list, other to the last element. Each node has two pointers (forward pointer and backward pointer). The major benefit of this type of list over others is that it can traversed in both the directions forwards and backwards.

Figure - Doubly Linked List

Circular Doubly Linked List - In Circular doubly linked list the forward pointer of the last node points to the first node and the backward pointer of the first node points to the last node.

Figure - Circular Doubly Linked List

---