Given below is the implementation of a standard class-based singly Linked List in Python.
# A single node of a singly Linked List class Node: # constructor def __init__(self, data = None, next=None): self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__(self): self.head = None # insertion method for the linked list def insert(self, data): newNode = Node(data) if(self.head): current = self.head while(current.next): current = current.next current.next = newNode else: self.head = newNode # print method for the linked list def printLL(self): current = self.head while(current): print(current.data) current = current.next # Singly Linked List with insertion and print methods LL = LinkedList() LL.insert(3) LL.insert(4) LL.insert(5) LL.printLL()
Now that we have the implementation of a Linked List in Python, we want to implement a method reverse()
which does the following:
head
starts pointing to the last element of the list.Given below is an iterative approach as to how you can reverse a given Linked List in Python:
previous
: Initially pointing at None
(line 3), this variable points to the previous element so the node.next
link can be reversed using it (line 9). This is then updated to the node next to it, i.e., current
(line 10).
current
: Initially pointing to head
(line 4), the node being pointed to by this variable gets its node.next
set to the previous
item in the list (line 9). This is then updated to the node next to it, i.e., following
(line 11).
following
: Initially pointing to the second node (line 5), this is used so the current
pointer may move one step ahead (line 12-13) in each iteration.
def reverseList(list): # initialize variables previous = None # `previous` initially points to None current = list.head # `current` points at the first element following = current.next # `following` points at the second element # go till the last element of the list while current: current.next = previous # reverse the link previous = current # move `previous` one step ahead current = following # move `current` one step ahead if following: # if this was not the last element following = following.next # move `following` one step ahead list.head = previous # Testing LL = LinkedList() LL.insert(1) LL.insert(2) LL.insert(3) LL.insert(4) print("Linked List") LL.printLL() print("Reversed Linked List") reverseList(LL) LL.printLL()
RELATED TAGS
View all Courses