LinkedList vs Stack

Question

In java, you can use the stack implemented by LinkedList. In other words, you can use a linked list to achieve all the functionality of the stack. In that sense, why do we still need a stack class, why don't we just stick to a linked list to keep things simple? Thanks

Answer 1

First, the introduction of the Stack documentation 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 basically the remainder that has become more or less redundant with the new Java collections framework.

Secondly, “providing the same functionality” is not a good measure to determine if a class should be or not. As long as LinkedList provides all the operations necessary to create a stack, it will not work well. Linked lists are good for inserting and deleting items in random positions. On the stack, we only add or remove from the end, which makes ArrayList much more attractive for the implementation of the stack.

At this point, we understand that ArrayList and LinkdList provide a List functionality that brings us closer to the heart of a good object-oriented design:

• We define a set of operations in the interface (for example, List ).
• We provide one or more implementations of this interface that should provide the necessary functionality, but can be optimized for a specific use case (for example, ArrayList or LinkedList ).
• If a particular usage pattern is especially common, we may decide to add another class that refers to this pattern in its name, which will make the code more structured. For example, we could implement Stack simply by delegating an ArrayList , but we provide a type that clearly says in its name what it means and does not provide operations (such as random access) that could violate the concept of the stack. (This is not what java.util.Stack does, which brings us back to a quote from the docs.)

Note that the inheritance relationship between List and the new Deque interface Deque more consistent than between List and Stack . LinkedList implements Deque , which is correct, since a Deque requires that elements can be added and removed from / to the beginning or end, and LinkedList is suitable for this, offering insertion and deletion in random positions. Stack , on the other hand, implements a List , which should be considered dubious.

---

Late update:. Because I get votes for the claim that “Linked lists are good for inserting and deleting elements at random positions. On the stack, we just add or remove from the end, which makes ArrayList much more attractive for implementing the stack.” I would like to expand this.

Linked lists allow you to insert and delete items in arbitrary positions at a 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 deleting at random positions, I mean the position given by the iterator, not the index. If a pointer is specified, insertion and deletion will be performed in linear time mode for both linked lists and arrays, but the constant coefficient for the linked list will be much higher.

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

In the implementation of the stack, the only advantage of a linked list - its ability to insert and delete elements at arbitrary positions (specified by iterators) at a constant time - is not required. On the other hand, the memory overhead is significantly higher, and memory access is significantly lower than that of a continuous array. Given that the asymptotic complexity of adding and removing elements from the end of the list is in any case amortized by a constant, an array-based list is the best choice for implementing stack storage.

An even better data structure is a variable number of fixed-size buffers, linked together with pointers. This data structure is often used to implement the so-called deque. It provides most of the benefits of arrays with little extra overhead, and adding and removing to / from the end (or at the beginning) is not only amortized, but always a constant-time operation.

Answer 2

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

Answer 3

Using one data structure when you can use a narrower area or a more correct data structure is problematic for two reasons:

• A more suitable data structure may be more optimized for the subset of operations or specific operations that it has (for example, say your application needs a list, and the primary one just inserts data in the middle of the list, you can usually consider LinkedList and ArrayList, the same operations, but LinkedList is more suitable since insert (n) operation is optimized compared to other operations / functions).

• A future code reader will be confused by why a less suitable data structure was used, as it is the smell of the code. The reader will spend more time reading your code and may even replace it, even if the operations currently in use are no longer optimized when switching to a more suitable data structure.

On the other hand, a more modern stack implementation in Java is java.util.Deque.