CS Code

Coding, quiz & more

Linked List Data Structure

In this tutorial, we are going to learn the Linked List Data Structure, Structure of Node, Applications of Linked List and Linked List Over Array.

Linked List is a linear data structure in which nodes are connected to each other. Each node stores the address of next node.

Linked List Representation
  • A node is divided into at least two parts:
    • Data Part
    • Next Part

Data part: Data part is used to store actual data. For example, name of the student, roll number, class and any data related to that student.

Next part: Next part is nothing but a pointer which stores address of the next node.

Starting node is also called as Head . The next part of the end node is set to NULL.

Why Linked List over Array?

Instagram

Of-course we choose Linked List to perform insertion, deletion, updation and searching on 1 Million records.

Why?

  • Insertion of new element in the array is too expensive. If we have to insert an element at position 1 then we have to shift all the elements from position 1 to the end by 1.
    • int arr[100000] = {1, 2, 3, 4, ……., 99999};
    • suppose we have to insert a new number(0) at index 0 then we have to shift all the numbers by index 1 to right.
    • {0, 1, 2, 3, 4, …..} (0 takes position of 1, 1 takes position of 2 and so on).
  • Same problem while deleting the elements from array.

Advantages of Linked List over Array:

  • Dynamic size.
  • Non-contiguous memory allocation
  • Ease of insertion/deletion

Drawbacks of Linked List:

  • Can not access elements randomly in the Linked List. In array elements can be accessed randomly using array index(ex. arr[4]). This is not possible in linked list.
  • Required extra space to store next pointer for all nodes.
  • Linked List is not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

Representation Of Linked List

In C, node can be represented using Structure. 

struct Node { 
    int data; 
    struct Node* next; 
}; 
class Node { 
public: 
    int data; 
    Node* next; 
}; 
class LinkedList { 
    Node head; // head of the list 
  
    /* Linked list Node*/
    class Node { 
        int data; 
        Node next; 
  
        // Constructor to create a new node 
        // Next is by default initialized 
        // as null 
        Node(int d) { data = d; } 
    } 
}
class Node: 
   
    # Function to initialize the node object 
    def __init__(self, data): 
        self.data = data  # Assign data 
        self.next = None  # Initialize  
                          # next as null 
   
# Linked List class 
class LinkedList: 
     
    # Function to initialize the Linked  
    # List object 
    def __init__(self):  
        self.head = None

Linked List Applications

  • Hash Tables
  • Implementation of stacks and queues.
  • To represent a polynomial.
  •  Dynamic memory allocation.
  • LRU/MRU (Least Recently Used/Most Recently Used)
  • Symbol table management in compiler design

Bonus Point

Is a blockchain essentially a linked list?

‹ Types Of Queue
› Operations On Linked List

Back to top