Linked Lists

---

In computer science, a linked list is a linear data structure used to store a collection of elements, called nodes, where each node points to the next one. Linked lists are a fundamental data structure that provides efficient insertion and deletion operations compared to arrays.

---

What is a Linked List?

A linked list is a linear collection of nodes, where each node contains two parts:

1. Data: The actual value or data being stored.
2. Next: A reference (or link) to the next node in the list.

In a linked list, the elements are not stored in contiguous memory locations like arrays. Instead, each element is dynamically allocated, and each node points to the next node in the list.

The key advantage of linked lists over arrays is that they allow for dynamic memory allocation. Linked lists can easily grow or shrink in size, unlike arrays that have a fixed size once they are created.

---

Types of Linked Lists

There are several variations of linked lists, each serving a different purpose. Let's explore the most common types:

1. Singly Linked List

In a singly linked list, each node contains a data field and a reference to the next node in the sequence. The last node in the list has a reference (or link) to null (or None in Python), indicating the end of the list.

Structure:

• Node: Contains data and a reference to the next node.
• Head: Points to the first node in the list.

2. Doubly Linked List

A doubly linked list is an extension of the singly linked list where each node contains two references:

1. A reference to the next node.
2. A reference to the previous node.

This allows traversal in both directions, making it more versatile than a singly linked list.

Structure:

• Node: Contains data, reference to the next node, and reference to the previous node.
• Head: Points to the first node.
• Tail: Points to the last node.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop. There are two types:

1. Singly Circular Linked List: The last node points to the first node and the previous node has no reference.
2. Doubly Circular Linked List: The last node points to the first node, and the first node points to the last node as well, with both forward and backward references.

---

Basic Operations on Linked Lists

The following operations are commonly performed on linked lists:

1. Insertion:

   • At the beginning: Add a new node at the start of the list.
   • At the end: Add a new node at the end of the list.
   • At a specific position: Insert a node at any given position in the list.

2. Deletion:

   • At the beginning: Remove the first node of the list.
   • At the end: Remove the last node.
   • At a specific position: Delete a node at a specified index.

3. Traversal: Traverse the list and print all the elements.

4. Search: Find a node by value.

---

Advantages of Linked Lists

• Dynamic Size: Unlike arrays, linked lists do not need a predefined size. The list can grow or shrink as needed.
• Efficient Insertions/Deletions: Adding or removing elements (especially at the beginning or in the middle) is more efficient than in arrays since there is no need to shift elements.
• Memory Efficiency: Linked lists use memory efficiently since they allocate memory as needed rather than pre-allocating a fixed amount of memory.

---

Disadvantages of Linked Lists

• Extra Memory: Each node in a linked list requires additional memory to store the reference to the next (and possibly previous) node.
• Sequential Access: Linked lists do not allow direct access to elements by index, unlike arrays. Traversing the list takes time.
• Complexity: Operations such as searching for an element or accessing a specific index take longer compared to arrays.

---

Sample Code: Implementing a Singly Linked List

Let's implement a basic singly linked list in Python. This implementation will include methods for insertion, deletion, and traversal.

Code for Singly Linked List:

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 insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    # Delete a node by value
    def delete_node(self, key):
        temp = self.head

        # If the node to be deleted is the head node
        if temp and temp.data == key:
            self.head = temp.next
            temp = None
            return

        # Search for the node to be deleted
        prev = None
        while temp and temp.data != key:
            prev = temp
            temp = temp.next

        # If the node was not found
        if not temp:
            return

        # Unlink the node from the linked list
        prev.next = temp.next
        temp = None

    # Traverse the list and print all elements
    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage
ll = LinkedList()
ll.insert_at_beginning(10)
ll.insert_at_beginning(20)
ll.insert_at_end(30)
ll.insert_at_end(40)

print("Linked List:")
ll.traverse()  # Output: 20 -> 10 -> 30 -> 40 -> None

ll.delete_node(10)
print("After Deletion:")
ll.traverse()  # Output: 20 -> 30 -> 40 -> None

---

Sample Code: Implementing a Doubly Linked List

Here’s a simple implementation of a doubly linked list in Python, which supports both forward and backward traversal.

Code for Doubly Linked List:

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

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

    # Insert at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        if self.head:
            self.head.prev = new_node
        new_node.next = self.head
        self.head = new_node

    # Insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node

    # Traverse forward
    def traverse_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    # Traverse backward
    def traverse_backward(self):
        current = self.head
        while current and current.next:
            current = current.next
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_beginning(20)
dll.insert_at_end(30)
dll.insert_at_end(40)

print("Doubly Linked List (Forward Traversal):")
dll.traverse_forward()  # Output: 20 <-> 10 <-> 30 <-> 40 <-> None

print("Doubly Linked List (Backward Traversal):")
dll.traverse_backward()  # Output: 40 <-> 30 <-> 10 <-> 20 <-> None

 

---

---