Java中list为什么有序？

作者：麦穗星
链接：https://www.zhihu.com/question/468756770/answer/1980061276
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

List底层有两种实现方式：基于数组（ArrayList）和基于链表（LinkedList）。

首先要明确的是：既然前提是「有序」，那么有序的表现是什么？就是在遍历元素的时候其顺序与添加的顺序是一致的，因此应该使用默认的add操作，不能随便指定位置插入，否则即使用的是List也不能表现出有序的特征！

1）数组：是一种紧凑的数据结构，占用的是一块连续的内存，每个元素都挨个排列，可以通过索引快速获取指定位置的元素，一般情况下添加元素时按照从左往右顺序添加，因此它是有序的。

2）链表：在内存中是不连续的，但是其中的每个节点都有个变量记录了该节点的下一个节点（简单起见这里用单向链表举例）：

N1 -> N2 -> … -> Nn

选定一个节点，就能通过该节点的next指针（变量）找到下一个节点。

而链表插入操作一般是边界操作（头/尾插入），只要插入操作调用的方法一样，就能保证其中元素的顺序与插入时一致。

题外话：

我们都知道HashSet（这里强调HashSet，是因为Set并不一定是无序的，要注意实现）是无序且不允许重复的，它基于HashMap，基本就是直接调用HashMap的API，而HashMap的元素的存储位置是根据元素（对象）的hashCode: int计算所得，可能先添加的元素hashCode比较大，而后添加的元素hashCode比较小，因此造成添加顺序与实际元素顺序不符的情况，这就是无序。

总结：

• List只是具备有序的性质，但是否有序依然要视具体的操作来定；
• HashSet天然无序，它不受调用方式、插入顺序的影响，只以hashCode决定元素位置。