Log In
1 vote
Implement Linked list using stack.
in Programming 380 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.

Related questions

3 votes
0 answers
Below is a question I was asked in an Interview What is the best case time complexity to find the height of a Binary Search Tree? I answered it explaining using the below algorithm int height(struct node *root) { if(root==NULL) return 0; if(root->leftChild==NULL && root->rightChild ... $O(n).$ Was my claim correct?
asked Jul 30, 2018 in Programming Ayush Upadhyaya 163 views
0 votes
1 answer
Hello everyone. Can anyone suggest me a good book for Data Structures for GATE. Horowitz and Weiss are available in .chm format and its really difficult to read from them. Any other suggestions. Also, I have a good knowledge of C, but i have to formally study it for GATE. Any suggestions for this too?
asked May 21, 2018 in DS mohitjarvissharma 357 views
0 votes
0 answers
In C language ,declaration of variables is done as follows: <var type> <name of var1> , <name of var2>; For eg: int a,b; Then why can’t we use the declaration for pointers as follows to declare 2 interger pointers: int * a,b; instead we use : int *a, *b; ? This might be a silly doubt but please help me out.
asked Jan 20, 2019 in Programming shraddha priya 68 views
0 votes
1 answer
In nested structures, why can't d value be first assigned to the structure members and then make it nested ? I am getting an error but not understanding why. Here is an example: struct ex{ int i; ​​​​​}; struct ex u; u.i=10; struct ex1 { struct ex d; }; struct ex1 t; t.d.i= 20; printf("%d", t.d.i);
asked Apr 4, 2017 in Programming Bongbirdie 368 views