为什么说单向链表是无序的？

Question

单向链表遍历的时候不应该从头部开始遍历到尾部，每个节点都有一个尾指针指向下一个节点，这样子看起来不应该是有序的吗，为什么会说是无序的，即存储元素和取出元素有可能不一样；那为什么双向链表就能保证，双向链表多了一个头指针指向前一个节点，除了查询快点外有什么很明显的区别吗？
还有在书上我看到了说： 在Java程序设计语言中，所有的链表实际上都是双向链接。有大佬解释一下吗，LinkedList、LinkedHashSet、LinkedHashMap类是双向链表，那不是还有HashSet,HashMap底层不是数组+单向链表吗？

Answer 1

因为问题不成立，并没有这种说法。

你要非说无序的话，那只能是内存上是无序的了，但这跟是单是双也没关系啊。

英文里面提 Ordered Link List 或者 Sorted Link List，一般指的是各个节点按照某种方式排序（比如从大到小），但这是人为写出来的代码，不是链表本身的特性，所以从这个角度上看，其实无论单双链表，都可以有序也可以无序。

---

双链表的缺点 @芒果zzZ 提到内存额外的占用了，但你要知道这种数据结构那都是上个世纪就有的产物了，九十年代 512KB 那都是大内存了，而且贵的离谱。其实很多现在看到稀奇古怪的做法，都是当时程序员们为了节省内存而想出的办法。现如今除非你是做某些特殊设备的嵌入式开发，内存容量很小，否则这点开支已经不算什么了。

要再非说一个缺点可能也就是双链表实现起来比单链表要复杂了……

---

最后那句话不知道你是在哪本书看的？

Answer 2

这个应该是很多人的疑问吧。

首先没有理由证明任意单链表是无序的。而且这个无序定义也很模糊，到底是按插入顺序是无序，还是按大小排序是无序，都没有说明，

双向链表比单向链表相比在于双向链表可以逆向查找，无论是从编码还是速度都是要更加舒服的，当然内存就。。。

Java中只是有一部分的实现是双向链表而已，HashMap肯定是数组+单链表+红黑数啊，HashMap的链表只是为了避免Hash冲突而已，没必要去实现双向链表。