hamburger

Study notes for Linked Lists

By BYJU'S Exam Prep

Updated on: September 26th, 2023

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. 

Study notes for Linked Lists

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.

Click Here to Avail GATE CSE Test Series!

Thanks

#DreamStriveSucceed

Our Apps Playstore
POPULAR EXAMS
SSC and Bank
Other Exams
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com
Home Practice Test Series Premium