Linked List in Data Structure

In computer science, we refer to the format of storing data on storage devices as a data structure. An array is the collection of data stored in contiguous memory locations.

This makes accessibility very easy but it leads to not so efficient use of memory because the smaller chunks of memory that are left between earlier stored data are not used.

But what if you need more efficient utilization of your memory. Here dynamic data structures come into the picture. Dynamic data structures as the name suggest do not have a fixed memory size.

They can shrink or grow themselves by deallocating or allocating the memory respectively, as and when required.

In this article, we will learn about the most basic dynamic data structures, Linked list, their types, and how to do basic operations on a linked list.

Linked List in Data Structure

A linked list is the most basic type of dynamic data structure. A linked list is a linear collection of data where the order of elements is not given by their physical memory address. The user stores the data in blocks of memory called nodes.

Each node has two parts. The first part contains the data and the second part points towards the next node. It contains the address of the next node in the actual memory.

Types of Linked Lists

1. Singly Linked list

Singly-linked lists are the most basic and easy to implement linked lists. Each node stores the data at random memory locations and contains a pointer that points to the next node in the memory.

2. Doubly linked list

Each node contains data and two pointers. One point to the previous node and the other points to the next node. This makes doubly-linked traversable both forward and backward.

3. Circular linked list

Just like a singly linked list, here also each node is linked to the next only with a slight modification. In a circular linked list, the last node of the list is pointed to the first node forming a loop. So we can reach the previous node by traversing forward.

In this article, we will be learning about Singly-linked lists only. We will learn about other types in detail in future articles.

Singly Linked list in Data Structure

A singly linked list as we have seen contains multiple nodes in which the earlier node points at the next node except the last node. A node has two parts, the first one contains the data and the second part contains the address of the next node.

Creating Node in Linked List

C program for creating a Linked List Node:

struct node   
{  
    int data;                 // data to store in node
    struct node *next;   //NULL for last node
}  

The previous part of the first node and the next part of the last node will always have NULL.

Need of Pointers in Linked List

Unlike arrays, in a linked list, memory allocation takes place at runtime and therefore memory location of each node is random. Each node can be present anywhere in the memory and to access them, each node has the address of its next node stored with it.

This forms a kind of link between every node. This is the additional pointer that we need because if the link is not present or it’s broken, the memory locations will be lost.

Basic Linked List Operations

• Insert: Insert the node at any position. Worst-case time complexity O(1).
• Delete: Delete the node at any position. Worst-case time complexity O(1).
• Search: Search for a specific node in the list. The worst-case time complexity O(n).
• Display: Display a complete list. The worst-case time complexity O(n).

Adding Nodes in Linked List

Adding nodes in a linked list can be sometimes tricky. Since a linked list is a dynamic data structure, we can not just break a link and add or delete the node anywhere. To better understand this let us do a thought experiment.

Consider a linked list similar to a train with multiple coaches. Each coach represents the first part of the node where data is present, here passengers. The next part of the coach, i.e. the coupling represents the second part of the node. This part contains a connection to the next node.

Now, if you want to add a new coach to a moving train you cannot simply uncouple any two coaches and add a new coach. As soon as you uncouple the coaches, the second part of the train which is not attached to the engine will be left behind and that will fail the task.

Similarly, in the linked list, we cannot just break a link between any two nodes and add a new node. Suppose you want to add a new node between the fourth and fifth nodes. To do that you first have to traverse from the first node to the fifth node.

Point the new node to the fifth node and then traverse again from the start to the fourth node. Point the fourth node towards the new node. The new node is now a part of the linked list.

1. Insert node at the beginning

Create a new node and point it to the first node.

void insertAtBegin(node *new) 
{
  new->next = head;
  head = new;
 }

2. Insert node at position ‘n’

Link new node to nth node, traverse to (n-1)th node, point (n-1)th node to new node.

Void insertAtPosition(node *new, node *previous)
{
    new -> next = previous -> next;
    previous -> next = new;
}

3. Insert node at last

Point the last node to the new node and point the new node to NULL.

Void insertAtEnd(node *new)
{
    while (last -> next != NULL)
               last = last -> next;
    last -> next = new;
    new -> next = NULL;
}

Deleting nodes in Linked List

1. Delete the first Node in Linked List

Point ‘prev’ of the second node to NULL.

void DeleteAtFirst()
{
     Node *temp  = *head;   
     head = temp -> next;
     free(temp);
    
}

2. Delete node at position ‘n’ in Linked List

Traverse to the node at the ‘n-1’ position and point it to the ‘n+1’ node. Delink node at position ‘n’ and ‘n+1’.

void DeleteAtPosition(int pos)  
{  
    struct node *ptr,*ptr1;   
    ptr=head;  
    for(i=0;i<pos;i++)  
    {  
        ptr1 = ptr;       
        ptr = ptr->next;  
    }  
    ptr1 ->next = ptr ->next;  
    free(ptr);   
}

3. Delete the node at last position

Point the second last node to null.

void DeleteAtLast()
{
     Node *ptr, *ptr1;
     ptr = head;
     while (ptr -> next != NULL)
     {
          ptr1 = ptr;
          ptr = ptr -> next;
     }
     ptr1 -> next =NULL;
     free ptr;   
}

Search node in Linked List

