数组是编程语言中提供的很有用的数据结构。但它有至少2个局限（1）若改变数组的大小，就要新建一个数据，并需要从原数组中复制所有的数据到新数组中（2） 数组中在内存中是依次连续存储的，这意味着插入一条数据，要移动数组中的其他数据。这一局限可以通过链式结构解决。链式结构是存储数据的节点以及指向其他节点的链指针的集合
链表的定义：如果一个节点包含指向另一个节点的数据域，那么多个节点可以串在一起，仅仅用一个节点就可以访问整个节点序列，这样一个节点就是最常用的链表。其数据结构是由节点组成，每一个节点保存一些信息和指向表中另一个节点的引用
如果每个节点仅包含其后节点的一个引用，则该表为单向链表
我们用单链表演示一个实例：
创建了一个单链表的节点
删除尾部的节点
我们看这个方法会发现，我们无法立即找到tail的前驱节点，只能通过遍历的方法来寻找，这会严重妨碍处理链表的速度。为了避免这个问题，我们使每一个节点，有两个引用域，一个指向前驱节点，一个指向后继节点。这种类型的节点成为双向链表
java中LinkedList使用的就是双向链表，我们打开LinkedList的源码看一下
第一句就表明了LinkedList是实现List接口的双向链表
网友评论