Singly Linked Lists

Singly Linked Lists

A singly linked list is a data structure that consists of a sequence of elements called nodes. Each node contains two parts: data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.

Structure of a Node

Each node in a singly linked list has the following structure:

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

Here, data holds the value of the node, and next is a pointer that references the next node in the list. If a node is the last node, its next pointer is set to null.

Creating a Singly Linked List

To create a singly linked list, you need to define a head pointer that points to the first node. If the list is empty, the head pointer is set to null.

Node* head = null;

To add nodes to the list, you can create a new node and adjust the pointers accordingly.

Inserting Nodes

Inserting at the Beginning

To insert a new node at the beginning of the list, follow these steps:

1. Create a new node.
2. Set the new node's next pointer to the current head.
3. Update the head pointer to point to the new node.

Here is an example:

Node* newNode = new Node();  newNode->data = 10;  newNode->next = head;  head = newNode;

Inserting at the End

To insert a new node at the end of the list, you need to traverse the list until you reach the last node. Then, set the last node's next pointer to the new node.

Node* newNode = new Node();  newNode->data = 20;  newNode->next = null;  if (head == null) {    head = newNode;  } else {    Node* current = head;    while (current->next != null) {      current = current->next;    }    current->next = newNode;  }

Inserting at a Specific Position

To insert a node at a specific position, you need to traverse the list to the desired position and then adjust the pointers. For example, to insert at position n:

1. Start from the head.
2. Traverse to the (n-1)th node.
3. Link the new node to the nth node.
4. Link the (n-1)th node to the new node.

Here is an example:

Node* newNode = new Node();  newNode->data = 30;  if (n == 0) {    newNode->next = head;    head = newNode;  } else {    Node* current = head;    for (int i = 0; i < n - 1; i++) {      current = current->next;    }    newNode->next = current->next;    current->next = newNode;  }

Deleting Nodes

Deleting the First Node

To delete the first node, simply update the head pointer to point to the second node:

if (head != null) {  Node* temp = head;  head = head->next;  delete temp;}

Deleting a Node by Value

To delete a node with a specific value, you need to traverse the list, keeping track of the previous node:

Node* current = head;  Node* previous = null;  while (current != null && current->data != value) {    previous = current;    current = current->next;  }  if (current != null) {    if (previous == null) {      head = current->next;    } else {      previous->next = current->next;    }    delete current;  }

Deleting the Last Node

To delete the last node, traverse the list until you reach the second last node and set its next pointer to null:

if (head != null) {  if (head->next == null) {    delete head;    head = null;  } else {    Node* current = head;    while (current->next->next != null) {      current = current->next;    }    delete current->next;    current->next = null;  }}

Traversing a Singly Linked List

To traverse a singly linked list, start from the head and visit each node until you reach the end:

Node* current = head;  while (current != null) {    cout << current->data << " ";    current = current->next;  }

Searching for a Value

To search for a specific value in the list, traverse the list and compare each node's data with the target value:

Node* current = head;  while (current != null) {    if (current->data == value) {      return true;    }    current = current->next;  }  return false;

Reversing a Singly Linked List

To reverse a singly linked list, you need to change the direction of the links. Use three pointers: previous, current, and next:

Node* previous = null;  Node* current = head;  while (current != null) {    next = current->next;    current->next = previous;    previous = current;    current = next;  }  head = previous;

Applications of Singly Linked Lists

Singly linked lists are used in various applications, such as:

• Implementing stacks and queues
• Dynamic memory allocation
• Managing lists of items, such as playlists in media applications

Complexity Analysis

The time complexity for various operations in a singly linked list is as follows:

• Insertion at the beginning: O(1)
• Insertion at the end: O(n)
• Insertion at a specific position: O(n)
• Deletion of the first node: O(1)
• Deletion by value: O(n)
• Traversal: O(n)

Summary

• A singly linked list consists of nodes with data and a link to the next node.
• Insertion can occur at the beginning, end, or a specific position.
• Deletion can occur at the beginning, end, or by value.
• Traversal and searching are done by visiting each node.
• Reversing the list changes the direction of the links.

Check your understanding

1. What is the structure of a node in a singly linked list?
2. How do you insert a node at the end of a singly linked list?
3. What is the time complexity of deleting a node by value?
4. How can you reverse a singly linked list?