CODEWITHSUNDEEP
c++linked-liststackbig-o
Justin Yum
Justin Yum

Reputation: 189

Writing pop() method for LinkedStack in O(1)

How would I write a pop() method for LinkedStack in O(1)? I have two private data members in my LinkedStack class: ListNode* head and ListNode* tail.

head points to the beginning of the LinkedStack, and tail points to the end of the LinkedStack.

pop() will remove the ListNode being pointed to by tail, then tail will point to the ListNode that was before tail.

Knowing this, how would I write pop() in O(1)? Obviously, I can write a for loop that grabs the previous ListNode right before tail, but then pop() wouldn't be O(1).

Since this is for homework, I'm not looking for code solutions, just maybe a hint in the right direction.

Edit: One solution I possibly see is having a ListNode* prev data member, which always points to the previous ListNode before tail. But I feel like there's a more efficient way....

Edit2: Thanks @user4581301. Assume that pop() will not be called when LinkedStack is empty.

Upvotes: 1

Views: 607

Answers (1)

paxdiablo
paxdiablo

Reputation: 881643

As you state, any situation where you have to traverse the list to locate a specific element is going to make the constant time requirement impossible to meet. This includes a singly-linked list where you're pushing items on to the end. A doubly-linked list will be easier since you can then get from the tail to the penultimate item without traversal.

However, I'm not sure why you're pushing on to the end. If you were to push new elements on the the front of the list, achieving constant time for both push and pop is trivial.

By that, I mean (pseudo-code since, as you mention, "this is for homework"):

def push(x):
    allocate node          # get new node and set data.
    node.data = x

    node.next = head       # insert at head of list
    head = node

def pop():
    assert head != null    # catch pop on empty stack

    node = head            # get first node and data
    retval = node.data

    head = head.next       # set head to be second node

    free node              # free node and return data
    return retval

You can see that there is no traversal of the list for either operation. First, pushing 7 on to a stack of primes:

Starting list:
    head
        \
         5 -> 3 -> 2 -|

Create new node, point to current head:
     head
         \
     7 -> 5 -> 3 -> 2 -|

Point head at new node:
    head
        \
         7 -> 5 -> 3 -> 2 -|

Now let's pop that same value.

Starting list:
    head
        \
         7 -> 5 -> 3 -> 2 -|

Save head as node, and value to return (7):
    head
        \
         7 -> 5 -> 3 -> 2 -|
        /
    node

Adjust head:
         head
             \
         7 -> 5 -> 3 -> 2 -|
        /
    node

Free node and return stored value (7):
    head
        \
         5 -> 3 -> 2 -|

Upvotes: 3

Related Questions