Linked List implementation for a stack

Question

Here is my implemetation of stack with linkedlist

STACK using linked list 

STACK-EMPTY:
if L.head == NIL
    return True
else return False

PUSH(x):
x.next = L.head 
if L.head != NIL
    L.head.prev = x
L.head = x
x.prev = NIL

POP():
x = L.head
L.head = x.next
x.next.prev = L.head
return x

would you validate this? how to improve ?

thanks

Answer 1

You can improvement the consistency of your data structure:

1. The prev of the list head is always NIL
2. An element which is not in the list has next and prev set to NIL

Taking 1. in account your POP has an inconsistency which can be source of errors: When you pop an element the prev of the head is the head itself, when you push an element the prev of the head is NIL.

Answer 2

Try this...

Definitions:

• S.top is a pointer to some node of type X at the top of the stack
• X is a node having two pointers, top and base
• X.top points to the next node toward the top of the stack.
• X.base points to the next node toward the base of the stack (bottom)

First initialize the stack top pointer:

STACK-INITIAL:
S.top = NIL
return true  // Never fails

Test for empty stack:

STACK-EMPTY:
return (S.top == NIL)

Push node x on stack:

PUSH(x):
x.top = NIL     // Top of stack, therfore top is NIL
x.base = S.top  // base is previous top
S.top = x       // x is now top of stack  
return true

Pop and return top of stack (this is the only 'interesting' part):

POP():
x = S.top          // Top node on stack (could be NIL)
if S.top != NIL    // Check in case stack was empty
  S.top = x.base   // New top = next node toward base
  x.base = NIL     // Disconnect x from stack
  if S.top != NIL  // Is stack now empty?
    S.top.top = NIL // No, set top node's top pointer to NIL
return x            // x could be NIL if stack was empty

Something to think about... I used a double linked list above because it looked like that is what you were using. However, you only need a single linked list where the links point to the base of the stack. Notice that the x.top pointers in the above algorithm are pretty much useless (set but never referenced). As long as you keep track of the stack top (S.top) the only thing you need to do is trace back down the stack during POP operations.

Response to comments

When an element is poped off of the stack, all of its associated pointers should be set to NIL. This is because it is no longer part of the stack so should not point to any stack elements. I added that bit to my original answer (see above).

In a similar manner, the new top of stack element (unless the stack becomes empty) needs to have its pointer to the element above it set to NIL (since the element above it was removed). In my example that is what the S.top.top = NIL stuff was all about (S.top points to the top stack element so S.top.top is the top pointer of that element). I think you would do the same with x.next.prev = NIL, assuming x is the element you POPed and is not NIL itself. In your pseudocode it looks like x.next.prev = L.head would leave the prev pointer of the top of stack element pointing to itself since L.head was set to x.next (the new top of stack just before that).

Finally, I question why would use a double linked list to implement a stack, only a single linked list with pointers to the next element below it are required