Linked List in plain english
Chidozie C. Okafor
Posted on April 13, 2022
Linked List: What are they?
Before we dive into a linked list, let's look at an array and list to find out what they are.
List/Array:
If you are going to the mall to get things for an occasion, you might probably want to make a list of all the item you need. If you are like me, the reason might be that you do not want to be thinking about those things anytime you get to the mall, so the list will hold all the items that you can easily look at, line to line so to remember them, you might probably want to number them (index) so as to get (lookup) the item in order you wrote them (insert). You might even cross (delete) the item anytime you add it to your shopping cart.
This is the basics that gave an array it's definition as: a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number. contiguous means that you can find all the elements of an array in the same memory location.
The Problem:
what is the problem here, the problem here is that in an array, you have the predefine the size of the array and allocate memory to it, that means if you have any other element to insert, it will be nearly impossible, except if you just create a new array with a much bigger size and copy the existing array into it, in order to have a space for extra elements.
Golang tried solving this issues by introducing dynamic array known as slice, python go as far as not only having a list which grows and shrink at will, but allows you to insert elements of different types in one list.
Let's see an array in code:
#python list
my_list = ['milk', 'coffee', 'honey', 4, 6, 2, 4.6]
#check if an item exists
print('milk' in my_list)
#True
#add to a list
my_list.append('tea')
This is how list is used in python. Let's take a look at array in golang.
package main
import "fmt"
func main() {
// Creating an array of string type
// Using var keyword
var myarr[3]string
// Elements are assigned using index
myarr[0] = "milk"
myarr[1] = "honey"
myarr[2] = "coffee"
// Accessing the elements of the array
// Using index value
fmt.Println("Elements of Array:")
fmt.Println("Element 1: ", myarr[0])
fmt.Println("Element 2: ", myarr[1])
fmt.Println("Element 3: ", myarr[2])
}
Now if we want to add more element to this array we will run into issues, because looking at it, we have reach our full capacity of size 3.
The solution:
Though both insertion, and lookup of a sorted array with known index will have a constant time operation O(1). But if the arrays grows more and keep copying things around, you might likely run into issues, That is why we try to look at a much better way of storing and retrieving our items. Linklist partially solve this issues but introduces a whole new problem which we will talk about later. Deletion and resizing an array is usually O(n) because it requires element shifting.
How To Link a list:
If all the element of an array is stored in one memory location, linked list said that instead of storing all these elements in one memory location with fixed size, why not we store each element separately and give each one a pointer to the next element, so that each element will keep a track of each other.
In a linked list, you don't need to sort the element, as you having nothing to do with the index, you simply ask the memory if it holds the element you are looking for, and if it says no, you use the pointer to locate the next memory and ask similar question till you get to the point were the element is pointing to null or None.
Let's see it in action:
from typing import Any
from dataclasses import dataclass
@dataclass
class Node:
"""
Node class
I love keeping a track of both the next and previous node,
in other words called doubly linked list.
"""
data: Any
next: 'Node' = None
prev: 'Node' = None
def __str__(self):
return str(self.data)
@dataclass
class LinkedList:
"""
Linked List Class
"""
head: Node = None
tail: Node = None
def __str__(self):
"""
print linked list
"""
if self.head is None:
return "Empty Linked List"
else:
return f"Linked List: {self.head} -> {self.tail} has {self.size()} nodes"
def __iter__(self):
"""
iterate over linked list
"""
current = self.head
while current is not None:
yield current
current = current.next
def size(self):
"""
return size of linked list
"""
if self.head is None:
return 0
current = self.head
count = 0
while current is not None:
count += 1
current = current.next
return count
def is_empty(self):
"""
check if linked list is empty
"""
return self.head is None
def add_first(self, data):
"""
add node to the beginning of the linked list
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def add_last(self, data):
"""
add node to the end of the linked list
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def add_at(self, index, data):
"""
add node at a specific index
"""
if index == 0:
self.add_first(data)
elif index == self.size():
self.add_last(data)
else:
new_node = Node(data)
current = self.head
count = 0
while current is not None:
if count == index:
new_node.next = current.next
current.next.prev = new_node
new_node.prev = current
current.next = new_node
break
current = current.next
count += 1
def remove_first(self):
"""
remove first node
"""
if self.head is None:
return None
else:
self.head = self.head.next
if self.head is None:
self.tail = None
else:
self.head.prev = None
def remove_last(self):
"""
remove last node
"""
if self.head is None:
return None
else:
self.tail = self.tail.prev
if self.tail is None:
self.head = None
else:
self.tail.next = None
def remove_at(self, index):
"""
remove node at a specific index
"""
if index == 0:
self.remove_first()
elif index == self.size() - 1:
self.remove_last()
else:
current = self.head
count = 0
while current is not None:
if count == index:
current.prev.next = current.next
current.next.prev = current.prev
break
current = current.next
count += 1
def insert_values(self, values):
"""
insert values into linked list
"""
for value in values:
self.add_last(value)
def print_ll(self):
"""
print linked list
"""
if self.head is None:
print("Empty Linked List")
else:
current = self.head
while current is not None:
print(current, end="--> ")
current = current.next
# print()
def reverse_ll(self):
"""
reverse linked list
"""
if self.head is None:
return None
else:
current = self.head
while current is not None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
self.head = current.prev
if __name__ == "__main__":
ll = LinkedList()
ll.add_first(1)
ll.add_first(2)
ll.add_first(3)
ll.add_last(4)
ll.add_last(5)
ll.add_at(2, 6)
ll.insert_values([7, 8, 9])
ll.print_ll()
print("\n")
print(ll)
"""
if you run this code you will get.
3--> 2--> 1--> 6--> 4--> 5--> 7--> 8--> 9-->
Linked List: 3 -> 9 has 9 nodes
"""
Let's look the code and explain what happens here
- Data contains the value to be stored in the node.
- Next contains a reference to the next node on the list
- Prev contains a reference to the previous node on the list
This is known as the head of an array, if you want to insert any other array, you simply use this pointer that is currently pointing to null and point it to the next array and then the next array points to another and so on, if there no next node, then the last element must point to None or null value.
If we are keeping track of both the head and tail (double linked list) it will look like this.
If you look very well, we have solved the this issues with array that have fixed size.
Linked lists serve a variety of purposes in the real world. They can be used to implement (spoiler alert!) queues or stacks as well as graphs. They’re also useful for much more complex tasks, such as lifecycle management for an operating system application.
Operations in linked List:
How to Traverse a Linked List
One of the most common things you will do with a linked list is to traverse it. Traversing means going through every single node, starting with the head of the linked list and ending on the node that has a next value of None.
Traversing is just a fancier way to say iterating. So, with that in mind, create an iter to add the same behavior to linked lists that you would expect from a normal list:
def __iter__(self):
"""
iterate over linked list
"""
current = self.head
while current is not None:
yield current
current = current.next
The method above goes through the list and yields every single node. The most important thing to remember about this iter is that you need to always validate that the current node is not None. When that condition is True, it means you’ve reached the end of your linked list.
After yielding the current node, you want to move to the next node on the list. That’s why you add node = node.next. Here’s an example of traversing a random list and printing each node:
How to Insert a New Node
There are different ways to insert new nodes into a linked list, each with its own implementation and level of complexity. That’s why you’ll see them split into specific methods for inserting at the beginning, end, or between nodes of a list.
Inserting at the Beginning
Inserting a new node at the beginning of a list is probably the most straightforward insertion since you don’t have to traverse the whole list to do it. It’s all about creating a new node and then pointing the head of the list to it.
def add_first(self, data):
"""
add node to the beginning of the linked list
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
In the above example, you’re setting self.head as the next reference of the new node so that the new node points to the old self.head. After that, you need to state that the new head of the list is the inserted node.
Inserting at the End
Inserting a new node at the end of the list forces you to traverse the whole linked list first and to add the new node when you reach the end. You can’t just append to the end as you would with a normal list because in a linked list you don’t know which node is last.
def add_last(self, data):
"""
add node to the end of the linked list
"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
Inserting Between Two Nodes
Inserting between two nodes adds yet another layer of complexity to the linked list’s already complex insertions because there are two different approaches that you can use:
Inserting after an existing node
Inserting before an existing node
It might seem weird to split these into two methods, but linked lists behave differently than normal lists, and you need a different implementation for each case.
def add_at(self, index, data):
"""
add node at a specific index
"""
if index == 0:
self.add_first(data)
elif index == self.size():
self.add_last(data)
else:
new_node = Node(data)
current = self.head
count = 0
while current is not None:
if count == index:
new_node.next = current.next
current.next.prev = new_node
new_node.prev = current
current.next = new_node
break
current = current.next
count += 1
In the above code, you’re traversing the linked list looking for the node with data indicating where you want to insert a new node. When you find the node you’re looking for, you’ll insert the new node immediately after it and rewire the next reference to maintain the consistency of the list.
How to Remove a Node
To remove a node from a linked list, you first need to traverse the list until you find the node you want to remove. Once you find the target, you want to link its previous and next nodes. This re-linking is what removes the target node from the list.
That means you need to keep track of the previous node as you traverse the list. Have a look at an example implementation:
def remove_first(self):
"""
remove first node
"""
if self.head is None:
return None
else:
self.head = self.head.next
if self.head is None:
self.tail = None
else:
self.head.prev = None
def remove_last(self):
"""
remove last node
"""
if self.head is None:
return None
else:
self.tail = self.tail.prev
if self.tail is None:
self.head = None
else:
self.tail.next = None
def remove_at(self, index):
"""
remove node at a specific index
"""
if index == 0:
self.remove_first()
elif index == self.size() - 1:
self.remove_last()
else:
current = self.head
count = 0
while current is not None:
if count == index:
current.prev.next = current.next
current.next.prev = current.prev
break
current = current.next
count += 1
In the above code, we use the size to our advantage. remove_first try to remove the first node of a linked list.
remove_last try to remove the last node, remove_at, uses the index you want and remove it from the list. you first check that your list is not empty. If it is, you can raise an exception or return None. After that, you check if the node to be removed is the current head of the list . If it is, then you want the next node in the list to become the new head.
If none of the above happens, then you start traversing the list looking for the node to be removed . If you find it, then you need to update its previous node to point to its next node, automatically removing the found node from the list. Finally, if you traverse the whole list without finding the node to be removed, then you raise an exception.
Notice how in the above code you use previous_node to keep track of the, well, previous node. Doing so ensures that the whole process will be much more straightforward when you find the right node to be deleted.
Performance Comparison: Lists vs Linked Lists
In most programming languages, there are clear differences in the way linked lists and arrays are stored in memory. In Python, however, lists are dynamic arrays. That means that the memory usage of both lists and linked lists is very similar.
Insertion and Deletion of Elements
In Python, you can insert elements into a list using .insert() or .append(). For removing elements from a list, you can use their counterparts: .remove() and .pop().
The main difference between these methods is that you use .insert() and .remove() to insert or remove elements at a specific position in a list, but you use .append() and .pop() only to insert or remove elements at the end of a list.
Now, something you need to know about Python lists is that inserting or removing elements that are not at the end of the list requires some element shifting in the background, making the operation more complex in terms of time spent.
With all this in mind, even though inserting elements at the end of a list using .append() or .insert() will have constant time, O(1), when you try inserting an element closer to or at the beginning of the list, the average time complexity will grow along with the size of the list: O(n).
Linked lists, on the other hand, are much more straightforward when it comes to insertion and deletion of elements at the beginning or end of a list, where their time complexity is always constant: O(1).
For this reason, linked lists have a performance advantage over normal lists when implementing a queue (FIFO), in which elements are continuously inserted and removed at the beginning of the list. But they perform similarly to a list when implementing a stack (LIFO), in which elements are inserted and removed at the end of the list.
Retrieval of Elements
When it comes to element lookup, lists perform much better than linked lists. When you know which element you want to access, lists can perform this operation in O(1) time. Trying to do the same with a linked list would take O(n) because you need to traverse the whole list to find the element.
When searching for a specific element, however, both lists and linked lists perform very similarly, with a time complexity of O(n). In both cases, you need to iterate through the entire list to find the element you’re looking for.
Posted on April 13, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related