LinkedList与Stack

Question

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

Answer 1

首先,在介绍Stack文档时,它说:

Deque接口及其实现提供了更完整和一致的LIFO堆栈操作集,应该优先使用该类.

这告诉我们,这个Stack类主要是一个剩余的,它已经或多或少地与新的Java Collections Framework一起变得多余.

其次,"提供相同的功能"并不是衡量一个班级是否存在的好方法.虽然a LinkedList提供了堆栈所需的所有操作,但它的性能很差.链接列表适用于在随机位置插入和删除元素.在堆栈中,我们只会附加到末尾或从末尾移除,这使得ArrayList实现堆栈更具吸引力.

在这一点上,我们认识到,ArrayList并LinkdList都提供的功能List这使我们接近良好的面向对象设计的心脏:

• 我们在接口中定义一组操作(例如List).
• 我们提供该接口的一个或多个实现,它们必须都提供所需的功能,但可以针对特定用例(例如ArrayList或LinkedList)进行优化.
• 如果特定的使用模式特别频繁发生,我们可能会决定在其名称中添加另一个引用此模式的类,这将使代码更好地构建.例如,我们可以Stack通过简单地委托来实现,ArrayList但是提供一种类型,该类型在其名称中清楚地表明它的意图是什么,并且不提供可能违反堆栈概念的操作(如随机访问).(这不是什么java.util.Stack让我们回到文档的引用.)

请注意,List较新Deque接口之间的继承关系比List和之间的更一致Stack. LinkedList实现Deque是正确的,因为Deque可以在开头或结尾添加和删除需要元素,并LinkedList通过在随机位置提供插入和删除来限定它.在另一方面Stack器具List应视为可疑.

最新更新:因为我对"链接列表有利于在随机位置插入和删除元素ArrayList的声明"进行了投票.在堆栈中,我们只是追加或从末尾移除,这使得实现堆栈更具吸引力.",我想扩展它.

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

基于数组的列表允许在结束时进行分摊的常量时间插入和删除,并通过索引进行常量时间访问.在随机位置添加和删除元素是线性时间操作,无论位置是由索引还是由迭代器(基本上只是数组的索引)给出.

在堆栈实现中,链接列表的唯一优势 - 它不需要在常量时间内在任意位置插入和删除元素(由迭代器给出).另一方面,它的内存开销相当高,并且其内存访问远远低于连续数组的内存访问.鉴于在列表末尾附加和删除项目的渐近复杂性在任何一种情况下都是摊销常数,基于数组的列表是实现堆栈存储的更好选择.

更好的数据结构是可变数量的固定大小的缓冲区,通过指针链接在一起.这种数据结构通常用于实现所谓的双端队列.它提供了阵列的大多数优点,只需要很少的额外开销,并且在末尾(或开头)添加和删除不仅是一个摊销,而且总是一个恒定时间的操作.

Answer 2

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

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

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

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