Which is exactly what we did and hence accomplished to make a Linked List behave as a Stack. So for any data structure to act as a Stack, it should have push() method to add data on top and pop() method to remove data from top. When we say "implementing Stack using Linked List", we mean how we can make a Linked List behave like a Stack, after all they are all logical entities. In this, we simply return the data stored in the head of the list. In order to do this, we will simply delete the first node, and make the second node, the head of the list. Removing Element from Stack (Linked List) Now whenever we will call the push() function a new node will get added to our list in the front, which is exactly how a stack behaves. In order to insert an element into the stack, we will create a node and place it in front of the list. Node *front // points to the head of list Then we define our stack class, class Stack This is our Linked list node class which will have data in it and a node pointer to store the address of the next node element. In this way our Linked list will virtually become a Stack with push() and pop() methods.įirst we create a class node. With Linked list, the push operation can be replaced by the addAtFront() method of linked list and pop operation can be replaced by a function which deletes the front node of the linked list. Stack is a data structure to which a data can be added using the push() method and data can be removed from it using the pop() method. Stacks can be easily implemented using a linked list. Implementation of Stack using Linked List top: returns the element at top of stack.Let's look at what needs to be done in each function of Stack using the functions addFirst, removeFirst and getFirst.Stack as we know is a Last In First Out(LIFO) data structure. Whereas the function removeLast which we implemented takes O(n) time, therefore we discard the idea of operating at the end of the linked list. take constant time to perform their action. We do so because the functions addFirst, getFirst and removeFirst are of O(1) i.e. take constant time to perform their action.īut if you use the linked list which we implemented then we chose to operate the starting of the linked list. If we use the linkedlist which is in java then it does not matter which way we choose to do it because addition and removal at end as well as beginning are O(1) i.e. We have two options to achieve this: we can perform these operations like addition and removal either at the beginning or at the end. To make a linked list work like a stack, we need to make use of functions, such that addition and removal occurs at one end only. Element is removed and added from one end only. Which means, the end at which element will be added lastly will be the first to get accessed. Move the temporary pointer through all the nodes of the list and print the value field attached to every node. Copy the head pointer into a temporary pointer. For this purpose, we need to follow the following steps. As we know, it is also given in the question that Stack adds and removes elements in LIFO manner, i.e. Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. We will look at each function of our Stack Adapter individually. Reverse Linked List (pointer - Recursive) Remove Duplicates In A Sorted Linked Listĭisplay Reverse (recursive) - Linked List
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |