一、双向链表DoubleLinkedList
单向链表的缺点是只能单向查询节点，即只能从头节点不断的调用next来获取洗一个节点，如果链表中节点元素非常多，会导致查询效率低下
可以从第一个节点开始调用next往后查询，也可以从尾节点不断调用prev从后往前查询，根据查询的index是在前半段还是后半段进行查询，相比单向链表，可以节省查询时间
修改Node节点实体类，增加prev属性
public class Node<T> { public T element; public Node<T> next; public Node<T> prev; // 此处省略有参构造/无参构造/getter/setter方法 } 复制代码
将linked包中原来的LinkedList复制一份重命名为SingleLinkedList即单向链表，将LinkeListWithDummyHead重命名为SingleLinkedListWithDummyHead，再将LinkedList复制一份重命名为DoubleLinkedList即双向链表，在单向链表的基础上进行双向链表的改造
首先单向链表中除了继承来的属性外还包含了一个头节点，双向链表需要增加一个尾节点的属性
// 第一个Node节点 private Node<T> first; // 尾节点 private Node<T> last; 复制代码
第一个要修改的成员方法就是getNodeByIndex(int index)方法，单向链表中查找方式是根据头节点不断的调用getNext()或者next一个一个的查询节点，知道第index个节点，而双向链表可以先判断index是在链表的前半段还是后半段，从而选择从前往后查询还是从后往前查询
//获取指定索引对应的元素 public Node getNodeByIndex(int index){ CheckUtils.checkIndex(index,size); Node<T> node = null; if (index < size >> 1){ node = first; for (int i = 0; i < index; i++) { node = node.getNext(); } } else { node = last; for (int i = size - 1; i > index; i--) { node = node.getPrev(); } } return node; } 复制代码
第二个要修改的方法是clear方法，需要将尾节点的指向也改为null
@Override public void clear() { size = 0; first = null; last = null; } 复制代码
第三个要修改的方法是add(int index, T element)，为保证链表不断，现将新加入的节点的prev只想原来index位置节点的prev节点，新加入节点的next指向原index位置的节点
以新加入的节点为参照，下面这三句代码就完成了新节点的next指向原index位置的节点，新节点的prev指向原index-1位置的节点
Node<T> next = getNodeByIndex(index); Node<T> prev = next.prev; Node<T> node = new Node<>(element, prev, next); 复制代码
将原index-1位置节点的next指向新节点，将原来index位置的prev指向新节点
next.prev = node; prev.next = node; 复制代码
如果添加到0位置，那么这个节点就是头节点
first=node 复制代码
如果添加到最后一个，那么这个节点就是尾节点
Node<T> oldLast = last; last = new Node<T>(element, last, null); oldLast.next = last; 复制代码
如果是空链表的情况下，新加入的节点就是第一个节点
fist = last; 复制代码
add(int index, T element)方法完整代码
@Override public void add(int index, T element) { CheckUtils.checkIndex4Add(index,size); if (index == size){ Node<T> oldLast = last; last = new Node<T>(element, last, null); if (oldLast == null){ first = last; } else { oldLast.next = last; } } else { Node<T> next = getNodeByIndex(index); Node<T> prev = next.prev; Node<T> node = new Node<>(element, prev, next); if (prev == null) { first = node; } else { next.prev = node; } prev.next = node; } size++; } 复制代码
第四个修改的方法就是remove方法，首先获取index位置的节点以及上一个节点prev以及下一个节点next，删除index位置节点只需要prev的下一个节点指向next，next的上一个节点指向prev，如果删除的是头节点，那么头节点就变为next节点（指定删除节点的下一个节点），如果删除的是尾节点，那么last节点就是prev节点（指定删除节点的上一个节点）
@Override public T remove(int index) { CheckUtils.checkIndex(index,size); Node<T> node = getNodeByIndex(index); Node<T> prev = node.prev; Node<T> next = node.next; if (prev == null){ first = next; } else { prev.next = next; } if (next == null){ last = prev; } else { next.prev = prev; } size --; return node.element; } 复制代码
新建一个DoubleLinkedTest测试类，增加测试方法
public class DoubleLinkedListTest { List<Integer> linkedList = new DoubleLinkedList<>(); @Before public void init() { linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); System.out.println("初始化：" + linkedList); } @Test public void add() { linkedList.add(11); linkedList.add(34); linkedList.add(78); linkedList.add(1,99); System.out.println("执行add方法后，" + linkedList); } @Test public void remove(){ linkedList.remove(0); System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList); linkedList.remove(2); System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList); } @Test public void indexOf(){ int i = linkedList.indexOf(3); System.out.println("执行indexOf，元素3位置的索引为：" + i); } } 复制代码
执行所有方法的测试，控制台输出执行结果
二、单向循环链表
单向循环链表即单向链表的最有一个元素的next指向第一个元素
将linked包中的LinedList复制一份重命名为CircularLinkedList
首先修改add方法
@Override public void add(int index, T element) { CheckUtils.checkIndex4Add(index,size); if (index == 0){ first = new Node<T>(element,first); // 拿到最后一个节点,如果size=0就获取第一个节点 Node<T> last = (size == 0) ? first : getNodeByIndex(size - 1); last.next = first; } else { Node<T> prev = getNodeByIndex(index - 1); prev.next = new Node<>(element,prev.next); } size++; } 复制代码
第二个要修改的方法是remove方法
@Override public T remove(int index) { CheckUtils.checkIndex(index,size); Node<T> node = first; if (index == 0){ if (size == 1){ first = null; } else { Node<T> last = getNodeByIndex(size - 1); first = first.next; last.next = first; } } else { Node<T> prev = getNodeByIndex(index - 1); node = prev.next; prev.next = node.next; } size --; return node.element; } 复制代码
新建一个测试类，执行这两个方法的测试
public class CircularLinkedListTest { List<Integer> linkedList = new CircularLinkedList<>(); @Before public void init() { linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); System.out.println("初始化：" + linkedList); } @Test public void add() { linkedList.add(11); linkedList.add(34); linkedList.add(78); linkedList.add(1,99); System.out.println("执行add方法后，" + linkedList); } @Test public void remove(){ linkedList.remove(0); System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList); linkedList.remove(2); System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList); } } 复制代码
执行所有方法的测试，控制台输出如下
三、双向循环链表
复制DoubleLinekedList并重命名为DoubleCircularLinkedList，相比双向链表，双向循环链表需要对add方法和remove方法修改
add方法中往最后面添加元素的情况需要修改，双向循环链表往最后添加元素，这个元素的next需要指向first，往第一个位置添加元素的情况也需要修改
@Override public void add(int index, T element) { CheckUtils.checkIndex4Add(index,size); if (index == size){ Node<T> oldLast = last; // 最后一个位置插入元素 last = new Node<T>(element, last, first); if (oldLast == null){ first = last; // 只有一个元素的情况下,它的next和prev都指向自己 first.next = first; first.prev = first; } else { oldLast.next = last; first.prev = last; } } else { Node<T> next = getNodeByIndex(index); Node<T> prev = next.prev; Node<T> node = new Node<>(element, prev, next); next.prev = node; prev.next = node; if (next == first) { // index == 0 first = node; } } size++; } 复制代码
针对remove方法进行修改
@Override public T remove(int index) { CheckUtils.checkIndex(index,size); Node<T> node = first; if (size == 1){ first = null; last = null; } else { node = getNodeByIndex(index); Node<T> prev = node.prev; Node<T> next = node.next; prev.next = next; prev.prev = prev; if (node == first) { first = next; } if (node == last){ last = prev; } } size --; return node.element; } 复制代码
增加测试类
public class DoubleCircularLinkedListTest { List<Integer> linkedList = new DoubleCircularLinkedList<>(); @Before public void init() { linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(4); System.out.println("初始化：" + linkedList); } @Test public void add() { linkedList.add(11); linkedList.add(34); linkedList.add(78); linkedList.add(1,99); System.out.println("执行add方法后，" + linkedList); } @Test public void remove(){ linkedList.remove(0); System.out.println("执行remove方法删除索引0位置的元素后，" + linkedList); linkedList.remove(2); System.out.println("再次执行remove方法删除索引2位置的元素后，" + linkedList); } } 复制代码
执行测试
