【数据结构】线性表 ⑥ ( 双循环链表 |
您所在的位置：网站首页 › 线性链表的基本操作 › 【数据结构】线性表 ⑥ ( 双循环链表 |
【数据结构】线性表 ⑥ ( 双循环链表
|
文章目录
一、双循环链表插入操作处理二、双循环链表删除操作处理三、LinkedList 双循环链表源码分析1、链表节点2、LinkedList 链表中收尾元素指针3、链表插入操作4、链表向指定位置插入操作5、获取指定索引的元素6、删除指定索引的元素
一、双循环链表插入操作处理
双循环链表 中 , 需要对 插入 / 删除 / 遍历 操作 进行特殊处理 , 因为需要调节 前驱指针 和 后继指针 两个指针 ; 如 : 双循环链表 中 , 如果要插入元素 , 将 c 节点 插入到 a 节点 和 b 节点 之间 , 当前的状态是 a 的后继指针 指向 b , b 的前驱指针指向 a ; 如果要实现插入 c 元素 , 则需要 将 a 的 后继指针 指向 c ,将 c 的 前驱指针 指向 a ,将 c 的 后继指针 指向 b ,将 b 的 前驱指针 指向 c ;插入节点操作 需要执行四个步骤 : ① 将 c 的 前驱指针 指向 a② 将 a 的 后继指针 指向 c③ 将 c 的 后继指针 指向 b④ 将 b 的 前驱指针 指向 c
二、双循环链表删除操作处理
下面的链表插入成功 , 顺序为 a , c , b ,
如果要删除双循环链表中的 c 元素 , 只需要将 a 元素的 后继指针 指向 b , 将 b 元素的 前驱指针 指向 a 即可 ; c 元素没有指针指向后 , 会自动被内存回收 ; 三、LinkedList 双循环链表源码分析LinkedList 源码地址 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java 1、链表节点LinkedList 链表是一个 双循环链表 , 下面的 Node 类 , 就是双循环链表的 节点 ; private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#1021 2、LinkedList 链表中收尾元素指针在 LinkedList 双循环链表中 , 维护了 首元素节点指针 transient Node first , 尾元素节点指针 transient Node last , 分别指向 首尾元素 ; transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node last; 3、链表插入操作LinkedList 双循环链表 调用 add 方法 添加元素 , 在其中调用了 linkLast 函数 , 将元素插入到了队尾 ; /** * 将指定的元素追加到此列表的末尾。 * *这个方法等价于 {@link #addLast}. * * @param e 元素添加到此列表 * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; } 源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#354 在 linkLast 函数中 , 创建了新的节点 , 将数据设置到了新节点中 , 最后将新节点设置为 尾部节点 ; 注意 , 设置新的尾部节点时 , 首先 , 保存原来的尾部节点指针 ( 现在不保存 , 之后访问不到了 ) ;然后 , 将新的节点设置为 尾部节点 ;最后 , 将原来的 尾部节点 的后继指针 指向新插入的节点 ; /** * 链接作为最后一个元素。 */ void linkLast(E e) { // 先保存尾结点的指针 final Node l = last; // 创建一个新节点 , 将数据插入到新节点中 final Node newNode = new Node(l, e, null); // 将新节点赋值给 尾部元素节点指针 last = newNode; if (l == null) // 链表是空的 , 该节点是插入的第一个节点 first = newNode; else // 链表不为空 , 该节点是插入的除第一个节点之外的后续节点 l.next = newNode; size++; modCount++; }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#147 4、链表向指定位置插入操作调用 LinkedList 的 public void add(int index, E element) 函数 , 可以向指定索引添加元素 , 如果添加的非末尾元素 , 则调用 linkBefore 函数 向 链表 中插入数据 ; /** * 将指定元素插入此列表中的指定位置。 * 将当前在该位置的元素(如果有的话) * 和任何后续元素向右移动(在它们的索引上加1)。 * * @param index 要插入指定元素的索引 * @param element 要插入的元素 * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { // 检查索引合法性 checkPositionIndex(index); if (index == size) // 如果是添加到末尾 linkLast(element); else // 如果是添加到非末尾的元素 linkBefore(element, node(index)); }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#532 void linkBefore(E e, Node succ) 函数 , 是将 E 数据对应的节点插入到 Node succ 数据之前 ; /** * 在非空节点 succ 前插入元素 e */ void linkBefore(E e, Node succ) { // assert succ != null; // 获取 succ 节点 前驱节点 final Node pred = succ.prev; // 新建要插入的节点 final Node newNode = new Node(pred, e, succ); // 前驱节点 的 后继指针 指向 新节点 succ.prev = newNode; if (pred == null) // 如果插入的 是 首元素节点 first = newNode; else // 后继节点 的 前驱指针 指向新节点 pred.next = newNode; size++; modCount++; }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#163 5、获取指定索引的元素LinkedList 中 , 调用 public E get(int index) 函数 , 获取指定索引的元素 ; checkElementIndex 函数的作用是 检查该索引是否合法 ; node 函数就是获取 双循环链表 元素的方法 ; /** * 返回列表中指定位置的元素。 * * @param index 要返回的元素的索引 * @return 在此列表中指定位置的元素 * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#500 Node node(int index) 函数的核心操作 , 就是执行 index - 1 次 循环 , 找到对应的节点并返回 ; 在执行前 判定 index 靠近 首元素 还是 尾部元素 , 如果 index < (size >> 1) 可以判定为 index 处于前半部分 ; 如果 index 靠近 首部元素 , 则正向遍历 ;如果 index 靠近 尾部元素 , 则逆向遍历 ; /** * 返回指定元素索引处的(非空)节点。 */ Node node(int index) { // assert isElementIndex(index); if (index > 1)) { Node x = first; // 从前往后遍历 for (int i = 0; i checkElementIndex(index); return unlink(node(index)); }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#551 unlink 函数中 , 先获取要删除节点的 前驱节点 和 后继节点 , 然后 执行下面两个操作 : 前驱节点 的 后继指针 指向 后继节点 ;后继节点 的 前驱指针 指向 前驱节点 ; /** * Unlinks non-null node x. */ E unlink(Node x) { // assert x != null; final E element = x.item; // 获取节点的 前驱节点 final Node next = x.next; // 获取节点的 后继节点 final Node prev = x.prev; if (prev == null) { first = next; } else { // 前驱节点 的 后继指针 指向 后继节点 prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { // 后继节点 的 前驱指针 指向 前驱节点 next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }源码参考 : https://www.androidos.net.cn/android/9.0.0_r8/xref/libcore/ojluni/src/main/java/java/util/LinkedList.java#220 |
【本文地址】
今日新闻 |
推荐新闻 |