Linked List
A linked list is one of the simplest data structures there is. It is an array of nodes that are connected via pointers.
Each node in the list contains a value and a pointer to the next node in the list. This behavior allows the linked list to behave as a dynamic array, where the size is not fixed and can be modified even after its creation(unlike traditional static arrays).
The three basic operations a linked list must support are searching, insertion and deletion.
Running times
Insertion:
- Insertion at the beginning: O(1)
- Insertion at the end: O(n) (in worst case, when we have to traverse to the end to insert a new node)
- Insertion at a specific position: O(n) (in worst case, when we have to traverse to the specific position to insert a new node)
Deletion:
- Deletion at the beginning: O(1)
- Deletion at the end: O(n) (in worst case, when we have to traverse to the end to delete a node)
- Deletion at a specific position: O(n) (in worst case, when we have to traverse to the specific position to delete a node)
Search: O(n) (in worst case, when we have to traverse through all the elements in the list to find a specific element)
Implementing a Linked List
1. Creating a linked list
First, let’s create the Node class to represent nodes in the list. As mentioned, each node has a value and a pointer to the next node.
class Node:
def __init__(self, value, next = None) -> None:
self.value = value
self.next = nextNext, the LinkedList class. I will also add the __repr__ method so we can print the items of the list.
class LinkedList:
def __init__(self, head: Node = None):
"""
# Consturctor #1 - Empty Linked List
"""
self.head = head
def __repr__(self):
"""
Print Linked List
"""
items = ''
current_node = self.head
while current_node != None:
items += str(current_node.value) + '-->'
current_node = current_node.next
return f"LinkedList({items[:-3]})"Let’s see how we can create a linked list:
# Creating a linked list
head = Node(2)
head.next = Node(1)
head.next.next = Node(4)
head.next.next.next = Node(3)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
linked_list = LinkedList(head)
# print list
print(linked_list)
# Output:
# LinkedList(2-->1-->4-->3-->5-->6)Next, we can create a second constructor for the class to allow for easier creation of linked lists. Let’s say we want to allow users to create linked lists by passing a list of values. We can do it like this:
class LinkedList:
def __init__(self, head: Node = None):
"""
# Consturctor #1 - Empty Linked List
"""
self.head = head
def __repr__(self):
"""
Print Linked List
"""
items = ''
current_node = self.head
while current_node != None:
items += str(current_node.value) + '-->'
current_node = current_node.next
return f"LinkedList({items[:-3]})"
@classmethod
def generate_list(cls, *args):
"""
Constructor #2 - Generate Linked List from list of values
"""
head = Node(args[0])
current_node = head
for value in args[1:]:
current_node.next = Node(value)
current_node = current_node.next
return cls(head = head)Now we can create a linked list much more easily:
linked_list = LinkedList.generate_list(2,1,4,3,5,6)
print(linked_list)
# Output
# LinkedList(2-->1-->4-->3-->5-->6)2. Searching
Searching a value in a linked list involves traversing through the list until we reach None value(end of list) or we find the node with the value we searched for.
class Node:
def __init__(self, value, next = None) -> None:
self.value = value
self.next = next
class LinkedList:
def __init__(self, head: Node = None):
"""
# Consturctor #1 - Empty Linked List
"""
self.head = head
@classmethod
def generate_list(cls, *args):
"""
Constructor #2 - Generate Linked List from list of values
"""
head = Node(args[0])
current_node = head
for value in args[1:]:
current_node.next = Node(value)
current_node = current_node.next
return cls(head = head)
def __repr__(self):
"""
Print Linked List
"""
items = ''
current_node = self.head
while current_node != None:
items += str(current_node.value) + '-->'
current_node = current_node.next
return f"LinkedList({items[:-3]})"
def index(self, index):
"""
Seach a value in Linked List. Return -1 if not found
Description:
- Iterate through the linked list
- If value is found, return the value
- If value is not found, return -1
"""
current_node = self.head
while current_node != None:
if index == 0:
return current_node.value
else:
index -= 1
current_node = current_node.next
return -1Let’s see an example:
linked_list = LinkedList.generate_list(2,1,4,3,5,6)
print(linked_list.index(2))
# Output:
# 42. Insert
Similar logic as searching. Traverse through the list until we reach the desired index location. Generate a Node and insert it at that location in the list.
Then we need to update the links in the list. The new node will need to point to the next node in the list. And the previous node will need to point to the new node.
class Node:
def __init__(self, value, next = None) -> None:
self.value = value
self.next = next
class LinkedList:
def __init__(self, head: Node = None):
"""
# Consturctor #1 - Empty Linked List
"""
self.head = head
@classmethod
def generate_list(cls, *args):
"""
Constructor #2 - Generate Linked List from list of values
"""
head = Node(args[0])
current_node = head
for value in args[1:]:
current_node.next = Node(value)
current_node = current_node.next
return cls(head = head)
def __repr__(self):
"""
Print Linked List
"""
items = ''
current_node = self.head
while current_node != None:
items += str(current_node.value) + '-->'
current_node = current_node.next
return f"LinkedList({items[:-3]})"
def index(self, index):
"""
Seach a value in Linked List. Return -1 if not found
Description:
- Iterate through the linked list
- If value is found, return the value
- If value is not found, return -1
"""
current_node = self.head
while current_node != None:
if index == 0:
return current_node.value
else:
index -= 1
current_node = current_node.next
return -1
def insert(self, value, index):
"""
Insert a value at a given index
"""
if len(self) < index:
print("Index not in Range")
return None
current_node = self.head
while current_node != None:
if index == 1:
next = current_node.next
current_node.next = Node(value)
current_node.next.next = next
return
else:
index -= 1
current_node = current_node.next
def __len__(self):
"""
Return the length of the linked list
"""
current_node = self.head
counter = 0
while current_node != None:
counter += 1
current_node = current_node.next
return counterLet’s see an example:
# Creating a linked list
linked_list = LinkedList.generate_list(2,1,4,3,5,6)
# Inserting a value
linked_list.insert(value=20, index=2)
# Print list
print(linked_list)
# Output:
# LinkedList(2-->1-->20-->4-->3-->5-->6)3. Delete
To delete a node we need to find the node and then delete it. Then we need to update the pointers of the previous and next nodes to point to each other.
class Node:
def __init__(self, value, next = None) -> None:
self.value = value
self.next = next
class LinkedList:
def __init__(self, head: Node = None):
"""
# Consturctor #1 - Empty Linked List
"""
self.head = head
@classmethod
def generate_list(cls, *args):
"""
Constructor #2 - Generate Linked List from list of values
"""
head = Node(args[0])
current_node = head
for value in args[1:]:
current_node.next = Node(value)
current_node = current_node.next
return cls(head = head)
def __repr__(self):
"""
Print Linked List
"""
items = ''
current_node = self.head
while current_node != None:
items += str(current_node.value) + '-->'
current_node = current_node.next
return f"LinkedList({items[:-3]})"
def index(self, index):
"""
Seach a value in Linked List. Return -1 if not found
Description:
- Iterate through the linked list
- If value is found, return the value
- If value is not found, return -1
"""
current_node = self.head
while current_node != None:
if index == 0:
return current_node.value
else:
index -= 1
current_node = current_node.next
return -1
def insert(self, value, index):
"""
Insert a value at a given index
"""
if len(self) < index:
print("Index not in Range")
return None
current_node = self.head
while current_node != None:
if index == 1:
next = current_node.next
current_node.next = Node(value)
current_node.next.next = next
return
else:
index -= 1
current_node = current_node.next
def delete(self, index):
"""
Delete a node at specifc index
"""
current_node = self.head
while current_node != None:
if index == 1:
current_node.next = current_node.next.next
break
else:
index -= 1
current_node = current_node.next
def __len__(self):
"""
Return the length of the linked list
"""
current_node = self.head
counter = 0
while current_node != None:
counter += 1
current_node = current_node.next
return counterLet’s see an example:
# Creating a linked list
linked_list = LinkedList.generate_list(2,1,4,3,5,6)
# Delete the node at index 2
linked_list.delete(index=2)
# Print list
print(linked_list)
# Output:
# LinkedList(2-->1-->3-->5-->6)Note that this implementation is the basic form of a linked list, we can and should customize it to suit our needs. Also, Python has two built-in data structures that can behave as a linked list, they are Lists and collections.deque. In most cases, we would be better of using these two data structures.
If there’s no need for special customization, we should opt to use these built-in data structures first. Linked lists are more useful in languages like C that have static arrays. However, knowing how to implement this data structure can be useful in particular situations and will add to your understanding of how other data structures are built and behave.
