Module 18. Linked Lists
Learning Objectives
- Understand the concept of linked lists and their importance in data structures.
- Implement a basic singly linked list in Python, including creating nodes and linking them together.
- Demonstrate how to perform basic operations on a singly linked list, such as insertion, deletion, and traversal.
- Explore the concept of a doubly linked list and its advantages over a singly linked list.
- Implement a doubly linked list in Python, including maintaining backward and forward pointers.
- Understand the concept of a circular linked list and its applications.
- Implement a circular linked list in Python, including handling traversal and insertion/deletion operations.
1. Linked Lists
A linked list is composed of nodes, where each node contains an element, and each node is connected to its next neighbor.
The figure above shows that there are three nodes in the linked list.
And a node can be defined as below:
class Node:
def __init__(self, element):
self.elmenet = element
self.next = None
The variable head denotes the first node in the list, while the variable tail denotes the last node in the list. If the list is empty, both head and tail are set to None.
- How it works?
When a list is empty, both the head and tail variables point to None.
In order to add nodes into a list, first of all create the first node:
The head variable points to Node 1, and similarly, the tail variable also points to Node 1.
head = Node("Atlanta")
tail = head
Next, create the second node and add it to the list.
Node 2 is succeeded by Node 1, updating the next pointer of Node 1 and the tail as follows: The next pointer of Node 1 now directs to Node 2, and likewise, the tail variable also points to Node 2.
tail.next = Node("Macon")
tail = tail.next
Next, create the third node and add it to the list.
Node 3 is followed by Node 2, updating the next pointer of Node 2 and the tail as follows: The next pointer of Node 2 now points to Node 3, and similarly, the tail variable also points to Node 3.
tail.next = Node("Dallas")
tail = tail.next
To traverse elements in the list, you can follow these steps:
- Start from the head of the list.
- Access the element of the current node.
- Move to the next node using the next
- Repeat steps 2 and 3 until you reach a node where the next pointer is None, indicating the end of the list.
current = head
while current != None:
print(current.elmenet)
current = current.next
- Basic operations of a linked List
- addFirst: Add a node to the head of the list
- addLast: Add a node to the tail of the list
- insert: Add a node at the specified index
- removeFirst: Remove the first node in the list
- removeLast: Remove the last node in the list
- removeAt: Remove the node at the specified index
- Method Implementation
- addFirst
When adding a node to the current list at the first position, please follow this procedure:
Initially, generate a new node, for instance, the "Chicago" node.
newNode = Node(e)
Insert the new node, "Chicago", at the beginning of the list before the first node, "Atlanta".
newNode.next = self.__head
The head variable is updated to point from the "Atlanta" node to the "Chicago" node.
self.__head = newNode
If the new node is added to an empty list, then it becomes the only node in the list.
if self.__tail == None:
self.__tail = self.__head
- addLast
When adding a node to the current list at the last position, please follow this procedure:
Initially, generate a new node, for instance, the "Chicago" node.
newNode = Node(e)
If the new node is added to an empty list, then it becomes the only node in the list.
if self.__tail == None:
self.__head = self.__tail = newNode
Otherwise, insert the new node, "Chicago", after the last node, "Dallas".
self.__tail.next = newNode
And then, update the tail variable to point from the node "Dallas" to the new node "Chicago".
self.__tail = self.__tail.next
- insert(index, e)
When inserting a node to the current list at the specified index, please follow this procedure:
An index of 0 indicates that the new node is added to the first position in the list.
if index == 0:
self.addFirst(e) # Insert first
If the index is greater than or equal to the number of nodes in the list, it indicates that the new node is added to the last position in the list.
elif index >= self.__size:
self.addLast(e) # Insert last
When inserting a new node in the middle of the list, declare a variable, current, and point it to the head node.
current = self.__head
Iterate through the nodes using a loop while moving to the previous node until the desired index is reached.
for i in range(1, index):
current = current.next
And declare a variable, temp and point it to the next node of the current node.
temp = current.next
Link the new node, “Chicago” to the current.next node.
current.next = Node(e)
Finally, link the next node of the current.next to the temp, “Dallas” node.
(current.next).next = temp
- removeFirst
When removing the first node in the current list, please follow this procedure:
If the list is empty, then return None which means nothing to remove.
if self.__size == 0:
return None
If the list is not empty, declare a temporary variable, temp and assign it to the first node.
temp = self.__head
Move the head from the “Chicago” node to the “Atlanta” node.
self.__head = self.__head.next
Return temp.element, “Chicago”.
Once the first node is removed, if the head variable points to None, indicating an empty list, then the tail variable should also be set to None.
if self.__head == None:
self.__tail = None
- removeLast
When removing the last node in the current list, please follow this procedure:
If the list is empty, then return None which means nothing to remove.
if self.__size == 0:
return None
If there is only one node in the list, declare a temporary variable, temp and assign it to the first node.
temp = self.__head
Then assign None to both the head and tail variables.
self.__head = self.__tail = None
If there are multiple nodes in the list, declare a variable named current and point it to the head node.
current = self.__head
Then iterate through the nodes using a loop, while moving to the previous node of the target node to be removed.
for i in range(self.__size - 2):
current = current.next
Declare a temporary variable named temp and assign it to the last node, which is "Dallas".
temp = self.__tail
Set the current node, "Macon", as the tail, and assign None to the tail 's next pointer (tail.next).
self.__tail = current
self.__tail.next = None
Finally, return temp.element, “Dallas”.
- removeAt(index)
When removing a node in the current list at the specified index, please follow this procedure:
If the index is out of range of the list, return None.
if index < 0 or index >= self.__size:
return None
If the index is 0, it indicates that the first node is to be removed.
elif index == 0:
return self.removeFirst()
If the index indicates the last node, remove the last node.
elif index == self.__size - 1:
return self.removeLast()
Otherwise, declare a temporary variable named previous and assign it to the head node, which is "Chicago".
Iterate through the nodes using a loop, while moving to the previous node of the target node to be removed.
Declare a temporary variable named current and assign it to the target node to be removed, which is "Macon".
Connect the previous.next to current.next.
Finally, return current.element, “Macon”.
- Linked List Implementation
class LinkedList:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def getFirst(self):
if self.__size == 0:
return None
else:
return self.__head.element
def getLast(self):
if self.__size == 0:
return None
else:
return self.__tail.element
def addFirst(self, e):
newNode = Node(e)
newNode.next = self.__head
self.__head = newNode
self.__size += 1
if self.__tail == None:
self.__tail = self.__head
def addLast(self, e):
newNode = Node(e)
if self.__tail == None:
self.__head = self.__tail = newNode
else:
self.__tail.next = newNode
self.__tail = self.__tail.next
self.__size += 1
def insert(self, index, e):
if index == 0:
self.addFirst(e)
elif index >= self.__size:
self.addLast(e)
else:
current = self.__head
for i in range(1, index):
current = current.next
temp = current.next
current.next = Node(e)
(current.next).next = temp
self.__size += 1
def removeFirst(self):
if self.__size == 0:
return None
else:
temp = self.__head
self.__head = self.__head.next
self.__size -= 1
if self.__head == None:
self.__tail = None
return temp.element
def removeLast(self):
if self.__size == 0:
return None
elif self.__size == 1:
temp = self.__head
self.__head = self.__tail = None
self.__size = 0
return temp.element
else:
current = self.__head
for i in range(self.__size - 2):
current = current.next
temp = self.__tail
self.__tail = current
self.__tail.next = None
self.__size -= 1
return temp.element
def removeAt(self, index):
if index < 0 or index >= self.__size:
return None
elif index == 0:
return self.removeFirst()
elif index == self.__size - 1:
return self.removeLast()
else:
previous = self.__head
for i in range(1, index):
previous = previous.next
current = previous.next
previous.next = current.next
self.__size -= 1
return current.element
def isEmpty(self):
return self.__size == 0
def getSize(self):
return self.__size
def __str__(self):
result = "["
current = self.__head
for i in range(self.__size):
result += str(current.element)
current = current.next
if current != None:
result += ", "
else:
result += "]"
return result
def clear(self):
self.__head = self.__tail = None
def __iter__(self):
return LinkedListIterator(self.__head)
# The Node class
class Node:
def __init__(self, e):
self.element = e
self.next = None
class LinkedListIterator:
def __init__(self, head):
self.current = head
def __next__(self):
if self.current == None:
raise StopIteration
else:
element = self.current.element
self.current = self.current.next
return element
(Test Program)
from LinkedList import LinkedList
city = LinkedList()
# Add nodes to the list
city.add("Atlanta")
print("(1)", city)
city.insert(0, "Chicago")
print("(2)", city)
city.add("Macon")
print("(3)", city)
city.addLast("Dallas")
print("(4)", city)
city.insert(2, "New York")
print("(5)", city)
city.insert(5, "Boston")
print("(6)", city)
city.insert(0, "LA")
print("(7)", city)
# Remove nodes from the list
city.removeAt(0)
print("(8)", city)
city.removeAt(2)
print("(9)", city)
city.removeAt(city.getSize() - 1)
print("(10)", city)
(Output)
(1) [Atlanta]
(2) [Chicago, Atlanta]
(3) [Chicago, Atlanta, Macon]
(4) [Chicago, Atlanta, Macon, Dallas]
(5) [Chicago, Atlanta, New York, Macon, Dallas]
(6) [Chicago, Atlanta, New York, Macon, Dallas, Boston]
(7) [LA, Chicago, Atlanta, New York, Macon, Dallas, Boston]
(8) [Chicago, Atlanta, New York, Macon, Dallas, Boston]
(9) [Chicago, Atlanta, Macon, Dallas, Boston]
(10) [Chicago, Atlanta, Macon, Dallas]
2. Circular Linked Lists
A circular linked list is a variant of a linked list where the first and last nodes are interconnected, creating a loop or circle within the list structure.
The next node of the last node is indicating to the first node.
- Circular Linked List Implementation
class CircularLinkedList:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def getFirst(self):
if self.__size == 0:
return None
else:
return self.__head.element
def getLast(self):
if self.__size == 0:
return None
else:
return self.__tail.element
def addFirst(self, e):
newNode = Node(e)
if self.__size == 0:
self.__head = self.__tail = newNode
self.__tail.next = self.__head
else:
newNode.next = self.__head
self.__head = newNode
self.__tail.next = self.__head
self.__size += 1
def addLast(self, e):
newNode = Node(e)
if self.__size == 0:
self.__head = self.__tail = newNode
self.__tail.next = self.__head
else:
self.__tail.next = newNode
self.__tail = newNode
self.__tail.next = self.__head
self.__size += 1
def insert(self, index, e):
if index == 0:
self.addFirst(e)
elif index >= self.__size:
self.addLast(e)
else:
current = self.__head
for i in range(1, index):
current = current.next
newNode = Node(e)
newNode.next = current.next
current.next = newNode
self.__size += 1
def removeFirst(self):
if self.__size == 0:
return None
else:
temp = self.__head
self.__head = self.__head.next
self.__tail.next = self.__head
self.__size -= 1
if self.__size == 0:
self.__tail = None
return temp.element
def removeLast(self):
if self.__size == 0:
return None
elif self.__size == 1:
temp = self.__head
self.__head = self.__tail = None
self.__size = 0
return temp.element
else:
current = self.__head
for i in range(self.__size - 2):
current = current.next
temp = self.__tail
self.__tail = current
self.__tail.next = self.__head
self.__size -= 1
return temp.element
def removeAt(self, index):
if index < 0 or index >= self.__size:
return None
elif index == 0:
return self.removeFirst()
elif index == self.__size - 1:
return self.removeLast()
else:
previous = self.__head
for i in range(1, index):
previous = previous.next
current = previous.next
previous.next = current.next
self.__size -= 1
return current.element
def isEmpty(self):
return self.__size == 0
def getSize(self):
return self.__size
def __str__(self):
result = "["
current = self.__head
for i in range(self.__size):
result += str(current.element)
current = current.next
if current != self.__head:
result += ", "
else:
result += "]"
return result
def clear(self):
self.__head = self.__tail = None
self.__size = 0
def __iter__(self):
return CircularLinkedListIterator(self.__head)
# The Node class
class Node:
def __init__(self, e):
self.element = e
self.next = None
class CircularLinkedListIterator:
def __init__(self, head):
self.current = head
def __next__(self):
if self.current is None:
raise StopIteration
else:
element = self.current.element
self.current = self.current.next
return element
3. Doubly Linked Lists
A doubly linked list consists of nodes equipped with two pointers: one pointing to the next node and the other pointing to the previous node. These pointers are commonly referred to as the forward pointer and the backward pointer, respectively. As a result, traversal of a doubly linked list can be performed both forward and backward.
- Doubly Linked List Implementation
class DoublyLinkedList:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def getFirst(self):
if self.__size == 0:
return None
else:
return self.__head.element
def getLast(self):
if self.__size == 0:
return None
else:
return self.__tail.element
def addFirst(self, e):
newNode = Node(e)
newNode.next = self.__head
newNode.prev = None
if self.__head:
self.__head.prev = newNode
self.__head = newNode
if self.__tail is None:
self.__tail = newNode
self.__size += 1
def addLast(self, e):
newNode = Node(e)
newNode.prev = self.__tail
newNode.next = None
if self.__tail:
self.__tail.next = newNode
self.__tail = newNode
if self.__head is None:
self.__head = newNode
self.__size += 1
def insert(self, index, e):
if index == 0:
self.addFirst(e)
elif index >= self.__size:
self.addLast(e)
else:
current = self.__head
for i in range(1, index):
current = current.next
newNode = Node(e)
newNode.next = current.next
newNode.prev = current
current.next.prev = newNode
current.next = newNode
self.__size += 1
def removeFirst(self):
if self.__size == 0:
return None
else:
temp = self.__head
self.__head = self.__head.next
if self.__head:
self.__head.prev = None
self.__size -= 1
if self.__head is None:
self.__tail = None
return temp.element
def removeLast(self):
if self.__size == 0:
return None
elif self.__size == 1:
temp = self.__head
self.__head = self.__tail = None
self.__size = 0
return temp.element
else:
temp = self.__tail
self.__tail = self.__tail.prev
self.__tail.next = None
self.__size -= 1
return temp.element
def removeAt(self, index):
if index < 0 or index >= self.__size:
return None
elif index == 0:
return self.removeFirst()
elif index == self.__size - 1:
return self.removeLast()
else:
current = self.__head
for i in range(index):
current = current.next
temp = current
current.prev.next = current.next
current.next.prev = current.prev
self.__size -= 1
return temp.element
def isEmpty(self):
return self.__size == 0
def getSize(self):
return self.__size
def __str__(self):
result = "["
current = self.__head
while current:
result += str(current.element)
current = current.next
if current:
result += ", "
else:
result += "]"
return result
def clear(self):
self.__head = self.__tail = None
def __iter__(self):
return LinkedListIterator(self.__head)
# The modified Node class
class Node:
def __init__(self, e):
self.element = e
self.next = None
self.prev = None
class LinkedListIterator:
def __init__(self, head):
self.current = head
def __next__(self):
if self.current is None:
raise StopIteration
else:
element = self.current.element
self.current = self.current.next
return element
Summary
- A linked list is a fundamental data structure used in computer science to store and manage collections of elements. Unlike arrays, which store elements in contiguous memory locations, linked lists consist of nodes, each containing a data element and a reference (or pointer) to the next node in the sequence.
- This arrangement allows for dynamic memory allocation and efficient insertion and deletion operations, as nodes can be easily added or removed without requiring contiguous memory blocks.
- Linked lists come in various forms, including singly linked lists, doubly linked lists, and circular linked lists. In a singly linked list, each node has a reference to the next node in the sequence, while in a doubly linked list, each node has references to both the next and previous nodes. Circular linked lists form a closed loop where the last node points back to the first node.
Programming Exercises
Exercise 1: Reverse a Linked List
Write a function to reverse a singly linked list in place. Ensure that the original structure of the list is modified.
Exercise 2: Remove Nth Node From End of List
Write a function to remove the nth node from the end of a linked list and return its head.
Exercise 3: Find the Middle of a Linked List
Write a function to find the middle node of a singly linked list. If the list contains an even number of nodes, return the second middle node.
Exercise 4: Remove Nth Node From End of List
Write a function to remove the nth node from the end of a singly linked list and return the head of the modified list. Assume n is always valid and does not exceed the length of the list.
Exercise 5: Merge Two Sorted Linked Lists
Write a method to merge two sorted singly linked lists into a single sorted linked list.