java - Java中的List接口是什么数据结构？

Question

我很想知道什么数据结构是 Java 中的 List 接口，以及 C 中最匹配它的类似东西是什么。

标签： javalistinterface

Answer 1

它是一个接口，而不是一个实现，这意味着实际的数据结构不是固定的——它取决于实现。

List 最重要的特性是它可以保留元素添加的顺序。

如果你想要在 C 中这样的东西，你必须自己构建它（我过去做过）。您可能会使用 Java 实际用于实现的模式之一。

1. 链表。根据要求，元素链接在一起，可以是单链接的，也可以是双链接的。

2. 基于数组。很简单，尽管您可能需要在列表已满时提供数组的扩展（因此您需要将数组包装在另一个结构中）。

权衡是这样的：链表解决方案允许以恒定成本进行插入和删除，而数组解决方案可能需要移动数据以在除尾部之外的任何位置进行插入和删除。数组解决方案允许恒定时间索引，而通过索引查找条目对于链表来说是 O(n)。

Java 等价物称为 LinkedList 和 ArrayList。这两个类都实现了 List 接口。