江苏龙网

  1. 首页 > 人文 > >

关于LinkedList的详细阐述( 二 )

f) {// 拿出头节点的值 ， 作为方法的返回值final E element = f.item;// 拿出头节点的下一个节点final Node next = f.next;//帮助 GC 回收头节点f.item = null;f.next = null;// 头节点的下一个节点成为头节点first = next;//如果 next 为空 ， 表明链表为空if (next == null)last = null;//链表不为空 ， 头节点的前一个节点指向 nullelsenext.prev = null;//修改链表大小和版本size--;modCount++;return element;}?从尾部删除节点的代码也是类似的 ， 这里就不再详细解释了 。
从源码中我们可以了解到 ， 链表结构的节点新增、删除都非常简单 ， 仅仅把前后节点的指向修改下就好了 ， 所以 LinkedList 新增和删除速度很快 。
2.3 查询节点在链表查询某一个节点是比较慢的 ， 因为需要挨个循环查找才行 ， 我们看看 LinkedList 的源码是如何寻找节点的：
// 根据链表索引位置查询节点Node node(int index) {// 如果 index 处于队列的前半部分 ， 从头开始找 ， size >> 1 是 size 除以 2 的意思 。if (index < (size >> 1)) {Node x = first;// 直到 for 循环到 index 的前一个 node 停止for (int i = 0; i < index; i++)x = x.next;return x;} else {// 如果 index 处于队列的后半部分 ， 从尾开始找Node x = last;// 直到 for 循环到 index 的后一个 node 停止for (int i = size - 1; i > index; i--)x = x.prev;return x;}}从源码中我们可以发现 ， LinkedList 并没有采用从头循环到尾的做法 ， 而是采取了简单二分法 ， 首先看看 index 是在链表的前半部分 ， 还是后半部分 。 如果是前半部分 ， 就从头开始寻找 ， 反之亦然 。 通过这种方式 ， 使循环的次数至少降低了一半 ， 提高了查找的性能 ， 这种思想值得我们借鉴 。
2.4 迭代器【关于LinkedList的详细阐述】因为 LinkedList 要实现双向的迭代访问 ， 所以我们使用 Iterator 接口肯定不行了 ， 因为 Iterator 只支持从头到尾的访问 。 Java 新增了一个迭代接口 ， 叫做：ListIterator ， 这个接口提供了向前和向后的迭代方法 ， 如下所示：
data-draft-node="block" data-draft-type="table" data-size="normal" data-row-style="normal">
迭代顺序方法
LinkedList 实现了 ListIterator 接口 ， 如下图所示：
// 双向迭代器private class ListItr implements ListIterator {private Node lastReturned;//上一次执行 next() 或者 previos() 方法时的节点位置private Node next;//下一个节点private int nextIndex;//下一个节点的位置//expectedModCount：期望版本号；modCount：目前最新版本号private int expectedModCount = modCount;…………}我们先来看下从头到尾方向的迭代：
// 判断还有没有下一个元素public boolean hasNext() {return nextIndex < size;// 下一个节点的索引小于链表的大小 ， 就有}?// 取下一个元素public E next() {//检查期望版本号有无发生变化checkForComodification();if (!hasNext())//再次检查throw new NoSuchElementException();// next 是当前节点 ， 在上一次执行 next() 方法时被赋值的 。// 第一次执行时 ， 是在初始化迭代器的时候 ， next 被赋值的lastReturned = next;// next 是下一个节点了 ， 为下次迭代做准备next = next.next;nextIndex++;return lastReturned.item;}上述源码的思路就是直接取当前节点的下一个节点 ， 而从尾到头迭代稍微复杂一点 ， 如下：
// 如果上次节点索引位置大于 0 ， 就还有节点可以迭代public boolean hasPrevious() {return nextIndex > 0;}// 取前一个节点public E previous() {checkForComodification();if (!hasPrevious())throw new NoSuchElementException();// next 为空场景：1:说明是第一次迭代 ， 取尾节点(last);2:上一次操作把尾节点删除掉了// next 不为空场景：说明已经发生过迭代了 ， 直接取前一个节点即可(next.prev)lastReturned = next = (next == null) ? last : next.prev;// 索引位置变化nextIndex--;return lastReturned.item;}


推荐阅读


上一篇：关于List集合，这份总结很全面

下一篇：微信设置“小辫子昵称”，最近火了