What is a Single Linked List In Python? And How To Implement It In Python

1: Nodes and Linked Lists

A linked list is a data structure that consists of a chain or sequence of nodes connected in some manner. A node is a relatively smaller data structure that contains
data and one or more links that are used to connect the node to one more other
nodes. In graphical form, a node may be depicted as a box, which is divided into
two types of components:
• A data block that stores one or more data components.
• One or more link components that are references to other nodes.

A simple node has a simple data block and one reference to another node.

• The nodes in a linked list are referenced by relationship not by position; to
find a data item, always start from the first item (no direct access). Recall
that access to the elements in an array is carried out using an index.

The following listing shows the Python code with a class definition of a node. Class Node includes two attributes: the data and the reference next to another node. The class also defines two methods, the constructor has one parameter with a default value of None.

class Node:
def __init__(self, data=None, _next=None):
self.data = data
self._next = _next
Creating and Manipulating a Linked List in python 3.
class Node:
def __init__(self, data=None, _next=None):
self.data = data
self._next = _next


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

def insert_at_front(self, data):
node = Node(data, self.head)
self.head = node

def insert_at_back(self, data):
if self.head is None:
self.head = Node(data, None)
return
else:
count = self.head
while count._next:
count = count._next
count._next = Node(data, None)

def _print(self):
count = self.head
text = ''

while count:
text += str(count.data) + '-->'
count = count._next

print(text)

def make_linked_list(self, _list):
self.head = None
for element in _list:
self.insert_at_back(element)

def get_length(self):
temp = self.head
count = 0
while temp:
count += 1
temp = temp._next
return count

def remove_at(self, index):
if index == -1 or index > self.get_length():
raise Exception('index error!')
elif index == 0:
self.head = self.head._next()
else:
count = 0
temp = self.head
while temp:
if count == index - 1:
temp._next = temp._next._next
break
else:
temp = temp._next

def insert_at_values(self, index, value):
if index == -1 or index > self.get_length():
raise Exception('index error')
elif index == 0:
self.insert_at_front(value)
else:
counter = 0
temp = self.head
while temp:
if counter == index - 1:
node = Node(value, temp._next)
temp._next = node
break
temp = temp._next
counter += 1

def insert_after_values(self, data_after, data_insert):
temp = self.head
while temp:
if temp.data == data_after:
node = Node(data_insert, temp._next)
temp._next = node
break
else:
temp = temp._next

def remove_by_value(self, data):
temp = self.head
flag = temp
while temp:
if temp.data == data:
flag._next = flag._next._next
break
elif temp._next is None:
print('no data!')
break
else:
flag = temp
temp = temp._next


Heres how you can implement the Linked List


linked_list = Linkedlist()
linked_list.make_linked_list(['banana', 'mango', 'grapes', 'orange'])
linked_list.insert_after_values('mango', 'y')
linked_list._print()
linked_list.remove_by_value('orange')
linked_list._print()

linked_list.remove_by_value('figs')
linked_list._print()

Output:

banana–>mango–>y–>grapes–>orange–>
banana–>mango–>y–>grapes–>
no data!
banana–>mango–>y–>grapes–>

But Following are the disadvantages of the Singly Linkedlist

1) It requires more space as pointers are also stored with information.

2) Different amount of time is required to access each element.

3) If we have to go to a particular element then we have to go through all those elements that come before that element.

4) we can not traverse it from last & only from the beginning.

5) It is not easy to sort the elements stored in the linear linked list.

Make Sure To Comment Whether you Understood The Above Concept

HAPPY CODING MATES:)

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Shopping Cart