T08. Linked Lists
由于数组具有以下缺陷：
- 在插入元素的时候需要移动大量数据
- 可能开了 100000 的空间，但是没用到那么多
- 如果满了，不方便扩容
所以引入链表这种数据结构。
单向的 Linked List 与 Link（singly）
链表，每一个节点都存储两个信息：数据、到下一个节点的链接。
在 CS210 这门课当中，认为 Linked List 是整个链表的头，而 Link（可以理解为 Node） 是每一个节点到下一个节点的连接。Linked List 存储到第一个 Link 的引用，而每一个 Link 存储到下一个节点的引用。
代码实现：
class LinkedList {
private Link first;
public LinkedList() { first = null; }
public boolean isEmpty() { return first == null; }
}
public class Link {
public int data;
public Link next;
public Link(int datain) { data = datain; next = null; }
}
对于 LinkedList 类，也就是整个链表结构类，还有以下操作：
// 在头部插入数据
public void insertHead(int x) {
Link newLink = new Link(x);
newLink.next = first;
first = newLink;
}
// 删除头部数据并返回
public Link deleteHead() {
Link data = first;
first = first.next;
return data;
}
// 遍历并输出链表
public void displayLink() { System.out.println("{" + data + "}"); }
public void display() {
Link cur = first;
while (cur != null) {
cur.displayLink();
cur = cur.next;
}
}
// 删除一个节点
public Link delete(int key) { // delete link with given key
Link current = first; // search for link
Link previous = first; // put these equal to first Link
while (current.data != key)
if (current.next == null) {
return null;
} // didn't find it
else {
previous = current; // go to next link
current = current.next
}
} // found it
if (current == first) { // if first link,
first = first.next; // change first
} else { // otherwise,
previous.next = current.next; // bypass it
}
return current;
}
Double Ended Linked List
双端链表，也可以在尾部插入元素。
单端链表可以用来实现一个栈，双端链表可以用来实现一个队列。
有序链表 sorted linked list
就是插入元素的时候 $O(n)$ 找到合适的插入位置
可以用来实现排序，虽然仍然需要 $O(n^2)$ 的比较次数，但是 copy 次数是 $O(2n)$ 的，这方面比插入排序快一点。
doubly linked list
双向链表，每一个 Node（Link）额外存储一下 prev 信息。