Linked lists are the very foundation of a lot of data structures in software development. So, before we start our discussion of linked lists, let’s try to come back and better understand what an array actually is.
An array is a data structure that holds a fixed size of elements in contiguous memory locations. Since they are fixed, you can’t increase an array’s size.
As an example, let us assume we have an array x that can hold up to 5 elements.
x = [1, 2, 3, 4, 5]
We can’t add the value 6 to this array if we wanted to, since the array is limited to only 5 elements. If we wanted to add a 6, we’d have to resize the array to hold at least 6 elements, then finally set the 6th element in the array equal to 6.
Typically on a Python list or Java’s ArrayList, once you reach some capacity of an array, Python or Java will automatically create a new array of a bigger size, copy all of the elements from the old array into the new one, then return the new array with the bigger size.
For example, let’s use the same example as before with the array x holding the values 1, 2, 3, 4, and 5.
x = [1, 2, 3, 4, 5]
We can’t add 6 to it, so if we append() to the list, Python will create a new array, copy all of the values from the old array into the new array, then finally add 6 to the array.
x = [1, 2, 3, 4, 5] x.append(6) # Under the hood, let's assume Python creates a new array that's twice the size of array x. # So, let's assume the new array's size will now be 10. # Let's assume this new array is initialized with None values. # So, it'd be [None, None, None, None, None, None, None, None, None, None] # Then it'll loop through the old array, and set the values from the old array to the new array. # So, it becomes: # [1, 2, 3, 4, 5, None, None, None, None, None] # Now, we also want to append 6, so it finds the next free spot in the array and sets it equal to 6. # [1, 2, 3, 4, 5, 6, None, None, None, None]
So, as our list gets bigger and bigger, there’ll be a lot of overhead with the program creating new arrays, copying all the values to the new array, and then finally adding the element.
Note how there’s also no guarantee that the array will be fully used. So, if we don’t fully use an array, we are essentially wasting space (since the array allocates the memory regardless of whether we use it or not).
So, this is where linked lists come into play.
A linked list works with nodes which are objects that contain a value and a pointer to another node.
So, a node contains some form of data and a link to the next node.
Node Implementation
Here’s a very basic implementation of a Node class in Python.
class Node:
def __init__(self, value):
self.value = value
self.next = None
def get_value(self):
return self.value
def set_value(self, value):
self.value = value
def set_next(self, reference):
self.next = reference
def get_next(self):
return self.next
The getters and setters are not important, so we’ll just focus on self.value and self.next. Essentially, self.value holds the data itself, and self.next holds a reference to the next node.
Now, a linked list is just a a chunk of nodes connected to each other. Say, our first node is 6 and is connected to another node with a value of 5. Then that node with a value of 5 is connected to another node with a value of 4. And finally that node with a value of 4 is connected to nothing, indicating that this is the end of the linked list.
Visually, it’d look something like: [6] -> [5] -> [4] -> Nothing.
Pretty straightforward, right? Let’s try implementing it.
Double Ended Linked List Implementation
The simplest linked list implementation only has a head pointer; however, we’ll implement a double-ended linked list, so it’s a bit more efficient to add items from the end. Don’t worry, it’s not much different. We will just have an additional tail pointer.
In this implementation of a linked list, we’ll have the functions:
- getSize() – returns the size of the linked list.
- isEmpty() – returns True if the linked list is empty or False if it is not empty.
- getFirst() – get the value of the first node from the linked list (if it is not empty).
- getLast() get the value of the last item from the linked list (if it is not empty).
- clear() – clear the linked list.
- print() – print out a visual representation of the linked list.
- addleft(arg) – to add something with a value of arg to the beginning of the linked list.
- addright(arg) – to add something with a value of arg to the end of the linked list.
- popleft() – to pop and return the first element from a linked list (if it is not empty).
- popright() – to pop and return the last element from a linked list (if it is not empty).
- remove(arg) – to remove a specific node with a value of arg (if it exists).
- search(arg) – to check if an item exists in the linked list.
- reverse() – to reverse the linked list.
Here’s our initial class so far.
class LinkedList:
def __init__(self):
self.head = None # This is the initial node.
self.tail = None # This will be the last node.
self.size = 0 # This will keep track of the size of the linked list.
We have a reference to the head, the tail, and a variable that keeps track of the size of the linked list.
Let’s now implement the functions getSize() and isEmpty().
def getSize(self): # Returns the size of the linked list.
return self.size
def isEmpty(self): # Checks if the size of the linked list is 0.
return self.size == 0
Pretty self-explanatory. They just check the variable that keeps track of the size of the linked list.
Now, let’s implement the functions getFirst() and getLast().
def getFirst(self): # Returns the value of the first node.
if self.head:
return self.head.value
def getLast(self): # Returns the value of the tail node.
if self.tail:
return self.tail.value
Still pretty basic. They both check whether the head and tail references are existent or not. If they exist, they return the value. If they don’t, they return None. (By default, all functions return None in Python).
How about implementing clear() next?
def clear(self): # Clear the linked list.
self.head = None
self.tail = None
self.size = 0
It just sets the head and tail pointers equal to None, and then it sets the variable size equal to 0.
Let’s move forward with print().
def print(self): # Print out a visual representation of the linked list.
print("[", end="") # Print '[' initially.
node = self.head # Set initial node equal to the head of the linked list.
while node: # Iterate through the node until it is empty.
if node.next: # If there is a next pointer, print a comma.
print(node.value, end=", ")
else: # If there is no next pointer, don't print a comma.
print(node.value, end="")
node = node.next # Set the node equal to its next node.
print("]") # Print the closing ']'.
The comments should make the code pretty self explanatory, but basically, we have a node that iterates through the entire linked list and prints out the nodes’ values. If that node has a next pointer that is also a node, it prints a comma; if its next pointer is null or None, then it doesn’t print a comma.
Now, let’s implement addLeft() and addRight().
def addLeft(self, value): # Add to the front of the linked list.
node = Node(value) # Create the new node.
node.next = self.head # Set this node's next reference to the current head.
self.head = node # Re-reference the current head to this new node.
if not self.tail: # If the tail doesn't exist, let's set the tail equal to the head.
self.tail = self.head
self.size += 1 # Increment the size by 1.
def addRight(self, value): # Add to the tail of the linked list.
node = Node(value) # Create the new node.
if self.tail: # If the tail exists, set the next of the current tail to the new node.
self.tail.next = node # Setting the next reference of the tail to the new node.
self.tail = node # Re-reference the tail node to the new node we just created.
else: # If the tail doesn't exist, set the tail equal to the node.
self.tail = node
if not self.head: # If the head doesn't exist, let's set the head equal to the tail.
self.head = self.tail
self.size += 1 # Increment the size of the linked list by 1.
The function addRight() adds a value to the end of the linked list and reassigns the tail pointer; the function addLeft() adds a value to the beginning of the linked list and modifies the head pointer.
Moving on, let’s implement popLeft() and popRight().
def popLeft(self):
if self.head: # Check if the head pointer is not None.
temp = self.head # Get a temporary pointer to the head node.
self.head = self.head.next # Re-assign head to equal the head's next value.
self.size -= 1 # Decrement the value of the linked list by 1.
if not self.head: # If the head is now null, set the tail to be null as well.
self.tail = None
return temp.value # Return the value of the previous head node.
def popRight(self):
if self.head: # Check if the head pointer is not None
temp = self.head # Get a temporary pointer to the head node.
if not self.head.next: # If there's only one node in our linked list, then remove head and tail pointers.
self.head = None # Reset head to None.
self.tail = None # Reset tail to None.
self.size = 0 # Reset the size back to 0.
return temp.value # Return the value of the node we just got rid of.
while temp: # While the temporary node is available, iterate through its next pointer.
# If temp has a next pointer, but that node doesn't have a next pointer, then set tail to temp.
if temp.next and not temp.next.next: # If the next node's next doesn't exist, then we reached the end.
value = temp.next.value # Value of the node to be removed.
self.tail = temp # Set the tail equal to the temp node.
temp.next = None # Set the value of the node's next to None.
self.size -= 1 # Decrement the value of the linked list by 1.
return value # Return the value of the node that we have removed.
temp = temp.next # Iterate to the next reference of the node.
With the code for popLeft(), we delete the elements from the front of the linked list. We check if the head exists, and if it does, we set the head equal to the previous head’s next pointer. We then finally return the previous head’s value and decrement the linked list’s size by 1.
With the code for popRight(), we delete the tail node. However, we can’t just delete the tail node, because we need to remove the tail node reference from its previous node. We don’t have access to that. So, we iterate through the head pointer until we reach a node where its next pointer has a next pointer where it is equal to null or None. Once we reach that pointer, we set it equal to the tail and decrement the linked list size by 1.
Next, let’s implement search(). This takes in an argument of what we want to find.
def search(self, value): # Let's try searching for a value in a linked list.
node = self.head # Let's set an initial pointer to the head.
while node: # Now, let's loop over the node until the reference doesn't exist or is null.
if node.value == value: # If the value of the node is the value, then the values exists in our linked list.
return True # Return true as the value exists.
node = node.next # If we don't find the value, let's check the next node that this node points to.
return False # We have exhausted our linked list, so this value doesn't exist in the linked list.
Pretty basic stuff. Set a temporary node equal to self.head, then traverse through that node and check if a node’s value is equal to the one passed in the function. If the value matches, then return True. If, however, no value matches throughout the entire traversal, then we know the value doesn’t exist; so, in that case, we return False.
Now, finally, let’s implement remove(). This takes in an argument of what we want to remove.
def remove(self, value): # Remove and return a node from a linked list. This will remove one instance if exists.
node = self.head # Set node equal to self.head to begin the traversal.
if node: # Check if the node is not None. If it is None, that means the linked list is empty.
if node.value == value: # If the first node is the value, then just pop from the beginning.
return self.popLeft()
while node: # While node exists, iterate through.
if node.next and node.next.value == value: # If the next pointer's value is our value, then remove it.
temp = node.next # Keep a temporary reference to return it later.
node.next = node.next.next # Set the next of our node to the next node's next.
if node.next is None: # If the node.next doesn't exist, then reassign self.tail to node.
self.tail = node
self.size -= 1 # Decrement size by 1.
return temp.value # Return the removed value.
node = node.next # Iterate through the node.
This is the same as search(), but it removes the node, if found, by removing that reference from the node that refers to it. The node that refers to it then has its next pointer point to the removed node’s next pointer.
Finally, let’s implement reverse().
def reverse(self): # Reverse a linked list.
node = self.head # We will iterate using this node.
previous = None # What the next of this node will now refer to.
while node: # Iterate through the node.
temp = node.next # Save a temporary variable to node's next pointer. We'll iterate over to it later.
node.next = previous # Set the next of this node to previous.
previous = node # Now, set the previous to the current node.
node = temp # Set node to temp (which we assigned to node.next) to continue iteration.
self.tail = self.head # Finally, set the tail equal to the head.
self.head = previous # Set the head equal to previous.
We have our initial node equal to self.head and previous referring to None.
Basically, the algorithm is:
- Iterate through the nodes until a node has None as its next pointer.
- Save a temporary variable that is equal to the next pointer of the current node.
- Set the next pointer of the current node equal to previous.
- Change the reference of previous to the current node (we’ll set the next node’s next to this).
- Finally, continue the iteration by setting node equal to the temporary variable that equals the next pointer of the current node.
Then once the loop is exhausted, we just modify self.tail to equal self.head (as they’re now reversed), and we modify self.head to equal previous (as we have reversed through them). This is a commonly asked question on interviews, so it’d be a good idea to get an intuitive idea of how this algorithm works.
And that should be about it for the functions of the linked list. Here’s the full code:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def get_value(self):
return self.value
def set_value(self, value):
self.value = value
def set_next(self, reference):
self.next = reference
def get_next(self):
return self.next
class LinkedList:
def __init__(self):
self.head = None # This is the initial node.
self.tail = None # This will be the last node.
self.size = 0 # This will keep track of the size of the linked list.
def getSize(self): # Returns the size of the linked list.
return self.size
def isEmpty(self): # Checks if the size of the linked list is 0.
return self.size == 0
def getFirst(self): # Returns the value of the first node.
if self.head:
return self.head.value
def getLast(self): # Returns the value of the tail node.
if self.tail:
return self.tail.value
def clear(self): # Clear the linked list.
self.head = None
self.tail = None
self.size = 0
def print(self): # Print out a visual representation of the linked list.
print("[", end="") # Print '[' initially.
node = self.head # Set initial node equal to the head of the linked list.
while node: # Iterate through the node until it is empty.
if node.next: # If there is a next pointer, print a comma.
print(node.value, end=", ")
else: # If there is no next pointer, don't print a comma.
print(node.value, end="")
node = node.next # Set the node equal to its next node.
print("]") # Print the closing ']'.
def addLeft(self, value): # Add to the front of the linked list.
node = Node(value) # Create the new node.
node.next = self.head # Set this node's next reference to the current head.
self.head = node # Re-reference the current head to this new node.
if not self.tail: # If the tail doesn't exist, let's set the tail equal to the head.
self.tail = self.head
self.size += 1 # Increment the size by 1.
def addRight(self, value): # Add to the tail of the linked list.
node = Node(value) # Create the new node.
if self.tail: # If the tail exists, set the next of the current tail to the new node.
self.tail.next = node # Setting the next reference of the tail to the new node.
self.tail = node # Re-reference the tail node to the new node we just created.
else: # If the tail doesn't exist, set the tail equal to the node.
self.tail = node
if not self.head: # If the head doesn't exist, let's set the head equal to the tail.
self.head = self.tail
self.size += 1 # Increment the size of the linked list by 1.
def popLeft(self):
if self.head: # Check if the head pointer is not None.
temp = self.head # Get a temporary pointer to the head node.
self.head = self.head.next # Re-assign head to equal the head's next value.
self.size -= 1 # Decrement the value of the linked list by 1.
if not self.head: # If the head is now null, set the tail to be null as well.
self.tail = None
return temp.value # Return the value of the previous head node.
def popRight(self):
if self.head: # Check if the head pointer is not None
temp = self.head # Get a temporary pointer to the head node.
if not self.head.next: # If there's only one node in our linked list, then remove head and tail pointers.
self.head = None # Reset head to None.
self.tail = None # Reset tail to None.
self.size = 0 # Reset the size back to 0.
return temp.value # Return the value of the node we just got rid of.
while temp: # While the temporary node is available, iterate through its next pointer.
# If temp has a next pointer, but that node doesn't have a next pointer, then set tail to temp.
if temp.next and not temp.next.next: # If the next node's next doesn't exist, then we reached the end.
value = temp.next.value # Value of the node to be removed.
self.tail = temp # Set the tail equal to the temp node.
temp.next = None # Set the value of the node's next to None.
self.size -= 1 # Decrement the value of the linked list by 1.
return value # Return the value of the node that we have removed.
temp = temp.next # Iterate to the next reference of the node.
def search(self, value): # Let's try searching for a value in a linked list.
node = self.head # Let's set an initial pointer to the head.
while node: # Now, let's loop over the node until the reference doesn't exist or is null.
if node.value == value: # If the value of the node is the value, then the values exists in our linked list.
return True # Return true as the value exists.
node = node.next # If we don't find the value, let's check the next node that this node points to.
return False # We have exhausted our node, so this value doesn't exist in the linked list.
def remove(self, value): # Remove and return a node from a linked list. This will remove one instance if exists.
node = self.head # Set node equal to self.head to begin the traversal.
if node: # Check if the node is not None. If it is None, that means the linked list is empty.
if node.value == value: # If the first node is the value, then just pop from the beginning.
return self.popLeft()
while node: # While node exists, iterate through.
if node.next and node.next.value == value: # If the next pointer's value is our value, then remove it.
temp = node.next # Keep a temporary reference to return it later.
node.next = node.next.next # Set the next of our node to the next node's next.
if node.next is None: # If the node.next doesn't exist, then reassign self.tail to node.
self.tail = node
self.size -= 1 # Decrement size by 1.
return temp.value # Return the removed value.
node = node.next # Iterate through the node.
def reverse(self): # Reverse a linked list.
node = self.head # We will iterate using this node.
previous = None # What the next of this node will now refer to.
while node: # Iterate through the node.
temp = node.next # Save a temporary variable to node's next pointer. We'll iterate over to it later.
node.next = previous # Set the next of this node to previous.
previous = node # Now, set the previous to the current node.
node = temp # Set node to temp (which we assigned to node.next) to continue iteration.
self.tail = self.head # Finally, set the tail equal to the head.
self.head = previous # Set the head equal to previous.
Whew, that was fun to make. Going back to the topic of arrays vs linked lists, linked lists are preferred when you’re working with a lot of data insertions and removals from the front or end points of the data. The operation is very fast as you just have to modify front or end pointers.
However, in terms of searching, modifying, or retrieving data, linked lists can be slow as you’d have to iterate through all the nodes in the worst case to find, modify, or remove the value.
So, if you’re working with data that seldom grows or shrinks in size and has a lot of data modification or lookups, choose an array. Editing the existing data on an array is instantaneous, as you just modify the indices’ values on an array. Lookups are also instantaneous (provided you know the index).
However, if you’re working with data that has a lot of insertions and deletions from the end or front, choose a linked list.
In the end, they’re both tools that you’ll need in your arsenal to be a good software developer. So, it’d be a good idea to gain a thorough understanding of how they work in order to know which data structure to use for a specific problem.
If you made it this far, thank you for reading. As always, if you have any questions, feel free to let me know down in the comments below.
One reply on “Linked Lists”
This is so nicely written. It’s easy to understand and super informative. Great research man