Version: Next

双向链表

特征
  • 双向链表的成员变量包括
    • size：节点数目
    • first：指向头结点
    • last：指向尾结点
  • 双向链表的节点成员属性包括：
    • element：节点值
    • prev：指向前一个节点
    • next：指向下一个节点

image-20200917093233962

双向链表节点

private static class BiLinkedListNode<E> {
E element;
BiLinkedListNode<E> next;
BiLinkedListNode<E> prev;
public BiLinkedListNode() {
}
public BiLinkedListNode(E element, BiLinkedListNode<E> prev, BiLinkedListNode<E> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
if (prev == null) {
stringBuilder.append("[null]");
} else {
stringBuilder.append("[").append(prev.element).append("]");
}
stringBuilder.append("[").append(element).append("]");
if (next == null) {
stringBuilder.append("[null]");
} else {
stringBuilder.append("[").append(next.element).append("]");
}
return stringBuilder.toString();
}
}

双向链表成员变量

public class BiLinkedList<E> {
private static final int ELEMENT_NOT_FOUND = -1;
private int size = 0;
private BiLinkedListNode<E> first;
private BiLinkedListNode<E> last;
//...
}

node(int index)方法

给定index，返回对应的节点对象

与单向链表的区别
  • 在单向链表中，只能从一个方向遍历查找一个节点
  • 在双向链表中，可以通过判断，决定从头还是从尾开始遍历查找节点，这样可以减少遍历的总节点数
    • index小于size的一半，从头节点开始遍历
    • index大于size的一半，从尾节点开始遍历
private BiLinkedListNode<E> node(int index) {
rangeCheck(index);
BiLinkedListNode<E> node;
if (index < (size >> 1)) { // 正向遍历
node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
} else { // 反向遍历
node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
}
return node;
}

toString方法

@Override
public String toString() {
StringBuilder result = new StringBuilder("BiLinkedList{" +
"size=" + size + " | ");
if (first == null) { // 如果链表为空，不遍历直接打印空
result.append("null }");
return result.toString();
}
BiLinkedListNode<E> node = first;
while (node.next != null) {
result.append(node).append(" <-> ");
node = node.next;
}
result.append(node).append("}");
return result.toString();
}

get(int index)方法

不需要修改

// 返回index位置对应的元素
public E get(int index) {
return node(index).element;
}

set(int index, E element)方法

不需要修改

// 设置Index位置的元素
public E set(int index, E element) {
BiLinkedListNode<E> node = node(index);
E old = node.element;
node.element = element;
return old;
}

clear方法

需要将尾结点引用置空，链表才能被垃圾回收器回收

// 清除所有元素
public void clear() {
size = 0;
first = null;
last = null;
}

add(int index, E element)方法

  • 找到index对应节点
  • 获取index节点的前一个和后一个
  • 创建要插入的节点，设置前一个节点为index的前一个节点，后一个节点为index
  • 将前一个节点的next设置为要插入的节点
  • 将下一个节点的prev设置为要插入的节点
// 向index位置插入一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
// 找到index对应的节点
BiLinkedListNode<E> node = node(index);
BiLinkedListNode<E> preNode = node.prev; // 前一个节点
// 创建要插入的节点
BiLinkedListNode<E> insertNode = new BiLinkedListNode<>(element, preNode, node);
// 前一个节点的next指向要插入的节点
preNode.next = insertNode;
// 后一个节点的prev指向要插入的节点
node.prev = insertNode;
size++;
}
处理边界情况
  • 在开头插入
    • 则不存在前驱节点，必须进行判断，否则会产生空指针
    • 插进去的节点就是头节点，因此要将链表的first指向插入的节点
  • 在尾巴插入
    • 相当于index的值等于size值的情况
    • 插入节点的next为null
    • 插入节点的prev为先前双向链表的last
    • 新插入的节点变成了新的last
    • 先前last的next指向新插入的节点
  • 在尾巴插入，且当前链表为空
    • size为0，插入了一个节点，那么这个节点是唯一的节点，first、last都是它
// 向index位置插入一个元素
public void add(int index, E element) {
rangeCheckForAdd(index);
// 在最后面插入
if (index == size) {
// 在最后面插入新节点，新节点的next为空，prev为上一个last
// 最终插进去的节点变为了新的last
last = new BiLinkedListNode<>(element, last, null);
if (size == 0) { // 链表为空
first = last; // 唯一一个节点，头 尾都是它
} else {
// 先前last的next指向新插入节点，也就是新的last节点
last.prev.next = last;
}
} else { // 不是在最后面插入
// 找到index对应的节点
BiLinkedListNode<E> node = node(index);
BiLinkedListNode<E> preNode = node.prev; // 前一个节点
// 创建要插入的节点
BiLinkedListNode<E> insertNode = new BiLinkedListNode<>(element, preNode, node);
if (preNode == null) { // 在最开头插入
first = insertNode;
} else {
// 前一个节点的next指向要插入的节点
preNode.next = insertNode;
}
// 后一个节点的prev指向要插入的节点
node.prev = insertNode;
}
size++;
}

remove(int index)方法

  • 找到index对应的节点node
  • node.prev的next指向node.next
  • node.next的prev指向node.prev
  • size--
// 移除index位置的元素并返回
public E remove(int index) {
BiLinkedListNode<E> node = node(index);
E removedElement = node.element;
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
return removedElement;
}
边界情况
  • 删除的元素是第一个元素
    • first指向node的next
    • node的next节点的prev指向null
  • 删除的元素是最后一个
    • last指向node的prev
    • node的prev节点的next指向null
  • 链表只有一个元素
    • first设置为null， last设置为null
// 移除index位置的元素并返回
public E remove(int index) {
BiLinkedListNode<E> node = node(index);
E removedElement = node.element;
if (size == 1) { // 删除唯一节点
first = null;
last = null;
} else if (node == first) { // 删除的是头结点
first = node.next;
node.next.prev = null;
} else if (node == last) { // 删除的是尾结点
last = node.prev;
node.prev.next = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
size--;
return removedElement;
}