Linked Lists

linked lists data structure by mayukh datta

Linked List is a linear data structure like stack and array. Unlike arrays, linked list elements are not stored at contiguous locations in memory. Each element (say a node) in a linked list has two parts - one is the data part that stores the input data and the other is the next part which is basically a pointer variable that stores the memory address of the next element. All the elements in a linked list are linked using pointers. An individual without the working knowledge of pointers and memory allocation in C must not begin learning linked lists.

Why Linked Lists?

In array, elements are stored in contiguous blocks of memory. This spacial locality in memory greatly benefits from modern CPU caching methods. Array provides faster, random access {constant access time, O(1)} to any of its elements using sub-scripted variable (a[ i ]).
//total 5 array elements
int array[5]={9,6,1,3,2};
//access and print each element
  printf("%d ", a[i]);
It is simple and easy to use. As array size is static, when it comes to dynamic allocation, array fails to make you comfortable. Insertion and deletion of elements in an array is expensive, it needs copying and shifting of existing elements every time.

Then, there are linked lists. They are of dynamic size and hence don't waste memory but takes some extra memory for pointers. Insertion and deletion can be carried out easily. They can grow in size until system memory exhausts. But, they don't allow random access to elements rather allows sequential access {linear access time, O(n)}. Sequential access is like - a roll of paper where all prior material must be unrolled in order to get to the sheet you want.

As both of them are used to store collections of data, we generally prefer using Linked Lists when we need ease in inserting and deleting elements, and when run time efficiency is much more important then using arrays is obvious.

Linked list has mainly two operations - insertion (inserting data) and deletion (deleting data). The first node is called head and the last node is called tail.

Commonly, linked lists are of three types:-

  1. Singly Linked List - Unidirectional, each node has a pointer to its successor, tail points to NULL.
  2. Doubly Linked List - Bidirectional, each node has pointer both to predecessor and successor, tail points to NULL.
  3. Circular Linked List - Tail points to head. It inherits properties from the other two linked lists to form singly circular and doubly circular linked list.

Code for Singly Linked List:-

Code for Doubly Linked List:-

Circular Linked List, Unrolled Linked List and Skip List will be discussed in a further blog post.

Reference (video):-