4. 链表¶
4.1. 链表¶
本模块介绍线性表两种传统实现之一，通常称为 链表 。 链表采用 动态内存分配 ， 即根据需要为新的线性表元素分配内存。 下图展示了链表的概念。 图中有 3 个"链接"在一起的 结点 。 每个结点都有两个方框。 右边的方框存放指向线性表中下一个结点的链接。 注意，最右边结点的链接方框中画有一条斜线， 表示这个方框没有引出任何链接。
由于线性表结点是一个独立的对象（而不只是数组中的一个单元），
最好的做法是为它定义一个单独的线性表结点类。
（我们还可以复用这个线性表结点类，
为 栈 和
队列
这两种数据结构实现链式版本。）
下面是线性表结点的一个实现，称为 Link 类。
Link 类的对象包含一个用于存储元素值的 element 字段，
以及一个存放指向线性表中下一个结点的指针的 next 字段。
由这种结点构成的线性表称为 单链表 ，
或者叫 单向链表 ，
因为每个线性表结点只有一个指向线性表中下一个结点的指针。
class Link { // Singly linked list node class
private Object e; // Value for this node
private Link n; // Point to next node in list
// Constructors
Link(Object it, Link inn) { e = it; n = inn; }
Link(Link inn) { e = null; n = inn; }
Object element() { return e; } // Return the value
Object setElement(Object it) { return e = it; } // Set element value
Link next() { return n; } // Return next link
Link setNext(Link inn) { return n = inn; } // Set next link
}
class Link<E> { // Singly linked list node class
private E e; // Value for this node
private Link<E> n; // Point to next node in list
// Constructors
Link(E it, Link<E> inn) { e = it; n = inn; }
Link(Link<E> inn) { e = null; n = inn; }
E element() { return e; } // Return the value
E setElement(E it) { return e = it; } // Set element value
Link<E> next() { return n; } // Return next link
Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
}
Link 类相当简单。
它的构造函数有两种形式：一种带有初始元素值，另一种不带。
成员函数允许使用者读取或设置 element 和 link 字段。
4.1.1. 这种表示存在的问题¶
前面描述的这种表示存在不少问题。
首先，需要为大量特殊情况编写代码。
例如，线性表为空时， head 、 tail 和 curr 都没有元素可以指向。
为 insert 和 remove 实现特殊情况处理会增加代码复杂度，
使代码更难理解，从而增加引入缺陷的可能性。
4.1.2. 更好的解决方案¶
幸运的是，有一种相当简单的方法， 既能处理所有特殊情况，又能解决删除最后一个结点的问题。 把链表实现为在表的最前面增设一个 头结点 ， 就可以消除许多特殊情况。 这个头结点与其他链接结点并无不同， 但它的值会被忽略，也不被视为线性表的实际元素。 头结点节省了编码工作量， 因为我们不再需要考虑空线性表， 或者当前位置位于线性表一端的特殊情况。 这一简化的代价是头结点所占的空间。 不过，由于处理特殊情况的语句被省去，代码规模更小，反而节省了空间。 通过再添加一个同样从不存储值的"尾部结点"（trailer）， 我们消除了与线性表末端相关的其余特殊情况。
下图展示了带头结点和尾部结点的链表的初始状态。
下面是含有若干元素的线性表在加上头结点和尾部结点之后的样子。
添加尾部结点还解决了删除线性表最后一个结点的问题， 这一点在我们后文仔细考察 remove 方法的实现时就会看到。
4.1.3. 链表的实现¶
下面是链表类的实现，名为 LList 。
// Linked list implementation
class LList implements List {
private Link head; // Pointer to list header
private Link tail; // Pointer to last element
private Link curr; // Access to current element
private int listSize; // Size of list
// Constructors
LList(int size) { this(); } // Constructor -- Ignore size
LList() { clear(); }
// Remove all elements
public void clear() {
curr = tail = new Link(null); // Create trailer
head = new Link(tail); // Create header
listSize = 0;
}
// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(new Link(curr.element(), curr.next()));
curr.setElement(it);
if (tail == curr) tail = curr.next(); // New tail
listSize++;
return true;
}
// Append "it" to list
public boolean append(Object it) {
tail.setNext(new Link(null));
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public Object remove() {
if (curr == tail) return null; // Nothing to remove
Object it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) tail = curr; // Removed last, move tail
curr.setNext(curr.next().next()); // Point around unneeded link
listSize--; // Decrement element count
return it; // Return value
}
public void moveToStart() { curr = head.next(); } // Set curr at list start
public void moveToEnd() { curr = tail; } // Set curr at list end
// Move curr one step left; no change if now at front
public void prev() {
if (head.next() == curr) return; // No previous element
Link temp = head;
// March down list until we find the previous element
while (temp.next() != curr) temp = temp.next();
curr = temp;
}
// Move curr one step right; no change if now at end
public void next() { if (curr != tail) curr = curr.next(); }
public int length() { return listSize; } // Return list length
// Return the position of the current element
public int currPos() {
Link temp = head.next();
int i;
for (i=0; curr != temp; i++)
temp = temp.next();
return i;
}
// Move down list to "pos" position
public boolean moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) return false;
curr = head.next();
for(int i=0; i<pos; i++) curr = curr.next();
return true;
}
// Return true if current position is at end of the list
public boolean isAtEnd() { return curr == tail; }
// Return current element value. Note that null gets returned if curr is at the tail
public Object getValue() { return curr.element(); }
// Check if the list is empty
public boolean isEmpty() { return listSize == 0; }
}
// Linked list implementation
class LList<E> implements List<E> {
private Link<E> head; // Pointer to list header
private Link<E> tail; // Pointer to last element
private Link<E> curr; // Access to current element
private int listSize; // Size of list
// Constructors
LList(int size) { // Constructor -- Ignore size
this();
}
LList() {
clear();
}
// Remove all elements
public void clear() {
curr = tail = new Link<E>(null); // Create trailer
head = new Link<E>(tail); // Create header
listSize = 0;
}
// Insert "it" at current position
public boolean insert(E it) {
curr.setNext(new Link<E>(curr.element(), curr.next()));
curr.setElement(it);
if (tail == curr) {
tail = curr.next(); // New tail
}
listSize++;
return true;
}
// Append "it" to list
public boolean append(E it) {
tail.setNext(new Link<E>(null));
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public E remove () {
if (curr == tail) return null; // Nothing to remove
E it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) {
tail = curr; // Removed last, move tail
}
curr.setNext(curr.next().next()); // Point around unneeded link
listSize--; // Decrement element count
return it; // Return value
}
public void moveToStart() {
curr = head.next(); // Set curr at list start
}
public void moveToEnd() {
curr = tail; // Set curr at list end
}
// Move curr one step left; no change if now at front
public void prev() {
if (head.next() == curr) {
return; // No previous element
}
Link<E> temp = head;
// March down list until we find the previous element
while (temp.next() != curr) {
temp = temp.next();
}
curr = temp;
}
// Move curr one step right; no change if now at end
public void next() { if (curr != tail) { curr = curr.next(); } }
public int length() { return listSize; } // Return list length
// Return the position of the current element
public int currPos() {
Link<E> temp = head.next();
int i;
for (i=0; curr != temp; i++) {
temp = temp.next();
}
return i;
}
// Move down list to "pos" position
public boolean moveToPos(int pos) {
if ((pos < 0) || (pos > listSize)) {
return false;
}
curr = head.next();
for(int i=0; i<pos; i++) { curr = curr.next(); }
return true;
}
// Return true if current position is at end of the list
public boolean isAtEnd() { return curr == tail; }
// Return current element value. Note that null gets returned if curr is at the tail
public E getValue() {
return curr.element();
}
//Tell if the list is empty or not
public boolean isEmpty() {
return listSize == 0;
}
}
下面是链表插入的一些特殊情况：在末端插入，以及向空线性表中插入。
4.2. 链表的删除¶
其余操作的实现各自只需要 \(\Theta(1)\) 时间。
