双向链表

• 一、双向链表
• 补充【List接口 和 AbstractList抽象类】
• 二、设计双向链表
• 三、双向链表的实现
• • 1. 查询节点
  • 2. 插入节点
  • 3. 删除节点
  • 4. 清空节点
• 四、双向链表 vs 动态数组

一、双向链表

1. 与单向链表不同的是，双向链表多了 从后向前的指向
2. 使用双向链表可以加快节点的查询速度

补充【List接口 和 AbstractList抽象类】

List接口：

public interface List {static final int ELEMENT_NOT_FOUND = -1;/*** 清除所有元素*/void clear();/*** 元素的数量* @return*/int size();/*** 是否为空* @return*/boolean isEmpty();/*** 是否包含某个元素* @param element* @return*/boolean contains(E element);/*** 添加元素到尾部* @param element*/void add(E element);/*** 获取index位置的元素* @param index* @return*/E get(int index);/*** 设置index位置的元素* @param index* @param element* @return 原来的元素ֵ*/E set(int index, E element);/*** 在index位置插入一个元素* @param index* @param element*/void add(int index, E element);/*** 删除index位置的元素* @param index* @return*/E remove(int index);/*** 查看元素的索引* @param element* @return*/int indexOf(E element);
}

AbstractList抽象类：

public abstract class AbstractList implements List  {/*** 元素的数量*/protected int size;/*** 元素的数量* @return*/public int size() {return size;}/*** 是否为空* @return*/public boolean isEmpty() {return size == 0;}/*** 是否包含某个元素* @param element* @return*/public boolean contains(E element) {return indexOf(element) != ELEMENT_NOT_FOUND;}/*** 添加元素到尾部* @param element*/public void add(E element) {add(size, element);}protected void outOfBounds(int index) {throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);}protected void rangeCheck(int index) {if (index < 0 || index >= size) {outOfBounds(index);}}protected void rangeCheckForAdd(int index) {if (index < 0 || index > size) {outOfBounds(index);}}
}

二、设计双向链表

• 与单项链表不同的是，双向链表增加了 last 指针，同时节点增加了向前的指向 prev 属性
  

public class DoubleLinkedList extends AbstractList {private Node first;// 增加 last 节点private Node last;private static class Node{E element;Node next;//增加上一个节点Node prev;public Node(Node prev, E element, Node next){this.element = element;this.next = next;this.prev =prev;}}
}

三、双向链表的实现

• 相较于单向链表，双向链表需要重写实现 查询节点 、 插入节点 、 删除节点 、 清空节点 这四个方法

1. 查询节点

1. 因为是双向链表，所以查询节点可以从后向前查询
2. 查询节点的方向可以根据节点总数的一半，即 size >> 1 为分隔，索引小于一半的从前向后查询，索引大于等于一半的从后往前查询

private Node node(int index){rangeCheck(index);// 根据节点数量的一半进行区分if(index < (size >> 1)){Node node =first;// 小于size >> 1的节点从前向后查询for (int i = 0; i < size; i++){node = node.next;}return node;}else {Node node = last;// 大于等于 size >> 1 的节点从后向前查询for(int i = size-1; i > index; i--){node = node.prev;}return node;}
}

2. 插入节点

1. 插入节点，就是在两个节点之间加入新的节点
2. 首先要找到需要插入节点位置的原节点，原节点要成为新节点的下一个节点
3. 原节点的上一个节点成为新节点的上一个节点
   

public void add(int index,E element){// 新节点后的下一个节点, 就是原链表 index 位置的节点Node next = node(index);// 新节点后的上一个节点, 就是原链表 index-1 位置的节点Node prev = next.prev;// 创建新节点, 新节点的上一个节点时prev, 新节点的下一个节点是nextNode node = new Node<>(prev, element, next);// next的上一个节点是新节点next.prev = node;// prev的下一个节点是新节点prev.next = node;
}

4. 当新插入的节点索引为 0 时， 需要做特殊处理，因为 first 引用着 0 节点
   

public void add(int index,E element){// 新节点后的下一个节点, 就是原链表 index 位置的节点Node next = node(index);// 新节点后的上一个节点, 就是原链表 index-1 位置的节点Node prev = next.prev;// 创建新节点, 新节点的上一个节点时prev, 新节点的下一个节点是nextNode node = new Node<>(prev, element, next);// next的上一个节点是新节点next.prev = node;// 当next.prev == null时, 说明新添加节点的索引是0if (next.prev == null) {// 此时first应该指向引得索引first = node;}else {// prev的下一个节点是新节点prev.next = node;}
}

5. 当插入的节点位置是链表的最后时，因为 last 属性引用最后一个节点，所以也需要做特殊处理

【已有元素：index = size && last != null】

【没有元素：index = size && last == null】

7. 最终的插入方法如下代码，

public void add(int index,E element){rangeCheckForAdd(index);// 如果 index == size, 说明添加的索引是最后位置if (index == size) {Node oldLast = last;// 新创建节点, 新节点的next = null, prev = 之前的最后节点last = new Node<>(oldLast, element, null);// 旧链表的最后节点的下一个节点是 新创建的节点oldLast.next = last;}else {// 添加新节点后的下一个节点Node next = node(index);// 添加新节点后的上一个节点Node prev = next.prev;// 创建新节点, 新节点的上一个节点时prev, 新节点的下一个节点是nextNode node = new Node<>(prev, element, next);// next的上一个节点是新节点next.prev = node;// 当next.prev == null时, 说明新添加节点的索引是0if (next.prev == null) {first = node;}else {// prev的下一个节点是新节点prev.next = node;}}size++;
}

3. 删除节点

1. 删除节点, 只需要让被删除节点的前一个节点与后一个节点之间相互联系, 同时去掉所有对被删除节点引用即可
2. 需要注意的是, 查出 第0个节点 和 最后一个节点要特殊处理

【删除中间元素】

【删除头/尾节点元素】

public E remove(int index){// 需要删除的节点Node node = node(index);// 删除节点的前一个节点Node prev = node.prev;// 删除节点的后一个节点Node next = node.next;// 删除节点, 只需要去掉对这个节点的引用即可// 如果prev == null, 说明删除的是第一个节点if (prev == null) {first = next;}else {prev.next = next;}// 如果next == null, 说明删除的是最后一个节点if (next == null) {last = prev;}else {next.prev = prev;}size--;return node.element;
}

4. 清空节点

• 清空节点，需要将 first 和 last 的引用全部断开

public void clear() {size = 0;first = null;last = null;
}

四、双向链表 vs 动态数组