The Gateway to Computer Science Excellence
0 votes
Implement Linked list using stack.
in Programming by Active (4k points) | 158 views
I think we implement stack using linked list not vice versa.
Why not vice versa?
linked list is a DS in which we can add and delete anywhere.

In stack we can delete and insert only at top.(Stack is specialized version of linked list) (we can also make it using array)

So if we want to make a linked list using stack we will need more than 1 stack otherwise how can we insert in middle using only 1 stack.

If 2  or more stacks are there then it might be possible.
yes, right.

Stack is already created with LL.

Then how that push and pop operation will use for insert and delete operation in LL??
we can also create stack using array.
yes, that is true.

But after that creation of LL is not possible
yes, you can use multiple stacks -- question doesnt specify a single one rt?
yes sir, i got confused since stack is written and not stacks

@srestha why so ?

we will make stacks using array i.e. arrays will follow all the properties of stack and then we just have to manipulate these stacks such that they behave like linked list. 

when we will give a single operation like insert 

then multiple operation will run in these stacks to mimic the behaviour of linked list.


Then  simplfy of this question is like this

Create a LL, where each element of LL is a stack :)

@Arjun Sir

Why do we put so much effort, rather just create a LL will solve purpose :) 

because this was the demand of the question.


Can u write simple code or algo for it?

we have  stack 1,S1 and stack 2,S2

stack 1 and stack 2 is empty.

To create a linked list simply push n items in Stack 1.

So stack S1 has nth element at top and 1st element at bottom.

To insert at kth position

1. we remove top n-k elements from stack S1 and put them in S2. S2 top has kth element and bottom has the nth element.

2. then insert the new element in S1.

3. for all elements of S2. pop S2 and push them in S1.

Now S2 is empty and  S1 has n+1 elements.

To delete at kth position
1. same as step 1 of insert

2. delete the top element of stack2

3. same as step 3 of insert.
how Linked List??
the operations which you want to do on linked list i am doing them using stack.

Its same like implementing queues using stack

Thanks @Satbir Your implementation looks good.
@Arjun sir ,please confirm if anything is missing in the implementation.

1 Answer

0 votes
Stacks are Abstract Data types which can be created using Linked-List or arrays depending on our need. If we want to create a LinkedList using stack, we can do it like suppose we pop ,the  top element from the stack, create a node using malloc and then  insert it at the front of the list, maintaining a head of the linked list and it will be updated every time we pop one element  from the stack.
by (433 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,299 answers
104,990 users