Study notes for Linked Lists

By Mukesh Kumar|Updated : December 4th, 2021

A linked list is another data structure in which elements are linked with one another. Here, each element is said as a node which is divided into two parts.

  • Information(data) part stores the information.
  • Address or pointer part holds the address of the next element of the same type. The linked list is also known as a self-referential structure.

Each element (node) of a list comprises two items: the data and a reference pointer to the next node.

  • The entry point(start) into a linked list is called the head of the list. Note that the head pointer is not a separate node but a reference to the first node.
  • The last node refer to NULL.
  • If the linked list is completely empty, then the head pointer is a null reference.

 

typedef struct linked list node

{

int data;

struct linkedlistnode * next;

} node;

 

Above is the syntax of declaring a node that contains two fields in it one is for storing information, and another is for storing the address of other nodes to traverse the list. 

 

Advantages:

  • Linked lists are the dynamic data structure as they can change them (grow and shrink) during the execution.
  • Utilizes memory efficiently because here memory is not pre-allocated. 
  • Insertion and deletion can be done easily at the desired location.

Disadvantages:

  • Require more memory if the number of fields is more.
  • Access to an arbitrary data item is time-consuming.

Operations on Linked Lists: 

  • The following operations involved in the linked list are as given belowCreation: Used to create a lined list.
    • Insertion: Used to insert a new node in the linked list at the specified position. A new node may be inserted at the beginning of a linked list.
    • At the end of a linked list
    • At the specified position in a linked list
    • In the case of an empty list, a new node is inserted as a first node.
    • Deletion: This operation is used to delete an item from the linked list. A node can be deleted 
    • From the starting (head) of a linked list.
    • From the end of a linked list.
    • At any specified position.
  • Traversing: Traversing is a process of going through (accessing) all the nodes(items) of a linked list from one to another end.

Types of Linked Lists

  • Singly Linked List: In this each node has one data field and only one address field, which points to the next node. So, the main disadvantage of this list is that we can't access the predecessor of a node from the current node.
  • Doubly Linked List: Each node of the linked list is having two address fields (or links) which help in accessing both the successor node (next node) and predecessor node (previous node).
  • Circular Linked List: It has the address of the first node in the link (or address) field of the last node.
  • Circular Doubly Linked List: It has both the previous and next pointer circularly.

Example1: Reverse of a Singly Linked List with iterations

 
void reverse_list()
{
         node *p, *q, *r;
         if(head == (mynode *)0)
         { return; }
          p = head;
          q = p->next;
          p->next = (mynode *)0;
          while (q != (mynode *)0)
         {
                      r = q->next;
                     q->next = p;
                     p = q;
                      q = r;
          }
           head = p;
}
 
Example 2: Reverse of a Singly Linked List with Recursion
 
node* reverse_list(mynode *root)
{
              if(root->next!=(mynode *)0) 
              {
                             reverse_list(root->next);
                             root->next->next=root;
                             return(root);
               }
               else
               { head=root; }
}
 
Example 3: Reverse of a Doubly Linked List
 
void reverse( )
{
                  node *cur, *temp, *nextnode;
                  if(head==tail)
                               return;
                  if(head==NULL || tail==NULL)
                                return;
                  for(cur=head; cur!=NULL; )
                 {
                               temp=cur->next;
                               nextnode=cur->next;
                               cur->next=cur->prev;
                               cur->prev=temp;
                               cur=nextnode;
                   }
                   temp=head;
                   head=tail;
                    tail=temp;
}
 
Example 4: Finding the middle of a Linked List
 
struct node *middle(struct node *head)
{
           p=head;
           q=head;
           while(q->next->next!=NULL)
          {
                        p=p->next;
                        q=q->next->next;
          }
           return p;
}

Time complexity on Singly Linked Lists of n nodes for the following operations:

  • Adding a new node in the beginning of the list: O(1)
  • Adding a new node in the end: O(n)
  • Adding a new node after a node : O(n)
  • Adding a new node before a node: O(n)
  • Adding a new node after k'th node: O(n)
  • Searching a node with a given data: O(n)
  • Deleting a node from the beginning: O(1)
  • Deleting a node at the end: O(n)
  • Deleting a node with a given data: O(n)
  • Deleting the k'th node: O(n)
  • Modifying the data of all nodes of a given linked list: O(n)
  • Traverse all nodes: O(n)

Time complexity on Doubly Linked Lists of n nodes for the following operations:

  • Adding a new node in the beginning of the list: O(1)
  • Adding a new node in to the end: O(n)
  • Adding a new node after k'th node: O(n)
  • Adding a new node after a node: O(n)
  • Adding a new node before a node: O(n)
  • Searching a node with a given data: O(n)
  • Traversing all nodes: O(n)
  • Deleting a node from the beginning: O(1)
  • Deleting a node from the end: O(n)
  • Deleting a node with a given data: O(n)
  • Deleting the k'th node: O(n)
  • Modifying the data of all nodes in a linked list: O(n)

Time complexity on Circular Linked Lists of n nodes for the following operations:

  • Adding a new node in the beginning of the list: O(n)
  • Adding a new node to the end: O(n)
  • Adding a new node after k'th node: O(n)
  • Adding a new node after a node: O(n)
  • Adding a new node before a node: O(n)
  • Searching a node with a given data: O(n)
  • Deleting a node from the beginning: O(n)
  • Deleting a node from the end: O(n)
  • Deleting a node with a given data: O(n)
  • Deleting the k'th node: O(n)
  • Modifying the data of all nodes in a linked list: O(n)
  • Traversing all nodes: O(n)

Time complexity on Circular Doubly Linked Lists of n nodes for the following operations:

  • Adding a new node in the beginning of the list: O(1)
  • Adding a new node to the end: O(1)
  • Adding a new node after k'th node: O(n)
  • Searching a node with a given data: O(n)
  • Adding a new node after a node with a given data: O(n)
  • Adding a new node before a node with a given data: O(n)
  • Traversing all nodes: O(n)
  • Deleting a node from the beginning: O(1)
  • Deleting a node from the end: O(1)
  • Deleting a node with a given data: O(n)
  • Deleting the k'th node: O(n)
  • Modifying the data of all nodes in a linked list: O(n)

So that was about Linked Lists.

Posted by:

Mukesh KumarMukesh KumarMember since Feb 2020
Share this article   |

Comments

write a comment
Load Previous Comments
Ajitem Joshi
Can someone help me by what "(mynode *)0" means?
Sachin Kumar Saxena
http://examworld.co.in/computer/
Amit Kumar

Amit KumarAug 6, 2019

Hello , I am not able to solve operating system questions ....every time I need to see the solution what should I do?
Ramashankar Yadav
Mam how I do better in CS
Mukesh Kumar

Mukesh KumarMar 11, 2020

Mam isn't those time complexity for inserting new node in the end of the doubly linked list wrong as we already maintain a tail pointer by which we can delete in O(1) and same is the case for deletion also
...Read More
Pradhnya

PradhnyaJul 22, 2020

Great  notes  I never  seen that like this language is simple n easy to understand
Bikram Das

Bikram DasNov 6, 2020

In case of finding middle element of linked list, I think all times there would not be returned the address of p . If the linked list consists of even number of elements then the address of p would be returned otherwise the address of q would be returned. Please, help me.. I am confusing about this. I am not sure.
...Read More
Aashish Parmar
रवीना

Follow us for latest updates