DEV Community

dennis mwangi
dennis mwangi

Posted on

How To Implement Linked List in Python

This is a simple guide to understanding how to implement a linked list in python.

The goal of this article is to enhance your understanding on how singly linked list is implemented in python-simplified.

A linked list is a data structure in computer science that stores a sequence of elements, called nodes, in which each node contains a reference or pointer to the next node in the list. The list is made up of a series of nodes, each of which contains a piece of data and a reference to the next node in the sequence.

Linked lists can be used to implement a variety of data structures, including stacks, queues, and associative arrays. They have several advantages over arrays, including efficient insertion and deletion operations, and the ability to easily grow or shrink the list as needed. However, they have some disadvantages as well, such as slower access time for individual elements and the need for more memory overhead to store the pointers.

There are several types of linked lists, including singly linked lists, doubly linked lists, and circular linked lists, each with its own characteristics and advantages.

How Linked List is Implemented in python

Linked List Image

I believe the best approach to implementing a linked list in python is by using classes and objects. Here is an example:

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

Enter fullscreen mode Exit fullscreen mode

A node class is defined to represent each node in the linked list. This node has two attributes: data which stores the data for that node and the next which stores a reference to the next node.

Again I have another class called the Linkedlist class to represent the linked list itself. This has an attribute head that stores the reference of the first node.

kindly read the comments in the code for better understanding.

class Linkedlist:
    def __init__(self):
        self.head = None

    # this methods returns if the head is empty
    def isempty(self):
        return self.head is None

    # creating my first node
    def firstNode(self,data):
# I create an instance of the class Node(data)
        newNode = Node(data)
# Now I link the refrence of the newNode to head
        newNode.next = self.head
 # Assign head to point to newNode
        self.head = newNode

    def lastNode(self, data):
        newNode = Node(data)
# check to know if the refrence of head is empty
        if self.isempty():
# if the statement is true, then link the node to the head
            newNode.next = self.head
        else:
# otherwise create a newNode
            current = self.head
# current becomes a new instance of head
            while current is not None:
# cycle through when the condition is true
                current = current.next
# Now, i want current to point to a new address reference
            current.next = newNode
# Anytime the current variable points to a new reference, a new Node should be created.
Enter fullscreen mode Exit fullscreen mode

Next, we will be looking at how to remove/pop the first node and then the last node

 def remove_firstNode(self, data):
 # check if head is empty and return Nothing
    if self.isempty():
        return None
    else:
        tmp = self.head
# tmp variable will hold the value of head
        self.head = self.head.next
# head should point to the next address so that we can pop or remove the immediate node
        return tmp

def remove_lastNode(self, data):
    if self.isempty():
        return None
    elif self.head.next is not None:
# check if head is pointing to an address
        tmp = self.head
        self.head = None
# self.head will become None and return the tmp.data value
        return tmp.data
    else:
        current = self.head
        while current.next.next is not None: 
# return true when the statement is valid
            current = current.next
        tmp = current.next
        current.next = None
        return tmp.data
Enter fullscreen mode Exit fullscreen mode

That's it guys! and I hope this has enhanced your understanding of implementing a singly linked list in python. For any correction, kindly reach out to me or comment below.

Also, please do well to like and follow me here for more articles. Cheers!

Top comments (0)