GitHub:https://github.com/UniqueDong/algorithms.git
上一篇《链表导论心法》讲解了链表的理论知识以及链表操作的实现原理。talk is cheap, show me the code ! 今天让我以一起把代码撸一遍，在写代码之前一定要根据上一篇的原理多画图才能写得好代码。举例画图，辅助思考。
- 比如插入节点，在已知节点 b 的前面插入 x
废话少说，撸起袖子干。
接口定义
首先我们定义链表的基本接口,为了显示出 B 格，我们模仿我们 Java 中的 List 接口定义。
package com.zero.algorithms.linear.list; public interface List<E> { /** * Returns <tt>true</tt> if this list contains no elements. * * @return true if this list contains no elements */ boolean isEmpty(); /** * Returns the number of elements in this list. * * @return the number of elements in this list */ int size(); /** * Returns the element at the specified position in this list. * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ E get(int index); /** * Appends the specified element to the end of this list (optional operation). * * @param e element to be appended to this list * @return */ boolean add(E e); /** * Inserts the specified element at the specified position in this list * (optional operation). Shifts the element currently at that position * (if any) and any subsequent elements to the right (adds one to their * indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted */ void add(int index, E element); /** * return true if this list contains the specified element * * @param o element whose presence in this list is to be tested * @return true if this list contains the specified element */ boolean contains(Object o); /** * Removes the first occurrence of the specified element from this list, * if it is present (optional operation). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ boolean remove(Object o); /** * Removes the element at the specified position in this list (optional * operation). Shifts any subsequent elements to the left (subtracts one * from their indices). Returns the element that was removed from the * list. * * @param index the index of the element to be removed * @return the element previously at the specified position */ E remove(int index); /** * Returns the index of the first occurrence of the specified element * in this list, or -1 if this list does not contain the element. * More formally, returns the lowest index <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, * or -1 if there is no such index. * * @param o element to search for * @return the index of the first occurrence of the specified element in * this list, or -1 if this list does not contain the element */ int indexOf(Object o); }
抽象链表模板
看起来是不是很像骚包，接着我们再抽象一个抽象类，后续我们还会继续写双向链表，循环链表。双向循环链表。把他们的共性放在抽象类中，将不同点延迟到子类实现。
package com.zero.algorithms.linear.list; public abstract class AbstractList<E> implements List<E> { protected AbstractList() { } public abstract int size(); /** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public abstract void addFirst(E e); @Override public boolean isEmpty() { return size() == 0; } public void add(int index, E element) { throw new UnsupportedOperationException(); } public E remove(int index) { throw new UnsupportedOperationException(); } /** * check index * @param index to check */ public final void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Tells if the argument is the index of a valid position for an * iterator or an add operation. */ private boolean isPositionIndex(int index) { return index >= 0 && index <= size(); } /** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */ private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size(); } public final void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size(); } }
Node 节点
单向链表的每个节点有两个字段，一个用于保存当前节点的数据 item，另外一个则是 指向下一个节点的 next 指针。所以我们在单向链表定义一个静态内部类表示 Node 节点。
构造方法分别将数据构建成 Node 节点，默认 next 指针是 null。
/** * Node data * * @param <E> */ private static class Node<E> { /** * Node of data */ E item; /** * pointer to next Node */ Node<E> next; public Node(E item, Node<E> next) { this.item = item; this.next = next; } public Node(E item) { this(item, null); } }
单项链表，size 属性保存当前节点数量，Node<E> head指向 第一个节点的指针，并且存在
(head == null && last == null) || (head.prev == null && head.item !=null)
是真事件。以及 last指针指向最后的节点。最后我们还要重写 toString 方法，便于测试。
代码如下所示：
public class SingleLinkedList<E> extends AbstractList<E> { transient int size = 0; /** * pointer to head node */ transient Node<E> head; /** * pointer to last node */ transient Node<E> last; public SingleLinkedList() { } @Override public String toString() { StringBuilder sb = new StringBuilder(); Node<E> cur = this.head; while (Objects.nonNull(cur)) { sb.append(cur.item).append("->"); cur = cur.next; } sb.append("NULL"); return sb.toString(); } }
添加元素
添加元素可能存在三种情况：
- 头结点添加。
- 中间任意节点添加。
- 尾节点添加。
在尾节点添加
将数据构造成 newNode 节点，将原先的 last 节点 next 指向 newNode 节点，如果 last 节点是 null 则将 head 指向 newNode ，同时 size + 1。
public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element * * @param e data */ private void linkLast(E e) { // 先取出原 last node final Node<E> l = last; final Node<E> newNode = new Node<>(e); // 修改 last 指针到新添加的 node last = newNode; // 如果原 last 是 null 则将 newNode 设置为 head，不为空则原 last.next 指针 = newNode if (Objects.isNull(l)) { head = newNode; } else { l.next = newNode; } size++; }
在头结点添加
将数据构造成 newNode 节点，同时 newNode.next 指向原先 head节点，并将 head 指向 newNode 节点，如果 head == null 标识当前链表还没有数据，将 last 指针指向 newNOde 节点。
@Override public void addFirst(E e) { final Node<E> h = this.head; // 构造新节点,next 指向原先的 head final Node<E> newNode = new Node<>(e, h); head = newNode; // 如果原先的 head 节点为空，则 last 指针也指向新节点 if (Objects.isNull(h)) { last = newNode; } size++; }
在指定位置添加
分两种情况，当 index = size 的时候意味着在最后节点添加，否则需要找到当前链表指定位置的节点元素，并在该元素前面插入新的节点数据，重新组织两者节点的 next指针。
linkLast 请看前面，这里主要说明 linkBefore。
首先我们先查询出 index 位置的 Node 节点，并将 newNode.next 指向 该节点。同时还需要找到index 位置的上一个节点，将 pred.next = newNode。这样就完成了节点的插入，我们只要画图辅助思考就很好理解了。
@Override public void add(int index, E element) { checkPositionIndex(index); if (index == size) { linkLast(element); } else { linkBefore(element, index); } } /** * Inserts element e before non-null Node of index. */ void linkBefore(E element, int index) { final Node<E> newNode = new Node<>(element, node(index)); if (index == 0) { head = newNode; } else { Node<E> pred = node(index - 1); pred.next = newNode; } size++; } /** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { Node<E> x = this.head; for (int i = 0; i < index; i++) { x = x.next; } return x; }
判断是否存在
indexOf(Object o) 用于查找元素所在位置，若不存在则返回 -1。
@Override public boolean contains(Object o) { return indexOf(o) != -1; } @Override public int indexOf(Object o) { int index = 0; if (Objects.isNull(o)) { for (Node<E> x = head; x != null; x = x.next) { if (x.item == null) { return index; } index++; } } else { for (Node<E> x = head; x != null; x = x.next) { if (o.equals(x.item)) { return index; } index++; } } return -1; }
查找方法
根据 index 查找该位置的节点数据，其实就是遍历该链表。所以这里的时间复杂度是 O(n)。
@Override public E get(int index) { return node(index).item; }
删除节点
删除有两种情况，分别是删除指定位置的节点和根据数据找到对应的节点删除。
先来看第一种根据 index 删除节点:
先检验 index 是否合法，然后根据 index 找到待删除 node。这里的删除比较复杂，老铁们记得多画图来辅助理解，防止出现指针指向错误造成意想不到的结果。
@Override public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public final void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size(); }
最难理解的就是后面这段代码了，但是只要多画图，多思考就好多了。
x节点就是当前要删除的节点数据，我们先把该节点保存的item以及next指针保存到临时变量。 第 10 ~13 这块 while 循环主要是用于找出被删除节点的 引用 cur 以及上一个节点的引用 prev。- 在找到被删除的 cur 指针以及 cur 上一个节点指针 prev 后我们做删除操作，这里有三种情况：当链表只有一个节点的时候，当一个以上节点情况下分为删除头结点、尾节点、其他节点。
/** * Unlinks non-null node x. */ E unlink(Node<E> x) { final E item = x.item; final Node<E> next = x.next; Node<E> cur = head; Node<E> prev = null; // 寻找被删除 node cur 节点以及 cur 的上一个节点 prev while (!cur.item.equals(item)) { prev = cur; cur = cur.next; } // 当只有一个节点的时候 prev = null,next = null // 如果删除的是头结点，则 head = x.next，否则 prev.next = next 打断与被删除节点的联系 if (prev == null) { head = next; } else { prev.next = next; } // 如果删除最后一个节点，则 last 指向 prev，否则打断被删除的节点 next = null if (next == null) { last = prev; } else { x.next = null; } size--; x.item = null; return item; }
单元测试
我们使用 junit做单元测试，引入maven 依赖。
<dependencies> <dependency> <groupId>org.junit.jupiter</groupId> <artifactId>junit-jupiter-engine</artifactId> <version>5.5.2</version> <scope>test</scope> </dependency> <dependency> <groupId>org.junit.jupiter</groupId> <artifactId>junit-jupiter-params</artifactId> <version>5.5.2</version> <scope>test</scope> </dependency> </dependencies>
创建测试用例
package com.zero.linkedlist; import com.zero.algorithms.linear.list.SingleLinkedList; import org.junit.jupiter.api.*; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.ValueSource; @DisplayName("单向链表测试") public class SingleLinkedListTest { SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>(); @BeforeAll public static void init() { } @AfterAll public static void cleanup() { } @BeforeEach public void tearup() { System.out.println("当前测试方法开始"); System.out.println(singleLinkedList.toString()); } @AfterEach public void tearDown() { System.out.println("当前测试方法结束"); System.out.println(singleLinkedList.toString()); } @DisplayName("add 默认末尾添加") @Test void testAdd() { singleLinkedList.add(1); singleLinkedList.add(2); } @DisplayName("在指定位置添加 add") @Test void testAddIndex() { singleLinkedList.add(0, 1); singleLinkedList.add(0, 0); singleLinkedList.add(1, 2); } @DisplayName("addFirst 表头添加测试") @Test void testAddFirst() { singleLinkedList.addFirst(0); singleLinkedList.addFirst(1); } @DisplayName("contains 测试") @ParameterizedTest @ValueSource(ints = {1}) void testContains(int e) { singleLinkedList.add(e); boolean contains = singleLinkedList.contains(e); Assertions.assertTrue(contains); } @DisplayName("testIndexOf") @ParameterizedTest @ValueSource(ints = {3}) void testIndexOf(int o) { singleLinkedList.add(1); singleLinkedList.add(2); singleLinkedList.add(3); int indexOf = singleLinkedList.indexOf(o); Assertions.assertEquals(2, indexOf); } @DisplayName("test Get") @Test void testGet() { singleLinkedList.addFirst(3); singleLinkedList.addFirst(2); singleLinkedList.addFirst(1); Integer result = singleLinkedList.get(1); Assertions.assertEquals(2, result); } @DisplayName("testRemoveObject 删除") @Test void testRemoveObjectWithHead() { singleLinkedList.add(1); singleLinkedList.add(2); singleLinkedList.add(3); singleLinkedList.addFirst(0); singleLinkedList.remove(0); singleLinkedList.remove(Integer.valueOf(3)); singleLinkedList.remove(Integer.valueOf(2)); singleLinkedList.remove(Integer.valueOf(1)); } }
到这里单向链表的代码就写完了，我们一定要多写才能掌握指针打断的正确操作，尤其是在删除操作最复杂。
课后思考
Java中的LinkedList是什么链表结构呢？- 如何使用
java中的LinkedList实现一个LRU缓存淘汰算法呢？
