Demystifying Algorithms: Singly Linked Lists

What is a Singly Linked List?

A singly linked list is a data structure consisting of nodes arranged in a sequence. Each node contains:

1. Data: The value stored in the node.
2. Next: A pointer (reference) to the next node in the sequence.

In a singly linked list:

• The first node is called the head.
• The last node’s Next pointer is null, indicating the end of the list.

This structure allows for efficient insertions and deletions compared to arrays but requires traversal to access specific elements.

The Technical View

• Time Complexity:

  • Access: (O(n)) (traverse from the head to find an element).
  • Insertion/Deletion:
  • At the head: (O(1)).
  • At a specific position: (O(n)).

• Space Complexity:

  • (O(n)), where (n) is the number of nodes.
  • Additional memory is required for pointers in each node.

A Fifth-Grader's Summary

Think of a singly linked list as a line of people holding hands. Each person has a name tag (data) and points to the next person (next). If you want to add or remove someone, you just adjust the hands—they don’t all need to shuffle around like in a line of cards (array).

Real-World Example

A playlist in a music app can work like a singly linked list. Each song (node) knows the next song to play (pointer). If you add or remove a song, the app updates the links between songs without reordering all the others.

Operations on a Singly Linked List

1. Insert a Node at the Head

Problem: Add a new node with value 3 at the beginning of the list.

Code:

class SinglyLinkedListNode {
    public int Data;
    public SinglyLinkedListNode Next;

    public SinglyLinkedListNode(int data) {
        Data = data;
        Next = null;
    }
}

SinglyLinkedListNode InsertAtHead(SinglyLinkedListNode head, int data) {
    SinglyLinkedListNode newNode = new SinglyLinkedListNode(data);
    newNode.Next = head;
    return newNode;
}

Initial List: 5 -> 10 -> 15 -> null

Steps:

1. Create a new node with data 3.
2. Point the new node’s Next to the current head (5).
3. Update the head to the new node.

Updated List: 3 -> 5 -> 10 -> 15 -> null

2. Insert a Node at the Tail

Problem: Add a new node with value 20 at the end of the list.

Code:

SinglyLinkedListNode InsertAtTail(SinglyLinkedListNode head, int data) {
    SinglyLinkedListNode newNode = new SinglyLinkedListNode(data);
    if (head == null) return newNode;

    SinglyLinkedListNode current = head;
    while (current.Next != null) {
        current = current.Next;
    }
    current.Next = newNode;
    return head;
}

Initial List: 5 -> 10 -> 15 -> null

Steps:

1. Create a new node with data 20.
2. Traverse to the last node (15).
3. Set the last node’s Next to the new node.

Updated List: 5 -> 10 -> 15 -> 20 -> null

3. Insert a Node at a Specific Position

Problem: Insert a node with value 12 at position 2 (0-based index).

Code:

SinglyLinkedListNode InsertAtPosition(SinglyLinkedListNode head, int data, int position) {
    SinglyLinkedListNode newNode = new SinglyLinkedListNode(data);

    if (position == 0) {
        newNode.Next = head;
        return newNode;
    }

    SinglyLinkedListNode current = head;
    while (position - 1 > 0) {
        current = current.Next;
        position--;
    }

    newNode.Next = current.Next;
    current.Next = newNode;

    return head;
}

Initial List: 5 -> 10 -> 15 -> null

Steps:

1. Create a new node with data 12.
2. Traverse to the node at position 1 (10).
3. Set the new node’s Next to the node at position 2 (15).
4. Update the node at position 1 (10) to point to the new node.

Updated List: 5 -> 10 -> 12 -> 15 -> null

4. Delete a Node

Problem: Remove the node at position 1 (0-based index).

Code:

SinglyLinkedListNode DeleteNode(SinglyLinkedListNode head, int position) {
    if (position == 0) {
        return head.Next;
    }

    SinglyLinkedListNode current = head;
    while (position - 1 > 0) {
        current = current.Next;
        position--;
    }

    current.Next = current.Next.Next;
    return head;
}

Initial List: 5 -> 10 -> 15 -> 20 -> null

Steps:

1. Traverse to the node at position 0 (5).
2. Skip the node at position 1 by updating 5’s Next to 15.

Updated List: 5 -> 15 -> 20 -> null

5. Reverse a Singly Linked List

Problem: Reverse the order of nodes in the list.

Code:

SinglyLinkedListNode Reverse(SinglyLinkedListNode head) {
    SinglyLinkedListNode prev = null;
    SinglyLinkedListNode current = head;

    while (current != null) {
        SinglyLinkedListNode nextNode = current.Next;
        current.Next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

Initial List: 5 -> 10 -> 15 -> 20 -> null

Steps:

1. Set prev to null and current to 5.
2. For each node:
   • Save the Next node.
   • Reverse the pointer: Set current.Next to prev.
   • Move prev and current forward.

Updated List: 20 -> 15 -> 10 -> 5 -> null

Conclusion

Singly linked lists are simple yet powerful. They allow efficient insertions and deletions compared to arrays but require traversal to access elements. Mastering operations like insertion, deletion, and reversal provides a solid foundation for working with more advanced data structures.

Stay tuned for the next post in this series, where we’ll demystify doubly linked lists!