Python Linked List: Print a given doubly linked list in reverse order
Last update on January 04 2021 14:02:41 [UTC/GMT +8 hours]4. Python program to create a doubly linked list of n nodes and display it in reverse order.
In this program, we create a doubly linked list and then reverse the list by reversing the direction of the list and print out the nodes.
Traverse through the list by swapping the previous pointer with next pointer of each node. Then, swap the position of head and tail node that is, head of the original list will become tail of new list and tail of the original list will become head of the new list. So, the reversed list will be:
ALGORITHM:
- Define a Node class which represents a node in the list. It will have three properties: data, previous which will point to the previous node and next which will point to the next node.
- Define another class for creating a doubly linked list, and it has two nodes: head and tail. Initially, head and tail will point to null.
- addNode[] will add node to the list:
- It first checks whether the head is null, then it will insert the node as the head.
- Both head and tail will point to a newly added node.
- Head's previous pointer will point to null and tail's next pointer will point to null.
- If the head is not null, the new node will be inserted at the end of the list such that new node's previous pointer will point to tail.
- The new node will become the new tail. Tail's next pointer will point to null.
a. reverse[] will reverse the given doubly linked list.
- Define a node current which will initially point to head.
- Traverse through the list by making current to point to current.next in each iteration till current points to null.
- In each iteration, swap previous and next pointer of each node to reverse the direction of the list.
- In the end, swap the position of head and tail.
a. display[] will show all the nodes present in the list.
- Define a new node 'current' that will point to the head.
- Print current.data till current points to null.
- Current will point to the next node in the list in each iteration.
PROGRAM:
Output:
Reverse a Doubly Linked List
Given a Doubly Linked List, the task is to reverse the given Doubly Linked List.
See below diagrams for example.
[a] Original Doubly Linked ListHere is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head [or start] and change the head pointer in the end.
Python Program For Reversing A Doubly Linked List
Given a Doubly Linked List, the task is to reverse the given Doubly Linked List.
See below diagrams for example.
[a] Original Doubly Linked ListHere is a simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers for all nodes, change prev of the head [or start] and change the head pointer in the end.
|
# Program to reverse a doubly linked list
# A node of the doubly linked list
class Node:
# Constructor to create a new node
def __init__[self, data]:
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
# Constructor for empty Doubly
# Linked List
def __init__[self]:
self.head = None
# Function reverse a Doubly Linked List
def reverse[self]:
temp = None
current = self.head
# Swap next and prev for all nodes
# of doubly linked list
while current is not None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev
# Before changing head, check for the
# cases like empty list and list with
# only one node
if temp is not None:
self.head = temp.prev
# Given a reference to the head of a list
# and an integer,inserts a new node on the
# front of list
def push[self, new_data]:
# 1. Allocates node
# 2. Put the data in it
new_node = Node[new_data]
# 3. Make next of new node as head
# and previous as None [already None]
new_node.next = self.head
# 4. change prev of head node to
# new_node
if self.head is not None:
self.head.prev = new_node
# 5. move the head to point to the
# new node
self.head = new_node
def printList[self, node]:
while[node is not None]:
print node.data,
node = node.next
# Driver code
dll = DoublyLinkedList[]
dll.push[2]
dll.push[4]
dll.push[8]
dll.push[10]
print
"Original Linked List"
dll.printList[dll.head]
# Reverse doubly linked list
dll.reverse[]
print
"Reversed Linked List"
dll.printList[dll.head]
# This code is contributed by Nikhil Kumar Singh[nickzuck_007]
|
Output:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10Time Complexity: O[N], where N denotes the number of nodes in the doubly linked list.
Auxiliary Space: O[1]
We can also swap data instead of pointers to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. Swapping data can be costly compared to pointers if the size of the data item[s] is more.
Please write comments if you find any of the above codes/algorithms incorrect, or find better ways to solve the same problem.
Method 2:
The same question can also be done by using Stacks.
Steps:
- Keep pushing the node’s data in the stack. -> O[n]
- The keep popping the elements out and updating the Doubly Linked List
|
"""
Function to reverse a doubly-linked list
swap next and prev pointers for all the
nodes change prev of the head node
change head pointer
"""
class Node:
def __init__[self, data]:
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__[self]:
self.head = None
"""
Method to reverse a Doubly-Linked List
using Stacks
"""
def reverseUsingStacks[self]:
stack = []
temp = self.head
while temp is not None:
stack.append[temp.data]
temp = temp.next
# Add all the elements in the stack
# in a sequence to the stack
temp = self.head
while temp is not None:
temp.data = stack.pop[]
temp = temp.next
# Popped all the elements and the
# added in the linked list,
# in a reversed order.
"""
Method to push a new item before
the head
"""
def push[self, new_data]:
new_node = Node[new_data]
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
"""
Method to traverse the doubly-linked
list and print every node in the list
"""
def printList[self, node]:
while[node is not None]:
print[node.data]
node = node. next
# Driver code
dll = DoublyLinkedList[]
dll.push[2]
dll.push[4]
dll.push[8]
dll.push[10]
print[
"original doubly-linked list"]
dll.printList[dll.head]
# Reverse a doubly-linked list
dll.reverseUsingStacks[]
print["Reversed doubly-linked list"]
dll.printList[dll.head]
|
Output:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10Time Complexity: O[N]
Auxiliary Space: O[N]
In this method, we traverse the linked list once and add elements to the stack, and again traverse the whole for updating all the elements. The whole takes 2n time, which is the time complexity of O[n].
Please refer complete article on Reverse a Doubly Linked List for more details!
C++
/* C++ program to reverse a doubly linked list */ #include using namespace std; /* a node of the doubly linked list */ class Node { public: int data; Node *next; Node *prev; }; /* Function to reverse a Doubly Linked List */ void reverse[Node **head_ref] { Node *temp = NULL; Node *current = *head_ref; /* swap next and prev for all nodes of doubly linked list */ while [current != NULL] { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } /* Before changing head, check for the cases like empty list and list with only one node */ if[temp != NULL ] *head_ref = temp->prev; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginging of the Doubly Linked List */ void push[Node** head_ref,int new_data] { /* allocate node */ Node* new_node =new Node[]; /* put in the data */ new_node->data = new_data; /* since we are adding at the begining, prev is always NULL */ new_node->prev = NULL; /* link the old list off the new node */ new_node->next = [*head_ref]; /* change prev of head node to new node */ if[[*head_ref] != NULL] [*head_ref]->prev = new_node ; /* move the head to point to the new node */ [*head_ref] = new_node; } /* Function to print nodes in a given doubly linked list This function is same as printList[] of singly linked lsit */ void printList[Node *node] { while[node != NULL] { cout data 8->4->2 */ push[&head, 2]; push[&head, 4]; push[&head, 8]; push[&head, 10]; cout
Chủ Đề |