Singly-linked list representing stack

Question

Why is it than we can use singly-linked list to represent a stack only if the links between nodes are oriented to point in the direction of top (newer) to bottom (older)?

Idos · Accepted Answer · 2015-12-04 00:34:15Z

2

Because otherwise operations like pop() will take O(n) instead of O(1) and same with the other ones. To represent a stack means accessing the last inserted item is the easiest (less time).

answered Dec 4, 2015 at 0:34

Idos

15.3k14 gold badges63 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

walton · Accepted Answer · 2015-12-04 00:56:33Z

-1

Okay i get it now, removing the head of a singly linked list take O(1) time and removing the tail takes O(n) time since you have to do a linear search to find the node that points to the tail and make that node point to null. So if the stack was tail to head (each pointer points up towards top of stack) it would take O(n) every time you popped as opposed to O(1) for a stack thats implemented head to tail (each pointer points to bottom of stack).

answered Dec 4, 2015 at 0:56

walton

1219 bronze badges

Collectives™ on Stack Overflow

Singly-linked list representing stack

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related