Searching for an element in the linked list. We compare the data of each node to the search element and return the location if found. If not found return -1.

Boolean flag= false;
bool search(struct Node* head, int x)
{
    struct Node* current = head;
    while (current != NULL)
    {
        if (current->key == x)
          {
            flag = true;
            break;
    }
}
    return flag;
}

Traversing the linked list

Move the control pointer from the first node to the last node via each node in between and display data of each node.

Int traverse(struct Node* head)
{
    struct Node* current = head;
    while (current != NULL)
    {
        return current -> data;
    }
}

Reversing a linked list

We need the head to point at the last node and the first node to point at NULL. In between all nodes will be pointing to their previous node in the original linked list.

void reverse(struct Node** head)
{
    struct Node* previous = NULL;
    struct Node* current = *head;
    struct Node* next = NULL;
    while (current != NULL) 
{
        next = current->next;    
        current->next = previous;
        previous = current;
        current = next;
    }
    *head = previous;
}

Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>
  
struct Node
 {
    int data;
    struct Node* next;
};
  
int main()
{
    struct Node* Node1 = NULL;
    struct Node* Node2 = NULL;
    struct Node* Node3 = NULL;
  
    
   Node1 = (struct Node*)malloc(sizeof(struct Node));
   Node2 = (struct Node*)malloc(sizeof(struct Node));
   Node3 = (struct Node*)malloc(sizeof(struct Node));
  
     
    Node1 -> data = 1; 
    Node1 -> next = Node2;   
       
    Node2 -> data = 2;
    Node2 -> next = Node3;
  
     
    Node3 -> data = 3; 
    Node3 -> next = NULL;
  
    display(Node1);
    return 0;
}

void display(struct Node* disp)
{
    while (disp != NULL) 
{
        printf(" %d ", disp -> data);
        disp = disp -> next;
    }
}

Linked list implementation in Python

class Node:
    def __init__(self, data):
        self.data = data  
        self.next = None  
  
class SinglyLinkedList:    
    def __init__(self):
        self.head = None
    
    def DsiplayList(self):
        temp = self.head
        while (temp):
            print (temp.data)
            temp = temp.next
  
if __name__=='__main__':
  
    sll = SinglyLinkedList()
  
    sll.head = Node(1)
    Node2 = Node(2)
    Node3 = Node(3)
  
    sll.head.next = Node2; 
    Node2.next = Node3; 
  
    llist.DisplayList()

Implementation of Linked List in C++

#include <bits/stdc++.h>
using namespace std;
  
class Node {
public:
    int data;
    Node* next;
};
  
void displayList(Node* n)
{
    while (n != NULL)
 {
        cout << n -> data << " ";
        n = n -> next;
    }
}
 
int main()
{
    Node* Node1 = NULL;
    Node* Node2 = NULL;
    Node* Node3 = NULL;
  
    Node1 = new Node();
    Node2 = new Node();
    Node3 = new Node();
  
    Node1 -> data = 1; 
    Node1 -> next = Node2; 
  
    Node2 -> data = 2; 
    Node2 -> next = Node3;
  
    Node3 -> data = 3; 
    Node3 -> next = NULL;
  
    displayList(Node1);
  
    return 0;
}

Linked list implementation in Java

class SinglyLinkedList
 {
    
Node head; 
 
    static class Node
   {
        int data;
        Node next;
        
        Node(int d)
        {
            data = d;
            next = null;
        } 
    }
  
    
    public void DisplayList()
    {
        Node n = head;
        while (n != null) 
        {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }
  
    public static void main(String[] args)
    {
        
        SinglyLinkedList sllist = new SinglyLinkedList();
  
        sllist.head = new Node(1);
        Node Node2 = new Node(2);
        Node Node3 = new Node(3);
  
        sllist.head.next =Node2; 
        Node2.next = Node3; 
  
        sllist.DisplayList();
    }
}

Complexity of Linked List

Space complexity: O(n)
Time complexity:

Advantages of Linked List

1. Memory allocation takes place dynamically. A linked list can change the size, while an array has a fixed size.
2. Nodes in a linked list are non-contiguous stored, thus making efficient use of memory.
3. No empty node can be present in a linked list.
4. Nodes are created randomly in the memory, therefore, space utilization is highly optimized.

Disadvantages of Linked List

1. Wastage of memory due to pointers.
2. Reverse traversing is not possible.
3. Accessing nodes at random is not possible.

Array vs Linked list

Applications of Linked List

1. Linked lists are used in programming requiring dynamic memory allocation.

2. Advance scientific calculations and numerical analysis using sparse matrices. The sparse matrix is represented by a linked list.

3. Linked list is useful for the implementation of stacks and queues.

4. Also used in reversing the functionality of the software.

5. Hash tables are created using linked lists. Hash table entries are implemented by a linked list.

6. Graphs use linked lists. If you want to represent graphs as an adjacency list, we use linked lists.

7. Polynomials can be represented with the help of linked lists. Each term in a polynomial has coefficient and power. Coefficient and power are stored as nodes and pointer points to the next node.

Conclusion

After going through this article, we now have some basic understanding of linked lists, some real-life examples of linked lists, how linked lists work, and types of linked lists.

We also learned some basic operations on a linked list like adding nodes, deleting nodes. We will learn about doubly linked lists and circular linked lists in future articles.