Many developers run away from data structures and algorithms because of how difficult it is perceived to be. In this article, I will try my best to make you understand one of the data structures called Linked List.
Linked List is a non-contiguous data structure, and a collection of nodes in which each node consists of a data and a reference or pointer to the next node. The first node is called Head while the last node is called Tail with its next node pointing to None.
There are not too many places where you can utilize a linked list, but as a good developer, it is important to get a good grasp of it to enable you understand how data structures are created along with the different operations that are performed on them.
In this article, we will be using the python programming language to create a Linked List with various operations that can be performed on it such as reading, modification, and deletion.
- You need to create a Node class with a data and next_node properties.
# A Node class.
class Node:
data = None
next_node = None
# Initializes this class with a data argument whenever an object is created
def __init__(self, data):
self.data = data
# Provides a more readable string representation of the class object
def __repr__(self):
return "<Node Data: %s>" %self.data
The init method is python's built-in method called anytime an instance of the Node class is created.
The repr method is a python built-in method that gives the liberty to produce a more readable representation of the Node class. You can test your code using the python interpreter.
To access the interpreter, you need to have python installed on your PC. You download it from here
Open your terminal, and type in the below code and click enter.
python -i <the name of your file>
Make sure you are on the directory where your code file is located.
The interpreter will open, and you can go ahead to test your code, like the example below.
$ python -i linked_list.py
>>> N1 = Node(20)
>>> N1
<Node Data: 20>
>>>
- Create a LinkedList class and set head to None
# A Linked list class
class LinkedList:
# Initializes class whenever an instance is created
def __init__(self):
self.head = None
We will start creating the different operations that can be carried out on a Linked List. After the init method, let's start by creating an add method that will add a node to the beginning of the List.
# Adds a node to the start of a list
def add(self, data):
new = Node(data)
new.next_node = self.head
self.head = new
# Adds a node to the end of a list and returns its new size
def addToEnd(self, data):
current = self.head
new = Node(data)
count = 0
added = False
if current is None:
self.head = new
else:
while current and not added:
count += 1
if current.next_node is None:
current.next_node = new
added = True
else:
current = current.next_node
return count + 1
implementation on python's interpreter
$ python -i linked_list.py
>>> l = LinkedList()
>>> l.add(2)
>>> l.add(5)
>>> l.add(3)
>>> l
[HEAD: 3]-->[5]-->[TAIL: 2]
>>>
From the above example, you will notice a chain-like representation of the class instance. Like the Node class, it is created using the python's built-in repr method. see code below
# Provides a more readable string representation of the class instance
def __repr__(self):
nodes = []
current = self.head
while current:
if current is self.head:
nodes.append("[HEAD: %s]" %current.data)
elif current.next_node is None:
nodes.append("[TAIL: %s]" %current.data)
else:
nodes.append("[%s]" %current.data)
current = current.next_node
return "-->".join(nodes)
Next, is an insert method which creates and inserts a node at a specified index argument.
# Adds a node at a specified index in the list.
def insert(self, data, index):
current = self.head
if index == 0:
self.add(data)
else:
new = Node(data)
while index > 1:
index -= 1
current = current.next_node
prev = current
next_node = current.next_node
prev.next_node = new
new.next_node = next_node
Testing with interpreter.
$ python -i linked_list.py
>>> l = LinkedList()
>>> l.add(2)
>>> l.add(5)
>>> l.add(12)
>>> l.add(6)
>>> l
[HEAD: 6]-->[12]-->[5]-->[TAIL: 2]
>>> l.insert(88, 1)
>>> l
[HEAD: 6]-->[88]-->[12]-->[5]-->[TAIL: 2]
>>>
Now, let's add a method that will return the length of the list
# Counts and returns the total number of nodes in a list by traversing through it
def size(self):
count = 0
current = self.head
while current:
count += 1
current = current.next_node
return count
You can test it using the interpreter following the way we did earlier.
Next, let's add a method that deletes a node from the list
# Traverses through the list and removes the first node which data corresponds to a given or specified argument.
# It returns the removed node.
def remove(self, key):
current = self.head
prev = None
found = False
while current and not found:
if current.data == key and current is self.head:
found =True
self.head = current.next_node
elif current.data == key:
found = True
prev.next_node = current.next_node
else:
prev = current
current = current.next_node
return current
# Removes a node at a specified index from the list. It returns the removed node.
def removeAtIndex(self, index):
current = self.head
prev = None
if index == 0:
self.head = current.next_node
else:
while index > 0:
index -= 1
prev = current
current = current.next_node
prev.next_node = current.next_node
return current
Go back, study and practice the code as many times as you can so as to enable you get a good grasp of Linked List and its common operations.
Congratulations for adding the knowledge of Linked List to your skillset.
Happy coding...
Top comments (0)