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
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
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.
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
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)