What is a Linked List?
A linked list is a linear data structure where elements (called nodes) are stored in separate memory locations and connected using pointers. Unlike arrays, they don't require contiguous memory.
Each node contains:
- Data (the value to be stored)
- A reference (or pointer) to the next node
Types of Linked Lists
- Singly Linked List: Each node points to the next one.
- Doubly Linked List: Each node has references to both the next and previous nodes.
- Circular Linked List: The last node connects back to the head node.
Why Use Linked Lists?
Linked lists offer dynamic memory allocation. Unlike arrays, you don’t need to define the size in advance, and insertions/deletions are faster when done at the start or middle.
How is a Linked List Different from an Array?
Aspect | Array | Linked List |
---|---|---|
Memory | Contiguous | Non-contiguous |
Insertion/Deletion | Slow (except at end) | Fast (O(1) at head) |
Access Time | O(1) | O(n) |
Creating a Node
class Node:
data
next
This simple structure stores data and points to the next node. When next
is null (or None), it's the last node.
Example: Creating a Linked List
head = Node("A")
head.next = Node("B")
head.next.next = Node("C")
This creates a linked list: A → B → C
Output:
A → B → C → null
Traversing a Linked List
We move from one node to the next until we reach the end.
function traverse(head):
current = head
while current is not null:
print current.data
current = current.next
Output:
A B C
Question:
Why can't we access the 3rd element directly like in an array?
Answer: Because nodes are not stored in order in memory. We must follow each pointer starting from the head until we reach the desired node.
Inserting at the Beginning
function insertAtHead(head, value):
newNode = Node(value)
newNode.next = head
head = newNode
return head
Inserting at head is O(1) – no traversal is needed.
Inserting at the End
function insertAtEnd(head, value):
newNode = Node(value)
if head is null:
return newNode
current = head
while current.next is not null:
current = current.next
current.next = newNode
return head
This operation requires traversal, hence O(n) time complexity.
Deleting a Node by Value
function deleteByValue(head, target):
if head.data == target:
return head.next
current = head
while current.next is not null and current.next.data != target:
current = current.next
if current.next is not null:
current.next = current.next.next
return head
Question:
What happens if the value isn’t in the list?
Answer: The loop exits without finding it, and the original list remains unchanged.
Advantages of Linked Lists
- Efficient memory usage
- Faster insertions/deletions (especially in large datasets)
- No need to define size in advance
Disadvantages
- Slow access (O(n) to reach nth element)
- Extra memory usage for storing pointers
Recap
- Linked Lists use dynamic memory.
- Each node stores data and a reference to the next.
- They are ideal when frequent insertion/deletion is required.