什么是单向链表？单向链表基础操作

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。链表可以分为单向链表和双向链表。

单向链表，每个元素只知道其下一个元素是谁。
 

双向链表，每个元素知道其上一个元素和下一个元素。

循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head。链表内还有一种特殊的节点称为哨兵(Sentinel)节点，也叫做哑元( Dummy)节点，它不存储数据，通常用作头尾，用来简化边界判断。

单向链表

根据单向链表的定义，首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用。

public class SinglyLinkedList {private Node head; // 头部节点private static class Node { // 节点类int value;Node next;public Node(int value, Node next) {            this.value = value;this.next = next;}}
}

在上述代码中Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义。下面演示单向链表的创建方法

头部添加（头插法）

public class SinglyLinkedList {// ...public void addFirst(int value) {this.head = new Node(value, this.head);}
}

如果 this.head == null，新增节点指向 null，并作为新的 this.head。如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head。注意赋值操作执行顺序是从右到左

尾部添加

public class SinglyLinkedList {// ...private Node findLast() {if (this.head == null) {return null;}Node curr;for (curr = this.head; curr.next != null; ) {curr = curr.next;}return curr;}public void addLast(int value) {Node last = findLast();if (last == null) {addFirst(value);return;}last.next = new Node(value, null);}
}

注意，找最后一个节点，终止条件是 curr.next == null ，分成两个方法是为了代码清晰，而且 findLast() 之后还能复用。

尾部添加多个

public class SinglyLinkedList {// ...public void addLast(int first, int... rest) {Node sublist = new Node(first, null);Node curr = sublist;for (int value : rest) {curr.next = new Node(value, null);curr = curr.next;}Node last = findLast();if (last == null) {this.head = sublist;return;}last.next = sublist;}
}

先串成一串 sublist，再作为一个整体添加。
根据索引获取

public class SinglyLinkedList {// ...private Node findNode(int index) {int i = 0;for (Node curr = this.head; curr != null; curr = curr.next, i++) {if (index == i) {return curr;}}return null;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}public int get(int index) {Node node = findNode(index);if (node != null) {return node.value;}throw illegalIndex(index);}
}

同样，分方法可以实现复用

插入

public class SinglyLinkedList {// ...public void insert(int index, int value) {if (index == 0) {addFirst(value);return;}Node prev = findNode(index - 1); // 找到上一个节点if (prev == null) { // 找不到throw illegalIndex(index);}prev.next = new Node(value, prev.next);}
}

注意：插入包括下面的删除，都必须找到上一个节点。

删除

public class SinglyLinkedList {// ...public void remove(int index) {if (index == 0) {if (this.head != null) {this.head = this.head.next;return;} else {throw illegalIndex(index);}}Node prev = findNode(index - 1);Node curr;if (prev != null && (curr = prev.next) != null) {prev.next = curr.next;} else {throw illegalIndex(index);}}
}

第一个 if 块对应着 removeFirst 情况，最后一个 if 块对应着至少得两个节点的情况，不仅仅判断上一个节点非空，还要保证当前节点非空。