Working with the concepts we've studied can actually be quite enjoyable once we understand them. And there's nothing quite as satisfying as feeling confident in our knowledge. So, why not let our minds dive into LinkedList and see what we can accomplish?
What is a LinkedList?
A linked list is a linear data structure comprised of a group of objects, with each object referred to as a node. These nodes contain a value and a memory address for the next node in the sequence.
In a linked list, the elements are not stored next to each other in memory like in a standard list or array. Instead, each node has the memory address of the next node, and to access an item, you need to walk through each node one by one. If there is no next node, then the value is set to null.
Creating a Linked List
The underlying type is a Node and a linked list contains a collection of them, let's define a Node type first
class Node:
def __init__(self, val):
self.val = val
self.next = None
def set_next(self, node):
self.next = node
# printing a node will provide it's value
def __repr__(self):
return self.val
def main():
first_name = Node("spike")
last_name = Node("speigel")
first_name.set_next(last_name)
print(first_name)
print(last_name)
# print full name
print(f"{first_name} {last_name}")
main()
Output:
spike
speigel
spike speigel
Now that we have a Node type, let's create a linked list and iterate through to print the values of it
yield keyword
While we are iterating through the list we need to print the value of each node, that happens when we return the node, but using return would break the loop
And that's when the yield keyword comes in, it resumes the function call where it left off after returning the value
let's see that in action
class LinkedList:
def __init__(self):
self.head = None
def __iter__(self):
node = self.head
# my method first version
#while node.next != None:
# yield node
# node = node.next
# if node.next == None:
# yield node
# return
# optimized method
while node != None:
yield node
node = node.next
# setting the list head to the node linked to other node and so on
def add_to_tail(self, node):
self.head = node
def __repr__(self):
values = []
# underlying implementation of this loop is the __iter__ method of linkedlist class
for node in self:
values.append(node.val)
return " -> ".join(values)
class Node:
def __init__(self, val):
self.val = val
self.next = None
def set_next(self, node):
self.next = node
# printing a node will provide it's value
def __repr__(self):
return self.val
def main():
node0 = Node("spike")
node1 = Node("julia")
node2 = Node("vicious")
node3 = Node("faye")
node0.set_next(node1)
node1.set_next(node2)
node2.set_next(node3)
linked_list = LinkedList()
linked_list.add_to_tail(node0)
print(linked_list)
main()
output:
spike -> julia -> vicious -> faye
The first solution I came up with for iterating through a linked list wasn't the most optimized one, I was checking the next node's value while being on the current node and I didn't have to since the value of the node is being set to its next one on current iteration itself
And at the next iteration, the condition will be checked, if the node is null the loop breaks, I hope that clears it
Adding a new tail to the linked list
Previously, we created a linked list where it's add_to_tail the method takes a node that already represents a linked list and the nodes are linearly set using the set_next method
But the optimal way to do so is to add a new node to the existing data structure and not present a pre-set version
So we iterate through the linked list if we have a node whose next value is null then we set it to the new node
class LinkedList:
def add_to_tail(self, node):
if self.head == None:
self.head = node
return
current_node = self.head
while True:
if current_node.next == None:
current_node.set_next(node)
return
current_node = current_node.next
def main():
node0 = Node("spike")
node1 = Node("julia")
node2 = Node("vicious")
node3 = Node("faye")
node0.set_next(node1)
node1.set_next(node2)
node2.set_next(node3)
linked_list = LinkedList()
linked_list.add_to_tail(node0)
print(linked_list)
linked_list.add_to_tail(Node("jet"))
print(linked_list)
linked_list.add_to_tail(Node("ed"))
print(linked_list)
main()
# Output:
spike -> julia -> vicious -> faye
spike -> julia -> vicious -> faye -> jet
spike -> julia -> vicious -> faye -> jet -> ed
Adding a new head to the linked list
Let's see how we can do this, and why we are pushing elements to the end and beginning of linked lists will make more sense shortly
add_to_head takes a node as input and sets the next value to the current head and the current head will be set to the new node
def add_to_head(self, node):
if self.head == None:
self.head = node
# node.next = self.head or
node.set_next(self.head)
self.head = node
def main():
node0 = Node("spike")
node1 = Node("julia")
node2 = Node("vicious")
node3 = Node("faye")
node0.set_next(node1)
node1.set_next(node2)
node2.set_next(node3)
linked_list = LinkedList()
linked_list.add_to_tail(node0)
print(linked_list)
linked_list.add_to_tail(Node("jet"))
print(linked_list)
linked_list.add_to_head(Node("akira"))
print(linked_list)
main()
# Output:
spike -> julia -> vicious -> faye
spike -> julia -> vicious -> faye -> jet
akira -> spike -> julia -> vicious -> faye -> jet
Linked List is better suited for implementing queue(FIFO - first in first out) data structure, for the reason, the nodes of it are spread across memory and one just needs to swap around pointers to add/remove and has constant time O(1)
While adding/removing an element at the beginning or at the end of the list has constant time O(1), performing the same operation at a specific position requires shifting the elements of the list on either side
as the position nears the beginning or end since elements of a list are stored as a contiguous sequence in the memory, the time complexity of its execution also nears O(n)
One still needs to traverse the linked list to get to a specific element but it has constant time to add/remove an element at any position in the list for that reason in some cases it's preferred over the normal list like implementing stack and queues
O(1) pushes to a linked list
So far, the current linked list can have O(1) pushes and pops at the head, we need to do that for the tail, as of now we traverse through the linked list to get to the end of it instead, we can keep track of it each time a new node is added by setting the tail pointer to the new node, that way we know where the last node exists in the linked list
# creating a new data member in the class constructor self.tail and setting it to None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def add_to_head(self, node):
if self.head == None:
self.head = node
# initially both will point to same object, tail's value will be changed as the new ones are added
self.tail = node
node.set_next(self.head)
self.head = node
def add_to_tail(self, node):
if self.head == None:
self.head = node
self.tail = node
return
# the current node the tail is pointing to its next value is Null/None
# we set that to new node
self.tail.next = node
# now we change the tail pointer to the new node, this way we don't have to iterate as we are keeping track of the last element with the help of tail data member
self.tail = node
# Note that this a small part of the code where the changes are made, you can find full code on previous code snippets
def main():
node0 = Node("spike")
node1 = Node("julia")
node2 = Node("vicious")
node3 = Node("faye")
nodes = [node0, node1, node2, node3]
linked_list = LinkedList()
for node in nodes:
linked_list.add_to_tail(node)
print(linked_list)
main()
# Output:
spike -> julia -> vicious -> faye
End thoughts
I'm really glad we had the chance to go through this together. Hopefully, you now have a firm understanding of how to implement basic applications using linked lists.
Also, this is something I learned from boot.dev, I'd recommend you to check that out, it's good.
Happy Learning and I'll see you in the next one