Operations On Linked List

In this tutorial, we are going to learn the Linked List operations and implementation of Linked List in C, C++, Java, Python.

---

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

Check basic concepts of Linked List here.

Structure of node in Linked List is

struct Node 
{ 
    int data; 
    struct Node* next; 
}; 

Note: If next pointer of a node is set to NULL then its end of the linked list.

Operations on Linked List

• Insert
  • Insert At Start
  • Insert At End
  • Insert At Position
• Delete
  • Delete At Start
  • Delete At End
  • Delete At Position
• Traverse : Traversing means visiting every node of the linked list at once.

Insert Operation

Insert At Start:

• Allocate memory for new node using malloc()
• Store data in the node
• Change next pointer of new node to point to head
• Change head to point to newly created node

struct node *newNode;   //refer above struct node
newNode = malloc(sizeof(struct node));
newNode->data = 5;
newNode->next = head;
head = newNode;

Insert At End:

• Allocate memory for new node using malloc()
• Store data in the node
• Traverse to the last node
• Change next pointer of last node to newly created node
• Set next pointer of newly created node to NULL

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 5;
newNode->next = NULL;

struct node *temp = head;
while(temp->next != NULL){
  temp = temp->next;
}

temp->next = newNode;

Insert At Position:

• Allocate memory for new node using malloc()
• Store data in the node
• Traverse to the node just before the position
• Change the next of newly created node to the node before the position(Like mentioned in the code).

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 5;

struct node *temp = head;

//position input by user. Display appropriate error message if position is greater than length of linked list

for(int i=1; i < position; i++) {
    if(temp->next != NULL) {
        temp = temp->next;
    }
}
newNode->next = temp->next;
temp->next = newNode;

---

Delete Operation

Delete At Start

• Store first node in a temporary struct node pointer
• Point head to the second node
• Free the temporary node

struct node *temp = head;
head = head->next;
free(temp);

Delete At End

• Traverse to the second last element
• Store next of second last element in temporary struct node pointer
• Change its next pointer to null
• Free the temporary pointer

struct node* temp = head;
while(temp->next->next!=NULL){
  temp = temp->next;
}
struct node* t = temp->next;
temp->next = NULL;
free(t);

Delete At Position

• Traverse to the node before the position to be deleted
• Change next pointers as mentioned in code below

for(int i=1; i< position; i++) {
    if(temp->next!=NULL) {
        temp = temp->next;
    }
}
temp->next = temp->next->next;

---

Linked List Traversal

Traversing meaning visiting each node in the Linked List at once. Starting from head pointer to the last node.

Last node is identified by the next pointer. If next pointer of a node is set to NULL then this node is last node of the linked list.

struct node *temp = head;
printf("Linked List Elements: \n");

while(temp != NULL)
{
     printf("%d  ->  ",temp->data);
     temp = temp->next;
}

---

Implementing Of Linked List Operations

#include <stdio.h>
#include <stdlib.h>  //for malloc() 

// Create a node
struct Node {
  int item;
  struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the item
  new_node->item = data;
  new_node->next = (*ref);

  // Move head to new node
  (*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* node, int data) {
  if (node == NULL) {
    printf("the given previous node cannot be NULL");
    return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->item = data;
  new_node->next = node->next;
  node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *ref;

  new_node->item = data;
  new_node->next = NULL;

  if (*ref == NULL) {
    *ref = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}

void deleteNode(struct Node** ref, int key) {
  struct Node *temp = *ref, *prev;

  if (temp != NULL && temp->item == key) {
    *ref = temp->next;
    free(temp);
    return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->item);
    node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);
}

#include <stdlib.h>
#include <iostream>

using namespace std;

// Create a node
struct Node {
  int item;
  struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {

  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the item
  new_node->item = data;
  new_node->next = (*ref);

  // Move head to new node
  (*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* prev_node, int data) {
  if (prev_node == NULL) {
    cout << "the given previous node cannot be NULL";
    return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->item = data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *ref;

  new_node->item = data;
  new_node->next = NULL;

  if (*ref == NULL) {
    *ref = new_node;
    return;
  }

  while (last->next != NULL)
    last = last->next;

  last->next = new_node;
  return;
}

void deleteNode(struct Node** ref, int key) {
  struct Node *temp = *ref, *prev;

  if (temp != NULL && temp->item == key) {
    *ref = temp->next;
    free(temp);
    return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->item != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    cout << node->item << " ";
    node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  cout << "Linked list: ";
  printList(head);

  cout << "\nAfter deleting an element: ";
  deleteNode(&head, 3);
  printList(head);
}

class LinkedList {
  Node head;

  // Create a node
  class Node {
    int item;
    Node next;

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

  public void insertAtBeginning(int data) {
    // insert the item
    Node new_node = new Node(data);
    new_node.next = head;
    head = new_node;
  }

  public void insertAfter(Node prev_node, int data) {
    if (prev_node == null) {
      System.out.println("The given previous node cannot be null");
      return;
    }
    Node new_node = new Node(data);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
  }

  public void insertAtEnd(int data) {
    Node new_node = new Node(data);

    if (head == null) {
      head = new Node(data);
      return;
    }

    new_node.next = null;

    Node last = head;
    while (last.next != null)
      last = last.next;

    last.next = new_node;
    return;
  }

  void deleteNode(int position) {
    if (head == null)
      return;

    Node node = head;

    if (position == 0) {
      head = node.next;
      return;
    }
    // Find the key to be deleted
    for (int i = 0; node != null && i < position - 1; i++)
      node = node.next;

    // If the key is not present
    if (node == null || node.next == null)
      return;

    // Remove the node
    Node next = node.next.next;

    node.next = next;
  }

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

  public static void main(String[] args) {
    LinkedList llist = new LinkedList();

    llist.insertAtEnd(1);
    llist.insertAtBeginning(2);
    llist.insertAtBeginning(3);
    llist.insertAtEnd(4);
    llist.insertAfter(llist.head.next, 5);

    System.out.println("Linked list: ");
    llist.printList();

    System.out.println("\nAfter deleting an element: ");
    llist.deleteNode(3);
    llist.printList();
  }
}

# Create a node
class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.head = None

    # Insert at the beginning
    def insertAtBeginning(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

    # Insert after a node
    def insertAfter(self, node, data):

        if node is None:
            print("The given previous node must inLinkedList.")
            return

        new_node = Node(data)
        new_node.next = node.next
        node.next = new_node

    # Insert at the end
    def insertAtEnd(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while (last.next):
            last = last.next

        last.next = new_node

    # Deleting a node
    def deleteNode(self, position):

        if self.head == None:
            return

        temp_node = self.head

        if position == 0:
            self.head = temp_node.next
            temp_node = None
            return

        # Find the key to be deleted
        for i in range(position - 1):
            temp_node = temp_node.next
            if temp_node is None:
                break

        # If the key is not present
        if temp_node is None:
            return

        if temp_node.next is None:
            return

        next = temp_node.next.next
        temp_node.next = None
        temp_node.next = next

    def printList(self):
        temp_node = self.head
        while (temp_node):
            print(str(temp_node.item) + " ", end="")
            temp_node = temp_node.next


if __name__ == '__main__':

    llist = LinkedList()
    llist.insertAtEnd(1)
    llist.insertAtBeginning(2)
    llist.insertAtBeginning(3)
    llist.insertAtEnd(4)
    llist.insertAfter(llist.head.next, 5)

    print('Linked list:')
    llist.printList()

    print("\nAfter deleting an element:")
    llist.deleteNode(3)
    llist.printList()

---

‹ Linked List Data Structure
› Types of Linked List