LinkedList vs Stack

Question

In java, you can use stack implemented by LinkedList. In other words, you can use linkedlist to achieve all functionality of stack. In this sense, why we still need stack class, why don't we just stick with linked list to keep the simplicity? Thanks

Solution 1

First, in the introduction of Stack's documentation it says:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Which tells us that the Stack class is mostly a leftover that has become more or less redundant with the newer Java Collections Framework.

Second, “providing the same functionality” is not a good measure to gauge whether a class should be there or not. While a LinkedList provides all the operations that are needed to make a stack, it will perform poorly. Linked lists are good for inserting and removing elements at random positions. In a stack, we only ever append to or remove from the end which makes an ArrayList much more appealing to implement a stack.

At this point, we realize that ArrayList and LinkdList both provide the functionality of a List which brings us close to the heart of good object oriented design:

• We define a set of operations in an interface (eg List).
• We provide one or more implementations of that interface that must all provide the required functionality but may be optimized for a certain use case (eg ArrayList or LinkedList).
• If a certain use-pattern occurs particularly frequent, we might decide to add another class that refers to this pattern in its name which will make the code better structured. For example, we could implement Stack by simply delegating to ArrayList but provide a type that clearly says in its name what its meant to be and does not provide operations (like random access) that might violate the concept of a stack. (This is not what java.util.Stack does which brings us back to the quote from the docs.)

Note that the inheritance relation between List and the newer Deque interface is more consistent than between List and Stack. LinkedList implements Deque which is correct since a Deque requires elements can be added and removed from / to the beginning or end and LinkedList qualifies for this by offering insertion and deletion at random positions. On the other hand Stack implements List which should be considered questionable.

---

Late Update: Since I'm getting down-votes for the statement that “Linked lists are good for inserting and removing elements at random positions. In a stack, we only ever append to or remove from the end which makes an ArrayList much more appealing to implement a stack.”, I would like to expand on that.

Linked lists allow insertion and removal of elements at arbitrary positions in constant time. On the other hand, it takes linear time to find an element, given its index. When I say that they are good for inserting and removing at random positions, I mean a position given by an iterator, not an index. If an index is given, insertion and deletion will be a linear-time operation for both, linked lists and arrays, but the constant factor for a linked list will be much higher.

Array-based lists allow for amortized constant-time insertion and deletion at the end and constant-time access by index. Adding and removing elements at random positions is a linear-time operation, regardless whether the position is given by an index or by an iterator (which is basically just an index for an array).

In a stack implementation, the only advantage of a linked list – it's ability to insert and delete elements at arbitrary positions (given by iterators) in constant time – is not needed. On the other hand, its memory overhead is considerably higher and its memory access is greatly inferior to that of a contiguous array. Given that the asymptotic complexity for appending and removing items from the end of the list is amortized constant in either case, an array-based list is a better choice for implementing the storage of a stack.

An even better data structure would be a variable number of fixed-size buffers, chained together via pointers. Such a data structure is often used to implement a so-called deque. It provides most advantages of arrays with very little additional overhead and adding and removing to / from the end (or the beginning) is not only an amortized but always a constant-time operation.

Solution 2

The Stack class extends Vector, so it is synchronized. The LinkedList class is not. The optimal choice depends on what you're trying to do and the constraints, but in general, there is a bit more overhead for synchronized classes. Also, as @NESPowerGlove mentioned, Deque and its implementations are preferred to Stack

Solution 3

This is not really a Java question but a general programming question: why use abstractions?

A stack is a data structure with two well defined operations: push and pop. We can go about implementing the stack in different ways. We could use arrays, linked lists, or some other structure.

The stack class is going to be a very thin layer over the linked list or array, and so the question arises: why go through the trouble of defining a separate class?

There are a few reasons which are basically the reasons we use abstractions in programming in general:

1. readability- If what you have is a stack it would be much clearer to whoever is reading your code (including your future self) if you actually use a stack object and its operations of push and pop explicitly and not just add and remove from a list.

2. data structure vs implementation- The stack is a data structure defined by its operations. The linked list is just one possible implementation. Defining the stack allows you to change implementation in the future without changing the code in any other place where the stack is being used. Just to make it clear let's say that you have implemented a stack with linked list, but after a while you've had a change of hearts and you decide to change the implementation to using an array instead. All you have to do is change the stack class implementation without the need to change the code in any other place where you actually used the stack. If you just used a linked list you would have to go through your code and change it EVERYWHERE.

3. type checking- Java like many other languages check the types of functions inputs and outputs and thus help us catch errors. Therefore defining different types can help writing better code and helps the compiler catch errors.

4. Adding unique functionality- I said that the stack is going to be a thin layer over the linked list, but it can still contain some functionality that the linked list does not have. perhaps when you print the stack you want to do it from top to bottom, while in the linked list it is the other way around. By defining a separate class you can change or add this desired functionality.

5. limiting functionality- You can do many thing to lists which you are not allowed to do with a stack. The main difference is that in lists you can add or remove values from any position, while in a stack you can only add and remove from the top. If you use a linked list to simulate a stack you might unwittingly do something wrong, which would be impossible if you defined a stack class which limits you to push and pop only.