Detailed Notes on Linked Lists in Python
A Linked List is a linear data structure where elements are stored in nodes. Each node contains two
parts: 1. Data: The actual value. 2. Reference (next): A pointer to the next node in the sequence.
Unlike arrays, linked lists are dynamic and allow efficient insertion and deletion of elements.
Types of Linked Lists:
• Singly Linked List - Each node points to the next node and the last node points to None.
• Doubly Linked List - Each node has pointers to both the next and previous nodes.
• Circular Linked List - The last node points back to the first node, forming a circle.
Basic Operations:
• Traversal - Visiting each node in the list.
• Insertion - Adding a new node at the beginning, end, or a specific position.
• Deletion - Removing a node from the list.
• Searching - Finding a node containing a given value.
• Updating - Modifying the value of a node.
Python Implementation Example (Singly Linked List):
class Node: def __init__(self, data): self.data = data self.next = None class
LinkedList: def __init__(self): self.head = None def insert_at_end(self, data):
new_node = Node(data) if self.head is None: self.head = new_node return temp =
self.head while temp.next: temp = temp.next temp.next = new_node def display(self):
temp = self.head while temp: print(temp.data, end=" -> ") temp = temp.next
print("None") # Example usage ll = LinkedList() ll.insert_at_end(10)
ll.insert_at_end(20) ll.insert_at_end(30) ll.display()
Advantages:
• Dynamic size (no need to define size in advance).
• Efficient insertions and deletions (O(1) at head).
Disadvantages:
• Random access is not possible (O(n) time complexity for searching).
• Extra memory required for storing pointers.
• Cache-unfriendly due to scattered memory allocation.
