In computer science, linked lists are a common linear data structure which consists of nodes connected to each other via pointers. Each node consists of two pieces of data, the data, and the address of the next node that the current node is connected to. Linked lists can be compared to a train, where the first item in the list is the locomotive, and all nodes in the list thereafter are the cars of the train, all connected to each other, starting at the head (the locomotive). Linked lists are similar to arrays in that they are both used for storing data, and can both be iterated through, and are mutable. However, they also each have their differences, and there are advantages to using both in different scenarios.
Why use a Linked List?
One major benefit of a linked list is more efficient use of memory. Unlike arrays which where memory must be preallocated, linked lists can dynamically increase or decrease in size as required by the program. New nodes with pointers can be created or removed at anytime, anywhere in the memory, without requiring a contiguous block of memory that arrays require. This means that arrays may eventually become full and need to be resized for further use, while linked lists can grow in size indefinitely.
However, arrays also have their advantages, particularly when accessing random parts of the array. Arrays are indexed, which allow any part of the array to be accessed directly while linked lists must be iterated through until the requested data is found.
One particular benefit of a linked list is its use in the implementation of other data structures such as stacks and queues. If one were to utilize an array to implement a stack, every push() and pop() operation would require the entire array to be reindexed. This results in a time complexity of O(n). However, push() and pop() operations on a linked list are extremely efficient. A push() operation on a linked list only requires the current head to be set as the second node, and the new node being set as the new head. Similarly, a pop() operation would only require returning the current head of the linked list, setting it to null, and setting the second node as the head.
Now that we’ve discussed the basic uses of a linked list, let’s talk about how we would implement one.
Structure of a Linked List
Linked lists are a collection of nodes, similar to cars in a train that are all linked together. Nodes consist of two parts. The data section which contains the information to be held in the node, and the pointer, which points to the next node in the list. The first item in the linked list is known as the HEAD and is the starting point whenever we traverse the list. The last node in the list will always point to NULL, and is also known as the tail of the linked list.
Implementing a Linked List
When implementing a linked list in Python, we will want to create two classes. The node class and the class for the linked list itself. The node class will contain two pieces of data. The data for the node itself, and the pointer which contains the reference to the next node.
class Node:
def __init__(self, data):
self.data = data
self.next = NoneNext, we can create the class for the Linked List. The first part of the linked list that must be initialized is the head. The head of a linked list is the first node in the list.
class LinkedList:
def __init__(self):
self.head = NoneLinked lists also contain some methods which we will implement below. The methods we will be including are Find, Insert, and Delete.
Find
The find method of a linked list will take in the item to be searched for, traverse through the linked list and check every node until the requested item is found. If the item does not exist in the list, we will notify the user that the item is not in the list. The time complexity of this method is O(n) because the entire list must be traversed to search for the item.
def find(self, item):
current_node = self.head # If head data is equal to request item, return found
if item == self.head.data:
return f"{item} has been found." # Traverse through linked list until matching item is found
while current_node.data != item:
current_node = current_node.next # If current_node results in None, we have reached the end of the linked list without finding the item
if current_node is None:
return f"{item} not found. return f"{item} has been found."
Prepend
The prepend method of a linked list will insert an item to the beginning (head) of the linked list. This involves setting the new item to be inserted as the new head of the linked list, and the former head to become the second item in the linked list.
def prepend(self, item):
# Instantiate the new node with item
new_node = Node(item) # Set new_node's next pointer to point at the current head
new_node.next = self.head # Set new_node to be the new head
self.head = new_node
Insert
The insert method of a linked list will insert the item into the linked list at the requested index. This method will traverse through the linked list to the specified index, then set the previous node to point to the new node, and set the new node to point to the next node. The time complexity of this method is O(n) because the list must be traversed to the specified index before the item can be inserted.
def insert(self, item, index):
new_node = Node(item)
current_node = self.head
previous_node = self.head # Traverse through the linked list to the specified index
for i in range(0, index - 1):
previous_node = current_node
current_node = current_node.next next_node = current_node.next # Set previous node to point to the new node
previous_node.next = new_node # Set the new node to point to the next node
new_node.next = next_node
Delete
The delete method of a linked list will search for the requested item to be deleted in the linked list, then remove it from the list. If the item does not exist, we will notify the user that the item doesn’t exist. The deletion process will be accomplished by keeping track of the previous node and the current node. When the item to be deleted is found, we will set the node that is previous to the node to be deleted to point to the node that comes after the node to be deleted, thus deleting the current node. The time complexity of this method is O(n) because the list must be traversed until the item is found before it can be deleted.
def delete(self, item):
current_node = self.head
previous_node = self.head # Set the head to point to the next node if item to be deleted is the head
if current_node.data == item:
new_head = current_node.next
self.head = new_head # Traverse through the linked list until requested item is found
while current_node.data != item:
previous_node = current_node
current_node = current_node.next if current_node is None:
return f"{item} not found." if current_node.data == item:
next_node = current_node.next
previous_node.next = next_node
return f"Deleted {item} from the linked list."
Conclusion
Linked lists are a fast and efficient data structure that is often used for its speed. They are often used to implement other abstract types such as stacks and queues.
