版权声明：尊重博主原创文章，转载请注明出处哦~
在第一章的数组中，我们看到数组作为数据存储结构有一定的缺陷。在无序数组中，搜索时低效的；而在有序数组中，插入效率又很低；不管在哪一种数组中删除效率都很低。况且一个数组创建后，它的大小是无法改变的。
在本章中，我们将讨论下链表这个数据结构，它可以解决上面的一些问题。链表可能是继数组之后第二种使用得最广泛的通用数据结构了。本章主要讨论单链表和双向链表。
顾名思义，单链表只能从表头到表尾的顺序，每个节点中保存了指向下一个节点的指针；双向链表则可以反向遍历，因为节点中既保存了向后节点的指针，又保存了向前节点的指针。由于链表结构相对简单，这里不再赘述，直接通过程序来查看它们常见的操作：
单链表
双向链表
在表头插入和删除速度很快，仅需改变一两个引用值，所以话费O(1)的时间。平均起来，查找、删除和在指定节点后面插入都需要搜索链表中的一半节点，需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表仍然要比数组快一些，因为当插入和删除节点时，链表不需要移动任何东西，增加的效率是很显著的，特别是当复制时间远远大于比较时间的时候。
当然，链表比数组优越的另一个重要方面是链表需要多少内存就可以用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了，所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。可变数组可以解决这个问题，但是它经常只允许以固定大小的增量扩展，这个解决方案在内存使用率上来说还是比链表要低。
链表比较简单，就讨论这么多，如有问题，欢迎留言指正~
·END·
Java菜鸟集训营分享是一种快乐
白癜风早期可以治愈吗白癜风治疗方法最好