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

48uugxga
  • 23

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

回复
阅读 704
2 个回答

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

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

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


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

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


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

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

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

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

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

你知道吗?

宣传栏