Previously the stack was implemented using an array. We can also implement a stack using a linked list. The advantage to using a linked list is that there is no limit on the size of the stack.
The field for the stack is the pointer to the first node in the list:
LLNode<T> top;
The push method creates a node for the new element and adds it to the list. The pop method removes the top element from the list. The top method returns the top element. In the array based stack the bottom of the stack is in location [0] because that makes the stack methods efficient and easy to implement. How should the items be added to the linked stack to make the methods efficient and easy to implement?
The stack is only accessed at one end: the top. Elements in the middle or at the bottom of the stack cannot be accessed until they reach the top. Thus the best way to implement the linked stack is to have the head pointer refer to the object on top of the stack. That's why the head pointer is called top in the linked stack.
The code to push an item on the stack adds the item to the front of the list. We've already looked at this code:
Top doesn't change the stack, it returns a reference to the item on top. The code for this is:
To pop, we need to remove the front item from the list, as shown in the following picture where north is popped from the stack:
In the LinkedStack class the methods must make sure they work correctly in all cases, so exceptions are added to the code we wrote above.
LinkedStack classTo derive the complexity of each method, we look at the code for each method, count the number of statements as a function of N, the number of elements in the stack, then get the big O. Assume we are looking at the worst case.
push
pop
top
isEmpty
isFull
Email Me |
Office Hours |
My Home Page |
Department Home |
MCC Home Page
© Copyright Emmi Schatz 2017