Linked List using Python
What is a linked list?
A linked list is a linear data structure to store a collection of items. The data in a linked list can be of any type -strings, characters, numbers. The elements can be sorted, unsorted. They can contain duplicate elements or all unique elements.
In a linear data structure, the elements are organized in a sequence whereas in a non-linear data structure the elements are organized without any sequence
So a linked list consists of a group of nodes in a sequence. Each node holds its own data and the address of the next node hence forming a chain-like structure. Linked list elements are not stored at the contiguous location, the elements are linked using pointers. A characteristic specific to linked lists is that the order of the nodes isn’t dictated by their presence in memory, but rather the pointers that each node has to the next node in the sequence.
Array vs Linked List
Multiple types of Linked Lists exist:
- Singly Linked Lists — The nodes in Singly Linked Lists contain a pointer to the next node in the list.
- Doubly Linked Lists — This kind of Linked List contains both a pointer to the next, but also a pointer to the previous node in the list.
- Circular Linked Lists — Instead of containing a null pointer at the end of the list, the last node in these lists contains a pointer to the first node, making them circular.
Creating a Linked List
Creating a new singly linked list takes O(1) time
The linked list now looks like this (head=>12->99->37->None)
Displaying a Linked List
Displaying a singly linked list takes O(n) time
So the Linked List class now has two functions insert and display
Following is an example of the implementation of the Linked List class
Inserting a node at the start
Earlier we inserted a node at the end of the LinkedList, this function will insert a node at the start . Inserting a new node at the beginning of the list takes O(1) time
The insert function created earlier has been renamed to insertEnd which inserts a new node at the end of the LinkedList. Class LinkedList now looks like this. Inserting a new node at the end of the list takes O(n) time
Following is the implementation of insertHead method which creates a linked list as (head=>30->20->10->None)
Inserting a new node between two nodes
Takes O(n) time
Suppose we have a Linked List L1 (head =>10->20–>30->None) and we want to insert a new node at position 1 ( like an array/list in python, we will keep 0 based indexing for the linked list too) so that the linked list L1 becomes:head=>10->15->20->30->None
If position = 0 (starting position) or head of the linked list
If some invalid value is given for the position parameter like less than 0(<0 ) or >length of the linked list ( -1 or 9 in this case) it will give the output as invalid Invalid Position
Deleting the last node
Takes O(n) time
If we’ll try to delete from an empty linked list it will print ‘empty list’
Deleting a node at any position
Takes O(n) time
Here is the code for the complete Linked List class:
class LinkedList:
def __init__(self):
self.head = None
def listLength(self): """returns length of the list""" length=0
if self.head is None:
return length
currentNode = self.head
while currentNode is not None:
length+=1
currentNode = currentNode.next
return length
def display(self):
"""displays the data present in the list""" if self.head is None:
print ('Empty List')
else:
currentNode = self.head
while True:
if currentNode is None:
break
print(currentNode.data)
currentNode = currentNode.next def insertEnd(self,newNode): """inserts a new node at the end of the list""" if self.head is None:
self.head = newNode
else:
lastNode = self.head
while True:
if lastNode.next is None:
break
lastNode = lastNode.next
lastNode.next = newNode
def insertHead(self,newNode): """inserts a new node at the beginning of the list""" newNode.next = self.head
self.head = newNode
def insertAt (self,newNode,position): """inserts a new node at a specified position in the
list""" if position < 0 or position > self.listLength():
print ('Invalid Position')
return
if position == 0:
self.insertHead(newNode)
return
currentPosition = 0
currentNode = self.head
while currentPosition != position-1:
currentPosition +=1
currentNode = currentNode.next
newNode.next = currentNode.next
currentNode.next = newNode
def deleteEnd(self): """deletes a node from the end of the list""" if self.listLength() == 0:
print ("Empty List")
return
elif self.listLength() == 1:
self.listLength -=1
self.head = None
else:
currentNode = self.head
while currentNode.next.next is not None:
currentNode = currentNode.next
currentNode.next = None
def deleteAt(self,position): """deletes a node at the specified position from the
list""" if position < 0 or position >= self.listLength():
print ('Invalid Position')
return
elif position == 0:
previousHead = self.head
self.head = self.head.next
previousHead.next = None
return
else:
currentPosition=0
currentNode = self.head
while True:
if currentPosition == position:
previousNode.next = currentNode.next
currentNode.next = None
break
previousNode = currentNode
currentNode = currentNode.next
currentPosition+=1
Doubly Linked List
As the name suggests, each node in a doubly-linked list has two nodes: one pointing to the next node and one pointing to the previous node. Here’s the Python implementation:
class DoublyNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = NoneAdvantages over Singly linked list
1) It can be traversed in both forward and backward directions.
2) The delete operation is more efficient (take a look at p4 below and contrast it with the delete operation for a doubly-linked list).
Disadvantages over Singly linked list
1) Every node requires extra space for a previous pointer.
2) All operations require an extra pointer to be maintained.
