Version: Next

虚拟头节点

  • 有时候，为了让代码更精简，统一所有节点的处理逻辑，可以在最前面加上一个虚拟的头节点（不存储数据）

image-20200916134540140

改造MyLinkedList类

添加虚拟头节点，添加构造方法

添加虚拟头结点

  • 添加一个构造函数
public MyLinkedList() {
first = new LinkedListNode<E>(null, null);
}

修改node(int index)方法

  • 修改前
private LinkedListNode<E> node(int index) {
rangeCheck(index);
LinkedListNode<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
  • 修改后——从first.next开始
private LinkedListNode<E> node(int index) {
rangeCheck(index);
LinkedListNode<E> node = first.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}

修改add(int index, E element)方法

  • 修改前
// 向index位置插入一个元素
public void add(int index, E element) {
if (index == 0) {
first = new LinkedListNode<>(element, first);
} else {
LinkedListNode<E> preNode = node(index - 1);
preNode.next = new LinkedListNode<>(element, preNode.next);
}
size++;
}
  • 修改后——如果传入index为0，直接把虚拟节点赋给前一个节点
// 向index位置插入一个元素
public void add(int index, E element) {
LinkedListNode<E> preNode = index == 0 ? first : node(index - 1);
preNode.next = new LinkedListNode<>(element, preNode.next);
size++;
}

修改remove(int index)方法

  • 修改前
// 移除index位置的元素并返回
public E remove(int index) {
E removedElement = null;
if (index == 0) {
removedElement = first.element;
first = first.next;
} else {
LinkedListNode<E> preNode = node(index - 1);
removedElement = preNode.next.element;
preNode.next = preNode.next.next;
}
size--;
return removedElement;
}
  • 修改后——如果传入的index为0，直接将前驱节点设置为虚拟节点
// 移除index位置的元素并返回
public E remove(int index) {
E removedElement = null;
LinkedListNode<E> preNode = index == 0 ? first : node(index - 1);
removedElement = preNode.next.element;
preNode.next = preNode.next.next;
size--;
return removedElement;
}