Hey, I suppose you have read my last article on the Linked list. If don’t then please read it first it will give you a better understanding of the linked list data structure. Here is the URL of the article Introduction to Linked List.
Now let’s implement the Singly Linked List.
Below is the template of the Node element which contains two fields one for data and another for a pointer which connects between Nodes.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
Lets first define the singly linked list class
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
Here I have taken two-pointer one for the head and second for the tail to maintain the tail pointer. So that we don’t have to iterate over and over again at the time of insertion.
Check if the head is pointing to None, if it’s pointing to None that means we linked list is empty(means we have not performed any insert operation). So in that case first create a Node and assign it to the head and then point the head to the tail. Now head and tail pointer is pointing to the same Node. if head is not None which means we have inserted elements to the list, so in that case first create a Node point it to a temporary variable and point tail next pointer to a temporary variable and then move the tail pointer to temporary variable.
class SinglyLinkedList:
.
.
def insertNodeAtTail(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
tmp = Node(data)
self.tail.next = tmp
self.tail = tmp
If head is None then the case is same as explained in the insertNodeAtTail operation. But if head is not None then create Node and assign it to temporary variable and now point temporary variable next pointer to head and at the end points head to temp. In this overall operation, we are moving one step backward from the head.
def insertNodeAtHead(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
tmp = Node(data)
tmp.next = self.head
self.head = tmp
Print operation is very important to see the elements for your list. So here I have pointed head to one temporary variable and in the next step written a while loop on the temporary variable and printed data of it.
def printNodes(self):
tmp = self.head
while tmp:
print(tmp.data)
tmp = tmp.next
The reverse operation is the most famous interview question asked by interviewers :). So let’s understand it properly. So to perform the reverse operation we need three-pointer 1. prev 2. current & 3. next pointer. As the name suggests the previous pointer points to the last Node of the current pointer. So if the current is pointing to head in that case prev pointer will point to None and same for next pointer which will point to the current of next None. Now loop over current pointer, get next Node then point current of next to prev. Now move the pointers to forward direction by pointing prev to current and current to next and at the end point head pointer to prev pointer.
def reverseList(self):
prev = None
current = self.head
while current is not None:
next_ = current.next
current.next = prev
prev = current
current = next_
self.head = prev
Remove duplicate elements from the linked list is also famous interview question. So basic idea is to remove duplicate elements from the linked list. So simple idea is that if prev Node and current Nodes values are same that means its duplicate. Then point prev pointer to next of next Node and check for the similar condition.
def removeDuplicateNodes(self):
prev = self.head
while prev.next is not None and prev is not None:
next_ = prev
while next_.next is not None:
if prev.data == next_.next.data:
dup = next_.next
next_.next = next_.next.next
del dup
else:
next_ = next_.next
prev = prev.next
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def insertNodeAtTail(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
tmp = Node(data)
self.tail.next = tmp
self.tail = tmp
def insertNodeAtHead(self, data):
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
tmp = Node(data)
tmp.next = self.head
self.head = tmp
def removeDuplicateNodes(self):
prev = self.head
while prev.next is not None and prev is not None:
next_ = prev
while next_.next is not None:
if prev.data == next_.next.data:
dup = next_.next
next_.next = next_.next.next
del dup
else:
next_ = next_.next
prev = prev.next
def printNodes(self):
tmp = self.head
while tmp:
print(tmp.data)
tmp = tmp.next
def reverseList(self):
prev = None
current = self.head
while current is not None:
next_ = current.next
current.next = prev
prev = current
current = next_
self.head = prev
if __name__ == "__main__":
sll = SinglyLinkedList()
sll.insertNodeAtTail(1)
sll.insertNodeAtTail(8)
sll.insertNodeAtTail(9)
sll.insertNodeAtTail(4)
sll.insertNodeAtTail(3)
sll.insertNodeAtTail(2)
sll.insertNodeAtTail(1)
sll.removeDuplicateNodes()
sll.printNodes()
Insertion - O(1)
Deletion - O(1)
Access - O(n)
Search - O(n)
Space Complexity - O(n)