Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations.Linked Lists are one of the most fundamental and important data structures having a wide range of applications. Linked Lists are also important from the perspective of interviews as well. In this article we are going to take a look at one such problem
Problem Statement
We were given a linked list. The task is to use an auxiliary Stack to reverse the order of elements in the Linked List.
Example 1:
Input 1: 4 1 3
Output 1: 3 1 4
Example 2:
Input 2: 4 7 8 1 9
Output 2: 9 1 8 7 4
Recommended: Try the Problemyourself before moving on to the solution.
Approach
The idea of this approach is simple: traverse all the nodes one by one from the starting node of the given linked list and push all the values of the nodes into the auxiliary stack.
We know that the stack Data Structure follows the LIFO(last in first out) order. So, if we extract the content of the stack, we get the last element first, then the second last element and so on, i.e. we get the data in reverse order.
Finally, we change the linked list data from starting with the reversed data from the stack one by one for all nodes.
Steps:
Declare a stack.
Push all the values of the nodes from starting into the stack.
Change the values of the nodes from the beginning of the linked list with the top element of the stack.
Move to the next node and pop the top element from the stack, and
Repeat steps 3 and 4 while the stack is not empty.
Let’s understand the above approach with an example:
Initially, the curr pointer points to the head of the linked list, and all the nodes are pushed into the stack data structure.
Now we replace, curr->data with the stack.top() element and move the curr pointer to the next node and pop the top element of the stack.
Again repeat the above process by replacing curr->data with the stack.top() element and moving the curr pointer to the next node and popping the top element of the stack.
We keep on repeating this step until we reach the end node of the linked list.
Now, the stack is empty, and we get the required reversed linked list.
Stacks operate on the LIFO principle, which states that the element inserted last is the first element to be removed from the list. Whereas, Queues operate on the FIFO principle, which states that the element inserted first is the first element to be removed from the list.
What is the purpose of a linked list?
Linked lists are linear data structures that store information in individual nodes. These nodes contain information as well as a link to the next node in the list. Linked lists are commonly used due to their ease of insertion and deletion.
Conclusion
So, this article discussed the approach to reverse a linked list with the help of stack data structure by using its LIFO order property, examples for a better understanding of the approach and its code in C++.