Introduction to Linked Lists
Welcome to Day 7 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive into the world of linked lists, a fundamental data structure in computer science.
What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes. Each node contains a data field and a reference (or link) to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, the elements are linked using pointers.
Basic Structure of a Linked List
A typical node in a linked list consists of two components:
- Data: The value or payload of the node
- Next: A reference to the next node in the sequence
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
Types of Linked Lists
- Singly Linked List: Each node points to the next node in the sequence.
- 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 on a Linked List
- Insertion: Adding a new node to the list
- Deletion: …
Introduction to Linked Lists
Welcome to Day 7 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive into the world of linked lists, a fundamental data structure in computer science.
What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes. Each node contains a data field and a reference (or link) to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, the elements are linked using pointers.
Basic Structure of a Linked List
A typical node in a linked list consists of two components:
- Data: The value or payload of the node
- Next: A reference to the next node in the sequence
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
Types of Linked Lists
- Singly Linked List: Each node points to the next node in the sequence.
- 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 on a Linked List
- Insertion: Adding a new node to the list
- Deletion: Removing a node from the list
- Traversal: Visiting each node in the list
- Search: Finding a node with a specific value
Example: Simple Singly Linked List Implementation
Let’s implement a basic singly linked list in Python:
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
5
6class LinkedList:
7 def __init__(self):
8 self.head = None
9
10 def append(self, data):
11 new_node = Node(data)
12 if not self.head:
13 self.head = new_node
14 return
15 current = self.head
16 while current.next:
17 current = current.next
18 current.next = new_node
19
20 def display(self):
21 current = self.head
22 while current:
23 print(current.data, end=" -> ")
24 current = current.next
25 print("None")
26
27# Usage
28my_list = LinkedList()
29my_list.append(1)
30my_list.append(2)
31my_list.append(3)
32my_list.display() # Output: 1 -> 2 -> 3 -> None
Advantages of Linked Lists
- Dynamic Size: Linked lists can grow or shrink in size during runtime.
- Efficient Insertion and Deletion: Adding or removing elements at the beginning is O(1).
- Flexible Memory Allocation: Nodes can be stored anywhere in memory.
Disadvantages of Linked Lists
- No Random Access: Accessing an element by index is O(n).
- Extra Memory: Each node requires additional memory for the pointer.
- Not Cache-Friendly: Nodes may be scattered in memory, reducing cache efficiency.
Exercise
- Implement a
prepend
method that adds a new node to the beginning of the linked list. - Write a
search
method that returns True
if a given value exists in the linked list, and False
otherwise. - Implement a
delete
method that removes the first occurrence of a given value from the linked list.
Summary
Linked lists are versatile data structures that offer efficient insertion and deletion operations. Understanding linked lists is crucial for many advanced algorithms and data structures. In the coming days, we’ll explore more complex operations and variations of linked lists.
Tomorrow, we’ll dive deeper into singly linked lists and implement more advanced operations. Stay tuned!