数据结构与算法--单链表
数据结构与算法--单链表
链式存储结构的特点
学习线性表的顺序存储结构时，举了个例子：记忆和你住一条街的每家姓氏，以自家为第一家。如果换一种记忆方式：你记得下一家是王家，王家的下一家是李家，李家下一家是赵家，赵家下一家是孙家....当人问及第四家是谁家时，你估计没法脱口而出了，你得按照这个顺序一步步推算，从你家开始从头数，从中间开始算要是遗漏了那就找不到了。这种记忆方式或者数据结构称为链式存储结构。它定位起来比较慢，如果别人问你这条街最后一家是谁家，这是最糟糕的情况，你从自家开始数到最后才发现原来这条街的最后一户原来是徐家啊！这时查找的时间复杂度就是O(n)。
再看插入，如果使用链式存储结构：假设新来的吴家搬到了你家旁边，你只需再多记住一条：下一家是吴家，吴家的下一家是王家...后面的不用记了——你早就记得了。实际上不管他搬到哪儿（设为index处），你也只需多记忆一条，不过你得知道新来的到底是搬到了哪家（index - 1）和哪家（index）之间，然后你在脑子里加了一条：index - 1处是许家，他的下一家是新搬来的吴家，吴家下一家才是index处的龙家。你从第一家开始一直定位到新搬来的那家的前一家（index - 1），这些时间也是要算进去的，所以平均来看时间复杂度为O(n)。当然有人搬走了也是类似的。
一条街上的住民来表示链式存储结构可能不太恰当。因为链式存储结构允许元素的分散，它们不一定排成一列，也就是说内存空间的划分不是连续的。哪儿有空间去哪儿都行，你随便瞎跑，但是你一定要记得你下一个同胞是什么在哪里。现实生活中的例子比如去银行办理业务，一般你会拿到一个编号比如57。之后你不用排队，你可以出去吃个饭，再到处走走。只要你确定还没轮到56号——当然56号结束了，接下来就是你了，所以你不用去关心之前的号码是什么情况。这个例子中虽然是“前一个”但原理都是一样的。抽象成一个结点Node的话，这个Node存有next表示下一个元素；和data表示这个元素持有的信息。由于Node是这样定义的，所以当前的结点当然也不知道下下个结点的信息。他记忆不好，他只记得自己的信息和下一个同胞，其他人他不认识。由于链式结构位置可以分散，意味着通常不会用数组来抽象，所以链式存储无需指定容量。（静态链表除外，静态链表使用数组，也要指定容量，后面会具体说），除非它把内存耗尽，否则你永远也无须担心数据太多不够装的问题。
链式存储结构的实现--单链表
所谓单链表就是结点的指针指向是单向的。表现在代码中如下：
private class Node {
Item data
Node next;
}
结点只有一个next指针，指向下一个结点——而不能指向上一个节点。最后一个结点指向null，表示已经到单链表的末尾。本实现中不设置头结点，Node first表示的就是第一个结点，按照习惯，你可以认为有一个头指针指向了它，但在Java中由于没有指针的说法，这个概念听起来就比较朦胧了。不管，反正可以实现。为了方便在表链尾部插入，我还使用了一个Node last表示最后一个结点。构造器可以传入多个参数，按照顺序在尾部插入。
先上全部代码。
package Chap3;
import java.util.Iterator;
public class SLinkedList<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
// 指向第一个节点
private Node first;
// 指向最后一个节点
private Node last;
private int N;
public SLinkedList(Item... items) {
for (Item item : items) {
add(item);
}
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
private Node index(int index) {
// [0, N-1]的定位范围
if (index < 0 || index >= N) {
throw new IndexOutOfBoundsException(index + "");
}
Node current = first;
for (int j = 0; j < index; j++) {
current = current.next;
}
return current;
}
public Item get(int index) {
Node current = index(index);
return current.data;
}
public void set(int index, Item item) {
Node current = index(index);
current.data = item;
}
// 可以在表头（index==0）和表尾插入
public void insert(int index, Item item) {
// 如果index==0,因为没有设置头结点所以只需单向链接就行
if (index == 0) {
push(item);
} else if (index == N) {
add(item);
} else if (index > 0 && index < N) {
Node a = new Node();
// 其他插入的位置在index-1和index之间, 需要定位到index-1的位置，
Node current = index(index - 1);
a.data = item;
a.next = current.next;
current.next = a;
N++;
} else {
throw new IndexOutOfBoundsException(index + "");
}
}
public Item remove(int index) {
// 和insert一样，index==0处理方式也不一样
Item item;
if (index == 0) {
item = pop();
// 和insert不一样（它可以在表尾null处插入），remove则不该移除本来就是null的值
// 表尾的删除也稍有不同
} else if(index == N -1) {
Node current = index(index - 1);
item = current.next.data;
current.next = null;
last = current;
} else if (index > 0 && index < N) {
Node current = index(index - 1);
// 定位到index的上一个了，所以取next
item = current.next.data;
Node next = current.next.next;
// 下面两行帮助垃圾回收
current.next.next = null;
current.next.data = null;
current.next = next;
N--;
} else {
throw new IndexOutOfBoundsException(index + "");
}
return item;
}
// 表尾加入元素
public void add(Item item) {
Node oldlast = last;
last = new Node();
last.data = item;
// last应该指向null，但是新的结点next默认就是null
// 如果是第一个元素，则last和first指向同一个，即第一个
if (isEmpty()) {
first = last;
} else {
oldlast.next = last;
}
N++;
}
// 表头插入元素
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.data = item;
// 和add一样，第一个元素加入时，last和first指向同一个结点
if (isEmpty()) {
last = first;
} else {
first.next = oldfirst;
}
N++;
}
// 删除表头元素
public Item pop() {
Item item = first.data;
Node next = first.next;
// 这两行有助于垃圾回收
first.data = null;
first.next = null;
first = next;
N--;
// 最后一个元素被删除，first自然为空了，但是last需要置空。
// 注意是先减再判断是否为空
if (isEmpty()) {
last = null;
}
return item;
}
public void clear() {
while (first != null) {
Node next = first.next;
// 下面两行帮助垃圾回收
first.next = null;
first.data = null;
first = next;
}
// 所有元素都空时，last也没有有所指了。记得last置空
last = null;
N = 0;
}
public int indexOf(Item item) {
int index = 0;
if (item != null) {
for (Node cur = first; cur != null; cur = cur.next) {
if (item.equals(cur.data)) {
return index;
}
index++;
}
} else {
for (Node cur = first; cur != null; cur = cur.next) {
if (cur.data == null) {
return index;
}
index++;
}
}
return -1;
}
public boolean contains(Item item) {
return indexOf(item) >= 0;
}
@Override
public Iterator<Item> iterator() {
return new Iterator<>() {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = current.data;
current = current.next;
return item;
}
};
}
@Override
public String toString() {
Iterator<Item> it = iterator();
if (!it.hasNext()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
while (true) {
Item item = it.next();
sb.append(item);
if (!it.hasNext()) {
return sb.append("]").toString();
}
sb.append(", ");
}
}
public static void main(String[] args) {
SLinkedList<String> a = new SLinkedList<>("12", "34", "56", "78");
System.out.println(a.get(0)); // 12
System.out.println(a.remove(1)); // 34
System.out.println(a.remove(1)); // 56
System.out.println(a); // [12, 78]
a.insert(0, "a");
a.insert(1, "b");
a.set(3, "d");
for (String aa : a) {
System.out.println(aa);
}
/* Out:
a
b
12
d
*/
System.out.println("*******");
SLinkedList<Integer> c = new SLinkedList<>(1, 2, 3, 4, 5);
System.out.println(c);
c.clear();
c.add(45);
c.add(46);
c.push(44);
System.out.println(c); // [44, 45, 46]
System.out.println(c.indexOf(46)); // 2
System.out.println(c.contains(46)); //true
System.out.println(c.size()); //3
}
}
先看这个比较重要的方法private Node index(int index)，这是个定位函数，给出一个index，返回index处的结点引用。很多公有方法中都用到了这个方法。首先还是要检查范围，显然只能获取[0, N - 1]内的Node。在循环中不断移动指针，一直移动到index处。
然后看push方法，它在链表的头部之前插入一个新的结点，新结点代替原来的“新结点”占据first的位置；再让新结点的next指向原新结点。有一处需要注意，当插入第一个结点时（此时表还是空），第一个结点同时也是最后一个结点，所以有last = first。
pop方法，就是让first的下一结点取代first的位置。原来的first等待垃圾回收，为了帮助垃圾回收，使用了几行代码
Node next = first.next;
// 这两行有助于垃圾回收
first.data = null;
first.next = null;
first = next;
先是将first.next这个结点保存到临时变量中，紧接着把将被取代的first的所有信息置为null，可以帮助垃圾回收，这之后才让first的下一个结点取代first的位置。注意当最后一个被弹出后，链表为空了。因为pop方法操作的始终是first指针，链表空后last没有意义了，也需要被置为null。
add 方法在表尾部添加结点。用last指针更方便，新结点作为last，然后让原last结点的next指向最新的last结点。在添加第一个结点的时候，也注意和push方法一样，最后一个结点同时也是第一个节点，故有first = last。
insert方法，当在index为0的地方插入，实际上就是push操作。其他位置，包括最后一个结点之后的位置（实际上相当于add操作），需要定位到插入结点的前一个结点，即插入到index -1和index之间。所以有Node current = index(index - 1);插入的新结点在current的next之前，且在current结点之后。
a.next = current.next;
current.next = a;
上面两句是关键，顺序不能颠倒。如果先让current.next = a。再a.next = current.next，此时current.next不再表示current的下一个结点了（变成了新结点，而代码实际上变成了a.next = a），这样造成了逻辑混乱，最终导致插入失败。
remove方法，也需要定位到移除结点的前一个结点，Node current = index(index - 1)然后令current的下一个结点指向current下下个结点，左边那个结点的手直接拉向了右边结点的手，抛弃了中间的那个结点。我们所有移除结点的方法，都会帮助垃圾回收。
Node next = current.next.next;
// 下面两行帮助垃圾回收
current.next.next = null;
current.next.data = null;
current.next = next;
current.next就是即将要移除的结点。先用一个临时变量保存current.next的next信息，之后清空current.next的所有信息。
一定要注意insert和remove方法在表中位置0和位置N - 1操作时，处理方法稍有不同，判断条件的分支搞了好几个也是这个原因。
clear方法实际上就是不断执行pop方法，等到最后一个结点弹出，first为null，此时记得last也需要置为空。
by @sunhaiyu
2017.8.1
