AlgoBreath

Linked List

1. Components of a Linked List:

  • Node: The fundamental part of a linked list. Each node contains:

    • Data: The value stored in the node.
    • Next: A pointer/reference to the next node in the list.

  • Head: The first node in a linked list.

  • Tail: The last node in a linked list, which points to null, indicating the end of the list.

2. Types of Linked Lists:

  • Singly Linked List: Each node points only to the next node. The last node points to null.
  • Doubly Linked List: Each node has two links: one to the next node and another to the previous node. The first node’s previous link and the last node’s next link point to null.
  • Circular Linked List: Similar to the singly linked list, but the last node points to the head, forming a circle.

3. Operations on Linked Lists:

  • Insertion:

    • At the beginning (head).
    • At the end (tail).
    • After/before a given node.

  • Deletion:

    • Remove the first node.
    • Remove the last node.
    • Remove a specific node.

  • Traversal: Access each element in the sequence.

  • Searching: Find a node with a given value.

  • Updating: Change the value of an existing node.

4. Advantages of Linked Lists:

  • Dynamic Size: Unlike arrays, linked lists don’t have a fixed size. They can grow and shrink during runtime.
  • Ease of Insertion/Deletion: Adding or removing elements doesn’t require shifting other elements, unlike in arrays.

5. Disadvantages of Linked Lists:

  • Memory Usage: Each node requires extra memory for the reference/pointer.
  • Traversal: Direct access is not possible; you have to access nodes sequentially starting from the first node (head).
  • Reverse Traversing: In singly linked lists, it’s not possible to traverse backward. Doubly linked lists solve this problem but use more memory per node.

6. Complexity Analysis:

  • Time Complexity:

    • Access: O(n)
    • Insertion: O(1) if you're at the position, otherwise O(n)
    • Deletion: O(1) with the node, otherwise O(n)

  • Space Complexity: O(n)

7. Applications of Linked Lists:

  • Implementing stacks and queues.
  • Dynamic memory allocation.
  • Implementing other data structures like graphs and trees.

8. Singly Linked List Example in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if not self.head:
            self.head = Node(data)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(data)

    def display(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next

Next