Chainlink: Implementing LinkedLists In Python.

Photo from Pinterest

Linked lists, according to Wikipedia are a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes that together represent a sequence. In this article, I will be explaining how this data structure works and how to implement it using the python programming language.

PREREQUISITES

Knowledge of Python’s Functional and Object-Oriented concepts.

Python has its inbuilt data structures such as lists, tuples, sets, dictionaries, and an array module which could suit all our data needs. So why use a linked list?. Linked lists are more efficient data structures such that inserting elements is easier, faster and require fewer resources and memory.

Linked lists store data in memory non-contiguously (in random memory locations) unlike the previously mentioned standard data types which store data contiguously (data is stored in one place) thereby increasing the speed and efficiency of programs.

Linked Lists are made of nodes, every node contains two sub-elements, the data to be contained and a memory address to the next node which is used as a reference to access the next element on the list. A collection of nodes make up the linked list. Every linked list has the head which is the first node set to None or Null when the linked list is created. It's all about data and pointers

Photo from Wikipedia

TYPES OF LINKED LISTS

• Singly Linked list.
• Doubly Linked list.

Singly-linked lists are unidirectional (we can only move in one direction which is from the head node to the tail). The singly-linked list contains only one pointer which is the memory location of the next node, the doubly-linked list whose nodes contain two pointers that reference the previous and next node. There are other types of linked lists such as the circular linked list and the Doubly Circular Linked list which are variations of the singly and doubly-linked lists.

IMPLEMENTATION OF THE LINKED LIST DATA STRUCTURE IN PYTHON

Since linked lists are not part of the standard library, we have to import or create them.

Linked lists are implemented in the deque object of the collections module which we import as thus

from collections import deque

The deque object takes in the elements as input the same way we pass in elements to a list but first, we have to create an instance of the object.

Linked_list = deque([‘1’, ’2', ’3', ’4', ’5'])

Possible operations on the deque object and its uses are as follows.

Summary of Operations on the deque Object

Inserting an element into our linked_list would be thus;

>>> linked_list.append('6')
deque(['1', '2', '3', '4', '5', '6'])

Where the new element is inserted at the end.

CREATING A CUSTOM LINKED LIST

Creating custom data structures and algorithms are good practices as they give us a grasp of what’s going on underneath the hood of these libraries and modules. Creating a linked list is quite easy, and in this article, we will be going through creating a linked list with the operations of adding elements deleting elements, finding elements, and deriving the size of the linked list.

First, we create a node class and then a linked list class

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0 #keeping track of the size

The Node class contains the data and the pointer to the next variable which is set to None. The LinkedListclass is used to perform operations on the nodes contains the initialization of the head node.

Now that we have created the LinkedList and Nodeclasses, we move forward to creating methods for operations on the linked list in the LinkedList class.

1. ADDING ELEMENTS TO OUR LINKED LIST

Operations go into the LinkedList class as methods

def add_data(self,data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    new_node.next = self.head
    self.head = new_node
    self.size += 1   #increasing the size attribute 

The add_node_elements method checks for a head node, if there is, it appends a new element to the end (tail) of the linked list by traversing through the linked list, finding the tail node (the node that points to None), and then becoming the next node after it. If there is no head node, it sets the new node to become the head node.

2. PRINTING OUT THE LINKED LIST.

We just created our data structure, We definitely need to output the elements contained and so we create a function for that.

def print_list(self):
    at = self.head
    while at is not None:
        print (at.data, "->", end=" ")
        at = at.next
        break

What this function does is simple. It checks that the head node is not None which signifies an empty linked list and then, goes on to print every element by looping through the linked list.

3. FINDING ELEMENTS IN THE LINKED LIST

Finding Elements are pivotal in data operations and here’s a simple way to implement that in our linked list.

def search(self, seeking):
    at = self.head
    while at is not None:
        if at.data == seeking:
            print("Data Found")
            break
        at = at.next
    else:
        print("Not found")

Starting from the head node using the at variable, we simply loop through all the elements using the while-else loop.

4. REMOVING AN ELEMENT OFF THE LINKED LIST

There are three possible play-outs here. If the data we seek to delete is the head node, we simply set the head node to None. If not, then we use a while else loop to iterate while seeking to match the value we want to delete. When we find the element we want to delete, then we set the node to be the next using the loop down until it becomes the tail node and then becomes None.

def delete_node(self,value):
    at = self.head
    if at.data == value:
        at = None
    while at.data is not value:
        at = at.next
    else:
        if at.data is None:
            print("Empty")
        at.data = at.next.data
        at.next = at.next.next
        self.size -= 1 #Decreasing the size attribute

If the data doesn’t exist, we output Empty to imply we didn’t find the value [line 9].

5. THE LENGTH OF THE CUSTOM LINKED LIST

def get_size(self):
    return self.size

Right from when I instantiated the LinkedListclass, I created a size attribute self.size , and then, in the add_data and delete_node methods, I incremented and decremented the size respectively. The get_size method simply returns the size attribute.

Photo from Reddit

Seems like we’ve gone from the head to the tail of this list 🤣. If you found this interesting, I’ll be writing more on data structures in Python and Javascript so, keep up with this space.