What are algorithm for linked list implementation of stack?

Answer 1

A stack is a last-in, first-out data structure (LIFO). A linked list gives you constant time access to the head of the list, thus all insertions (pushes) and extractions (pops) must be done at the head of the list to implement a stack:

Algorithm: push

Input: a linked list Lst and a value Val

Output: none

Nod = new node (Val) // instantiate a new node with given value

if Lst->count > 0 then Nod->next := Lst->head // point the new node at the head

Lst->head := Nod // make the new node the head

Lst->count := Lst->count + 1 // increment the count

Algorithm: pop

Input: a linked list, Lst Output: none

if Lst->count = 0 then return // can't pop from an empty list!

Old := Lst->head // store the current head

Lst->head := Lst->head->next // set the new head (may be null)

delete Old // delete the old head

Lst->count := Lst->count - 1 // decrement the count