Linked List

The basics.

A Linked List is a linear and dynamic data structure.

Unlike arrays, linked list elements are not stored at a contiguous location, the elements are linked using pointers hence it includes a series of connected nodes. Each node in a list consists of at least two parts:

• A data item (we can store integers, strings or any type of data)
• Pointer(or Reference) to the next node that connects one node to another or an address of the next node.

A linked list is represented by a pointer to the first node of the linked list .The first node is called head of the linked list. If the linked list is empty, then the value of the head points to NULL.

You might be wondering why to use a linked list if we have an array which is also a linear data structure.

• The size of the arrays is fixed

So we must know the upper limit on the number of elements in advance.

• Insertion of a new element / Deletion of a existing element in an array of elements is expensive

In Array room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

Some of the basic types of linked list are

1. Singly linked list:

In this type of linked list, one can move or traverse the linked list in only one direction. where the next pointer of each node points to other nodes but the next pointer of the last node points to NULL.

Source

2. Doubly linked list:

Each node in a doubly linked list has a reference to both the next node and the previous node in the sequence.In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward).

Source

3. Circular linked list:

In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer.

Source

Now we will explore more about Singly linked list.

Consider the below class Node to which every node of linked list belong for below functions:

class Node
    {
        int data;
        Node next;
           
        // Constructor to create a new node

        Node(int d) {
        data = d; 
        next = null; 
        }
    }

INSERTION:

1. At the front of the linked list:

The new node is added before the head of the given Linked List.The newly added node becomes the new head of the Linked List.

For example, if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25.

Time Complexity: O(1),Auxiliary Space: O(1)

Source

Approach:

1)Allocate the Node & Put in the data.

2)Make the next of new Node as head.

3)Move the head to point to new Node

//This function Inserts a new Node at the front of the list. 
  public void push(int new_data){

      Node new_node = new Node(new_data);
      new_node.next = head;
      head = new_node;
}

2. After a given node:

For example, if the given Linked List is 10->15->20->25 and we add an item 5 after 15, then the Linked List becomes 10->15->5->20->25.

Time Complexity: O(1),Auxiliary Space: O(1)

Approach:

1. Firstly, check if the given previous node is NULL or not.
2. Then, allocate a new node
3. Assign the data to the new node
4. And then make the next of the new node as the next of previous node.
5. Finally, move the next of the previous node as a new node.

Source

//This function Inserts a new node after the given prev_node. 
public void insertAfter(Node prev_node, int new_data)
{
    /*Check if the given Node is null */
    if (prev_node == null) {
        System.out.println(
            "The given previous node cannot be null");
        return;
    }
  
    /* Allocate the Node & Put in the data*/
    Node new_node = new Node(new_data);
  
    /*Make next of new Node as next of prev_node */
    new_node.next = prev_node.next;
  
    /* make next of prev_node as new_node */
    prev_node.next = new_node;
}

3. At the end of the Linked List:

The new node is added after the last node of the given Linked List. We have to traverse the list till the end and then change the next to last node to a new node.

For example if the given Linked List is 5->10->15->20->25 and we add an item 30 at the end, then the Linked List becomes 5->10->15->20->25->30.

Time complexity: O(N), Auxiliary Space: O(1).

Source

Approach:

Allocate the Node & Put in the data & Set next as null.

If the Linked List is empty, then make the new node as head

Else traverse till the last node

Change the next of last node and assign to new node

public void append(int new_data)
{
    Node new_node = new Node(new_data);
    if (head == null)
    {
        head = new Node(new_data);
        return;
    }
  
    Node last = head; 
    while (last.next != null)
        last = last.next;
  
    last.next = new_node;
    return;
}

TRAVERSAL OF LINKED LIST:

Traversal of linked list means visiting every node present in the linked list.

Approach:

Create a pointer that initially points to the head of the linked list.

Repeat the following steps until the current node is NULL:

a. Access the data stored in the current node.

b. Move the current pointer to the next node by following the next pointer.

c. Repeat from step 2a.

public void printList()
    {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

DELETION:

Delete the first node or head node of the linked list.

Approach:

1. If the linked list is empty (i.e., head is NULL), return.
2. Create a temporary pointer, called “temp”, that points to the head of the linked list.
3. Move the head pointer to the next node.
4. Delete the temporary node by freeing the memory it occupied.

Source

static Node removeFirstNode(Node head)
 {
        if (head == null)
            return null;
  
        // Move the head pointer to the next node
        Node temp = head;
        head = head.next;
  
        return head;
  }

Delete from middle

Approach:

1. If the linked list is empty (i.e., head is NULL), return.
2. Create a pointer, called “current”, that initially points to the head of the linked list.
3. Repeat the following steps until the “current” node is the node before the node to be deleted or the end of the linked list is reached:
4. Move the “current” pointer to the next node.
5. If the end of the linked list is reached without finding the node before the node to be deleted, return.
6. Set the “next” pointer of the current node to point to the node after the node to be deleted.

Source

/*code for deleting the node in between assuming that nodeTodeleted is present in the Linked list*/
public void deleteNode(Node nodeToDelete) { 
if (head == null) 
    return; 
Node current = head; 
while (current.next != null && current.next != nodeToDelete) { 
    current = current.next; 
} 
current.next = current.next.next; 
} 

Delete last node from the linked list:

Approach:

1. If the linked list is empty (i.e., head is NULL), return.
2. Create a pointers called “temp” and initialise the pointer to the head of the linked list.
3. Repeat the following steps until the temp.next.next(i.e 2nd last node is reached) is null of the linked list is reached:
4. Move the temp pointer to the next node.
5. Set the “next” pointer of the “temp” node to be NULL.

Source

static Node removeLastNode(Node head) {
 
        if(head == null || head.next == null) {
            return null;
        }
        // Find the second last node
        Node temp = head;
        while(temp.next.next != null) {
            temp = temp.next;
        }
        // change the second last node next pointer to null
        temp.next = null;
 
        return head;
    }

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.