A singly linked list is a type of linked list where each node has just one link pointing to the next node.

Linked List Operations: Traverse, Insert and Delete

There are different linked list operations that let us do various tasks on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article:

• Traversal - access each element of the linked list

• Insertion - add a new element to the linked list

• Deletion - remove existing elements

• Search - find a node in the linked list

• Sort - sort the nodes of the linked list

Things to Remember about Linked List

• head points to the first node of the linked list

• next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

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

---

Traverse a Linked List

Displaying the contents of a linked list is very simple. We keep moving the temp node to the next one and display its contents.

When temp is NULL, we know we have reached the end of the linked list, so we exit the while loop.

struct node *temp = head;
printf("\n\nList elements are - \n");
while(temp != NULL) {
  printf("%d --->",temp->data);
  temp = temp->next;
}

The output of this program will be:

List elements are - 
1 --->2 --->3 --->

---

Insert Elements to a Linked List

You can add elements to either the beginning, middle or end of the linked list.

1. Insert at the beginning

• Allocate memory for new node

• Store data

• Change next of new node to point to head

• Change head to point to recently created node

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

2. Insert at the End

• Allocate memory for new node

• Store data

• Traverse to last node

• Change next of last node to recently created node

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

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

temp->next = newNode;

3. Insert at the Middle

• Allocate memory and store data for the new node

• Move to the node just before where you want to insert the new node

• Update the next pointers to insert the new node in between

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

struct node *temp = head;

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

---

Delete from a Linked List

You can delete either from the beginning, end or from a particular position.

1. Delete from beginning

• Point head to the second node

head = head->next;

2. Delete from end

• Traverse to second last element

• Change its next pointer to null

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

3. Delete from middle

• Traverse to the node before the one you want to delete

• Change the next pointers to skip the node you want to remove

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

temp->next = temp->next->next;

---

Search an Element on a Linked List

YYou can search for an element in a linked list using a loop with these steps. We are looking for item in the linked list.

• Set head as the current node.

• Run a loop until the current node is NULL because the last element points to NULL.

• In each loop, check if the node's key is equal to item. If it matches, return true; otherwise, return false.

// Search a node
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
    if (current->data == key) return true;
      current = current->next;
  }
  return false;
}

---

Sort Elements of a Linked List

We will use a simple sorting algorithm, Bubble Sort, to sort the elements of a linked list in ascending order.

1. Make the head the current node and create another node index for later use.

2. If head is null, return.

3. Otherwise, run a loop until the last node (i.e., NULL).

4. In each iteration, follow steps 5-6.

5. Store the next node of current in index.

6. Check if the data of the current node is greater than the next node. If it is, swap current and index.

// Sort the linked list
void sortLinkedList(struct Node** head_ref) {
  struct Node *current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
    return;
  } else {
    while (current != NULL) {
      // index points to the node next to current
      index = current->next;

      while (index != NULL) {
        if (current->data > index->data) {
          temp = current->data;
          current->data = index->data;
          index->data = temp;
          }
          index = index->next;
      }
      current = current->next;
    }
  }
}

---

LinkedList Operations in Python, Java, C, and C++

# Linked list operations in Python


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


class LinkedList:

    def __init__(self):
        self.head = None

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

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

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

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

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    # Insert at the end
    def insertAtEnd(self, new_data):
        new_node = Node(new_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 is None:
            return

        temp = self.head

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

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

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

        if temp.next is None:
            return

        next = temp.next.next

        temp.next = None

        temp.next = next

    # Search an element
    def search(self, key):

        current = self.head

        while current is not None:
            if current.data == key:
                return True

            current = current.next

        return False

    # Sort the linked list
    def sortLinkedList(self, head):
        current = head
        index = Node(None)

        if head is None:
            return
        else:
            while current is not None:
                # index points to the node next to current
                index = current.next

                while index is not None:
                    if current.data > index.data:
                        current.data, index.data = index.data, current.data

                    index = index.next
                current = current.next

    # Print the linked list
    def printList(self):
        temp = self.head
        while (temp):
            print(str(temp.data) + " ", end="")
            temp = temp.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()

    print()
    item_to_find = 3
    if llist.search(item_to_find):
        print(str(item_to_find) + " is found")
    else:
        print(str(item_to_find) + " is not found")

    llist.sortLinkedList(llist.head)
    print("Sorted List: ")
    llist.printList()

Complexity

Characteristics of a Singly Linked List:

• Each node holds a value and a reference to the next node in the list.

• The list has a head, which points to the first node, and a tail, which points to the last node.

• The nodes are not stored next to each other in memory; each node holds the address of the next node.

• To access an element, you need to start from the head and move through the list to find the desired node, as there is no direct access to any specific node.

Application of Singly Linked Lists:

• Memory management: Singly linked lists can be used to create memory pools, where memory is given out and taken back as needed.

• Database indexing: Singly linked lists can be used in databases to allow quick insertion and deletion of data.

• Representing polynomials and sparse matrices: Singly linked lists can efficiently represent polynomials and sparse matrices, where most elements are zero.

• Operating systems: Singly linked lists are used in operating systems for tasks like scheduling processes and managing system resources.

Advantages of Singly Linked Lists:

• Dynamic memory allocation: Singly linked lists let you change the size of the list at runtime by adding or removing elements.

• Cache friendliness: Singly linked lists can be cache-friendly because nodes can be stored in separate cache lines, reducing cache misses and improving performance.

• Space-efficient: Singly linked lists are space-efficient since each element only needs to store a reference to the next node, not a large block of contiguous memory.

Disadvantages of Singly Lists:

• Poor random access performance: Accessing an element in a singly linked list requires going through the list from the head to the desired node, making it slower for random access compared to arrays.

• Increased memory overhead: Singly linked lists need extra memory to store pointers to the next node in each element, leading to more memory usage compared to arrays.

• Vulnerability to data loss: Singly linked lists can lose data if a node’s next pointer is lost or corrupted, as there is no way to access other elements in the list.

• Not suitable for parallel processing: Singly linked lists are not good for parallel processing because updating a node needs exclusive access to its next pointer, which is hard to manage in parallel environments.

• Backward traversing not possible: Singly linked lists do not support backward traversing.