java 链表与堆栈

LinkedList vs Stack

提问by user2372074

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

在java中，可以使用LinkedList实现的栈。换句话说，您可以使用链表来实现堆栈的所有功能。从这个意义上说，为什么我们仍然需要堆栈类，为什么我们不坚持使用链表来保持简单？谢谢

回答by 5gon12eder

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

首先，在Stack's 文档的介绍中说：

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

Deque接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作，应优先使用此类。

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

这告诉我们，Stack该类主要是遗留下来的，随着更新的Java 集合框架或多或少变得多余。

Second, “providing the same functionality” is not a good measure to gauge whether a class should be there or not. While a LinkedListprovides 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 ArrayListmuch more appealing to implement a stack.

其次，“提供相同的功能”并不是衡量一个类是否应该存在的好方法。虽然 aLinkedList提供了创建堆栈所需的所有操作，但它的性能会很差。链表适用于在随机位置插入和删除元素。在堆栈中，我们只在末尾追加或删除，这使得ArrayList实现堆栈更具吸引力。

At this point, we realize that ArrayListand LinkdListboth provide the functionality of a Listwhich brings us close to the heart of good object oriented design:

在这一点上，我们意识到ArrayList和LinkdList两者都提供了 a 的功能，List这使我们接近良好的面向对象设计的核心：

• We define a set of operations in an interface(eg List).
• We provide one or more implementationsof that interface that must all provide the required functionality but may be optimized for a certain use case (eg ArrayListor 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 couldimplement Stackby simply delegatingto ArrayListbut 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.Stackdoes which brings us back to the quote from the docs.)

• 我们在接口中定义了一组操作（例如List）。
• 我们提供该接口的一个或多个实现，这些实现必须全部提供所需的功能，但可以针对特定用例（例如ArrayList或LinkedList）进行优化。
• 如果某个使用模式出现得特别频繁，我们可能会决定添加另一个在其名称中引用此模式的类，这将使代码结构更好。例如，我们可以实现Stack通过简单地委托给ArrayList，但提供一个类型，其名称是什么它的意思是，不提供操作（如随机存取）可能违反堆栈的概念明确表示。（这不是java.util.Stack让我们回到文档中引用的内容。）

Note that the inheritance relation between Listand the newer Dequeinterface is more consistent than between Listand Stack. LinkedListimplements Dequewhich is correct since a Dequerequires elements can be added and removed from / to the beginning or end and LinkedListqualifies for this by offering insertion and deletion at random positions. On the other hand Stackimplements Listwhich should be considered questionable.

请注意，List和较新的Deque接口之间的继承关系比List和之间更一致Stack。 LinkedList实现Deque这是正确的，因为Deque可以从/到开头或结尾添加和删除 requires 元素，并LinkedList通过在随机位置提供插入和删除来满足此要求。在另一方面Stack器具List应视为可疑。

---

---

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 ArrayListmuch more appealing to implement a stack.”, I would like to expand on that.

后期更新：因为我对“链表适合在随机位置插入和删除元素ArrayList的声明”投反对票。在堆栈中，我们只在末尾追加或删除，这使得实现堆栈更具吸引力。” ，我想扩展一下。

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 muchhigher.

链表允许在恒定时间内在任意位置插入和删除元素。另一方面，在给定索引的情况下，查找元素需要线性时间。当我说它们适合在随机位置插入和删除时，我的意思是迭代器给出的位置，而不是索引。如果索引中给出，插入和删除将是两个，链表和数组的线性时间的操作，但对于一个链表中的常数因子将是多少更高。

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.

更好的数据结构是可变数量的固定大小的缓冲区，通过指针链接在一起。这样的数据结构通常用于实现所谓的双端队列。它以很少的额外开销提供了数组的最大优势，并且从末尾（或开头）添加和删除不仅是一种摊销，而且始终是一个恒定时间的操作。

回答by userMostRad

The Stackclass extends Vector, so it is synchronized. The LinkedListclass 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, Dequeand its implementations are preferred to Stack

的Stack类扩展Vector，因此它是同步的。该LinkedList班是没有的。最佳选择取决于您要尝试执行的操作和约束，但一般来说，同步类的开销要多一些。此外，正如@NESPowerGlove 所提到的，Deque它的实现是首选Stack

回答by NESPowerGlove

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

当您可以使用范围更窄或更正确的数据结构时，使用一种数据结构会产生问题，原因有两个：

1. The better suited 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 it primary just inserts data in the middle of the list quite commonly, you may want to consider a LinkedList versus an ArrayList, same operations, but LinkedList is more suited as the insert(n) operation is optimized over other operations/features).

2. A future reader of the code will be confused on why the lesser suited data structure was used as it's a code smell. The reader will spend more time reading your code and may even replace it even if the operations currently used are not anymore optimized when switching to the better suited data structure.

1. 更适合的数据结构可能会针对操作子集或它所具有的特定操作进行更优化（例如，假设您的应用程序需要一个列表，而它主要只是在列表中间插入数据，这很常见，您可能想要考虑 LinkedList 与 ArrayList，相同的操作，但 LinkedList 更适合，因为 insert(n) 操作比其他操作/功能进行了优化）。

2. 代码的未来读者将会对为什么使用不太合适的数据结构感到困惑，因为它是代码异味。读者将花更多时间阅读您的代码，甚至可能会替换它，即使当前使用的操作在切换到更合适的数据结构时不再优化。

On a side note, the more modern stack implementation in Java is java.util.Deque.

附带说明一下，Java 中更现代的堆栈实现是 java.util.Deque。