3 min read
Linked Lists and Their Uses
Last Update: 6 October, 2022Linked lists are simple data structures that consist of two main parts. A part that contians the actual data and another for information about the next list item. There are 3 main types of linked lists; singly linked lists, doubly linked lists and circular linked lists that. Usually linked lists have a part that acts as the head, you can choose to end your linked lists with a tail or you can use it empty as well. A simple visual representation for a singly linked list would look something like this:
There are different methods for creating linked lists in different languages. I will create linked lists in python because of the reason that python is really easy to learn and understand.
§We Shall Begin
First of all how do we actually create a linked list? Each item of the linked list is called node. Each node will consist of two of two parts as we said above. One part for the data and another for the address of the next node. This is how I actually created the node:
class Node:
def __init__(self, data):
self.data = data
self.next = None
For the actual linked list we will create another python class. I coded mine so that we need to inform our linked list about the head ourselves. You can code it in a way that it automatically gets the head (and maybe tail node too) from the given nodes.
§Insertion
Like in any structure that resembles a chain, you can break the link any any part to insert a node in constant time. Creating this behaviour in an array / list would potentially take O(N) time. Let's say you have this array:
arr = [4, 5, 1, 6, 2]
Ok now, we want to insert 3 in the second position python arr[1] = 3. By the end of insertion our array / list will look like this:
arr = [4, 3, 5, 1, 6, 2]
In order to achieve this we pushed every item one index to the right and opened up space for the value 3. This is the cause of the O(N) time complexity.
In a linked list achieving the same would be easier as we just need to break the link between two nodes and add a node between with new links. The time complexity of this operation is constant (O(N)). A visual would probably help us understand this better:
Deletion would be also as easy removing the links. We select the previous node of the node we want to remove and make this node point to the node after the node we wanna remove. This way we just skip it in the chain. A visual representation can be found down below:
§Deletion
Deletion in a linked list takes constant time (O(1)) whereas in a list / array it would take linear (O(N)) time. In a list we would be removing the item / value from the list and move every item in the list one index left.
§The Code For Linked List
The full code for the linked list data structure will look something like this. I wrote this code to practice actions on linked lists. You can see that it covers most of the actions you would wanna do in a linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = Node
def is_empty(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("is it empty: ", bool(size == 0))
def front(self):
return self.head.data
def back(self):
temp = self.head
while temp.next is not None:
temp = temp.next
return temp.data
def get_size(self):
size = 0
temp = self.head
while temp:
size += 1
temp = temp.next
print("size is: ", size)
return size
# going one by one printing the values
def print_list(self):
temp = self.head
while temp:
print(temp.data)
temp = temp.next
def value_at(self, index):
temp = self.head
nth = 0
while temp:
if index != nth:
nth += 1
temp = temp.next
else:
print(index, "- nth item value is: ", temp.data)
return
def push_front(self, value):
to_add = Node(value)
temp = self.head
self.head = to_add
to_add.next = temp
def pop_front(self):
self.head = self.head.next
def push_back(self, value):
to_add = Node(value)
temp = self.head
while temp.next:
temp = temp.next
temp.next = to_add
def pop_back(self):
temp = self.head
while temp.next.next is not None:
temp = temp.next
print("removed: ", temp.next.data)
temp.next = None
def insert(self, index, value):
to_insert = Node(value)
temp = self.head
nth = 0
while temp:
if nth == index:
old_temp_next = temp.next
to_insert.next = old_temp_next
temp.next = to_insert
temp = temp.next
nth += 1
# got a little fancy with this one
def erase(self, index):
if index < 0:
print('index can\'t be negative')
if index == 0:
self.pop_front()
nth = 1
prev = self.head
current = self.head.next
while current:
if index == nth:
prev.next = current.next
current.next = None
return
nth += 1
prev = current
current = current.next
print("out of bounds")
# value_n_from_end(n) - returns the value of the node at nth position from the end of the list
# I decided to start the indexing from 0, so zeroth is the last one
def value_n_from_end(self, index):
nth = 1
size = self.get_size()
wanted = size - index
current = self.head
if wanted == 0:
print("wanted data is: ", current.data)
return current.data
while current:
if nth == wanted:
print("returning: ", current.data)
return current.data
current = current.next
nth += 1
# Going with the iterative way of doing this because the space complexity is O(1)
# def reverse(self): # Iterative time O(n), space O(1)
# prev = None
# current = self.head
# while(current):
# next = current.next
# current.next = prev
# prev = current
# current = next
# # print("current", current.data)
# self.head = prev # I forgot about the head for like 10 mins
def reverse(self, node): # recursive time O(n), space O(n)
if node is None:
print("node is:", node.data)
return node
if node.next is None:
print("node is, no next:", node.data)
self.head = node
return node
node1 = self.reverse(node.next) # call recursively until we hit the base
node.next.next = node # points to itself
node.next = None
return node1
# remove_value(value) - removes the first item in the list with this value
def remove_value(self, value):
current = self.head
prev = None
if self.head.data == value:
self.head = self.head.next
while current:
if current.data == value:
prev = current
current = current.next
prev.next = current
prev = current
current = current.next
if __name__ == '__main__':
# initialize with an empty list
s_l_list = LinkedList()
# the first node, gotta define the head
s_l_list.head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(3)
# chain' em up
s_l_list.head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
# s_l_list.print_list()
# s_l_list.get_size()
# s_l_list.is_empty()
# s_l_list.value_at(0)
# s_l_list.value_at(2)
# s_l_list.push_back(5)
# s_l_list.print_list()
# s_l_list.push_back(6)
# s_l_list.print_list()
# s_l_list.pop_back()
# s_l_list.print_list()
# s_l_list.push_front(0)
# s_l_list.print_list()
# s_l_list.pop_front()
# s_l_list.print_list()
# print(s_l_list.front())
# print(s_l_list.back())
# s_l_list.print_list()
# s_l_list.insert(1, 77)
# s_l_list.print_list()
# s_l_list.erase(2)
# s_l_list.print_list()
# s_l_list.value_n_from_end(0)
# s_l_list.reverse() # for the iterative method
# s_l_list.print_list()
# s_l_list.reverse(s_l_list.head) # call the method with the current head
# s_l_list.print_list()
s_l_list.remove_value(1)
s_l_list.print_list()
You can uncomment the commented lines in order to test out different parts and the actions you can do on linked list. Go test it out!
§Conclusion and Uses for Linked Lists
You can consider using linked lists when:
- You need a constant time in insertion and deletion operations on really big datasets.
- You don't really know how many items your array / list is going to contain. In every insertion / deletion to an array, your array is re-created in the memory. This may not seem as a problem when working with languages suchas JavaScript and python since we don't need to actually set a size when we are creating our array / list.
- You need to create a queue like data structures in wich the order matters.
There are many other benefits of course and you wanna go deeper I suggest that your read this article. It's a bit hard to read but I believe after reading my post here you should be able to easily understand that one too.
Keep learning!
Ilker AkbiyikTable of Contents
Related Posts
