概念与定义

空或者只有一个结点。或者

1、存在唯一的一个被称之为“第一个”的结点。

2、存在唯一的一个被称之为“最后一个”的结点。

3、除第一个结点之外，每个结点均只有一个前驱结点。

4、除最后一个结点之外，每个结点均只有一个后继结点。

线性表最重要的直觉是“元素之间只有一条主线”。无论底层使用数组还是链表，抽象层只关心第 i 个元素是谁、能不能在第 i 个位置插入或删除、能不能按顺序遍历。顺序表和链表的差异主要不在接口，而在“找到位置”和“移动元素”的成本不同。

抽象类

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class elemType>
class list
{
public:
    virtual void clear() = 0;                 // 清空线性表
    virtual int length() const = 0;           // 返回当前元素个数
    virtual void insert(int i, const elemType &x) = 0; // 在下标i处插入x
    virtual void remove(int i) = 0;           // 删除下标i处的元素
    virtual int search(const elemType &x) const = 0;   // 查找x，返回下标或-1
    virtual elemType visit(int i) const = 0;  // 访问下标i处的元素
    virtual void traverse() const = 0;        // 按顺序输出所有元素
    virtual ~list() {}
};

这个抽象类只描述线性表应该能做什么，并不规定元素如何存放。seqList 会用连续数组保存元素，sLinkList 和 dLinkList 则用指针把结点串起来。后续代码中所有类都实现同一批接口，因此可以把重点放在：每种存储方式如何完成 insert、remove、search 这几个核心操作。

顺序表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//抽象类的子类
template <class elemType>
class seqList: public list<elemType>
{
private:
    elemType *data;       // 存放元素的动态数组
    int currentLength;    // 当前顺序表长度
    int maxSize;          // 当前数组容量
    void doubleSpace();   // 数组满时扩容
public:
    seqList(int initSize = 10);
    ~seqList()  {delete [] data;}
    void clear()  {currentLength = 0;}
    int length() const {return currentLength;}
    void insert(int i, const elemType &x);
    void remove(int i);
    int search(const elemType &x) const ;
    elemType visit(int i) const;
    void traverse() const ;
};

//构造函数
template <class elemType>
seqList<elemType>::seqList(int initSize)
{
    data = new elemType[initSize]; // 分配初始容量，可继续补充异常处理
    maxSize = initSize;
    currentLength = 0;
}

//查找
template <class elemType>
int seqList<elemType>::search(const elemType &x) const
{
    for (int i = 0; i < currentLength; i++) {
        if (data[i] == x) return i; // 找到后立即返回下标
    }
    return -1; // 扫描完整个顺序表仍未找到
}

//遍历
template <class elemType>
void seqList<elemType>::traverse() const
{
    for (int i = 0; i < currentLength; i++)
        cout << data[i] << " ";
    cout << endl;
}

//插入
//时间复杂度：最好O(1)，最坏O(n)，平均O(n)
template <class elemType>
void seqList<elemType>::insert(int i, const elemType &x)
{
    if (i < 0 || i > currentLength) throw OutOfBound();
    if (currentLength == maxSize) doubleSpace();
    for (int j = currentLength; j > i; j--) data[j] = data[j - 1]; // 后移腾出位置
    data[i] = x; // 填入新元素
    ++currentLength;
}

//扩充空间
template <class elemType>
void seqList<elemType>::doubleSpace()
{
    elemType *tmp = data; // 暂存旧数组地址，便于拷贝和释放
    data = new elemType[2 * maxSize];
    for (int i = 0; i < currentLength; i++) data[i] = tmp[i];
    maxSize *= 2;
    delete [] tmp;
}

//删除
template <class elemType>
void seqList<elemType>::remove(int i)
{
    if (i < 0 || i >= currentLength) throw OutOfBound();
    for (int j = i; j < currentLength - 1; j++) data[j] = data[j + 1]; // 前移覆盖被删元素
    --currentLength;
}

顺序表的核心不变量是：有效元素始终连续存放在 data[0] 到 data[currentLength - 1] 中，currentLength 表示真实元素个数，maxSize 表示当前数组容量。插入时要先把位置 i 及其后面的元素整体后移一格，删除时则把位置 i 后面的元素整体前移一格，因此随机访问很快，但中间插入和删除会有移动成本。

doubleSpace() 是顺序表能动态增长的关键。它并不是在原地扩大数组，而是申请一块更大的新数组，把旧元素复制过去，再释放旧数组。因此扩容那一次操作较慢，但如果从多次插入的角度均摊，每个元素被搬移的次数有限，平均插入成本仍然可以看作常数级扩容开销加上必要的移动开销。

链式表类

链式表和顺序表的主要差异在存储方式：顺序表要求元素连续存放，链式表则用指针把分散的结点串起来。这样做的直接结果是，链表在已知位置附近插入或删除时不需要移动大量元素，只要修改局部指针；但它不能像数组那样通过下标立即访问第 i 个元素，查找位置通常要从头结点开始一步步走。

单链表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
template <class elemType>
class sLinkList: public list<elemType>
{
private:
struct node
{ //单链表中的结点类
    elemType data;
    node *next;
    node(const elemType &x, node *n = NULL) { data = x; next = n; }
    node( ): next(NULL) {}
    ~node() {}
};
    node *head; //头指针
    int currentLength; //表长
    node *move(int i) const; //返回第i个元素的地址
public:
    sLinkList() ;
    ~sLinkList() {clear(); delete head; }
    void clear() ;
    int length() const {return currentLength;}
    void insert(int i, const elemType &x);
    void remove(int i);
    int search(const elemType &x) const ;
    elemType visit(int i) const;
    void traverse() const ;
};

//构造函数
template <class elemType>
sLinkList<elemType>::sLinkList()
{
    head = new node; //创建头结点
    currentLength = 0;
}

//清空
template <class elemType>
void sLinkList<elemType>::clear()
{
    node *p = head->next, *q;
    while (p != NULL) {
        q = p->next; // 先保存后继，避免删除后丢失链表剩余部分
        delete p;    // 释放当前结点
        p = q;       // 继续处理下一个结点
    }
    head->next = NULL; //重置头结点
    currentLength = 0;
}

//返回第i个元素的指针
template <class elemType>
sLinkList<elemType>::node *sLinkList<elemType>::move(int i) const
{
    node* p = head;
    while (i-- >= 0) p = p->next; // 从头结点出发，移动到第i个数据结点
    return p;
}

//查找
template <class elemType>
int sLinkList<elemType>::search(const elemType &x) const
{
    node *p = head->next;
    int i = 0;
    while (p != NULL && p->data != x) { p = p->next; ++i; }
    if (p == NULL) return -1;
    else return i;
}

//遍历
template <class elemType>
void sLinkList<elemType>::traverse() const
{
    node *p = head->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next; // 沿next指针顺序访问
    }
    cout << endl;
}

单链表的核心不变量是：head 是头结点，真正的数据从 head->next 开始；每个结点只知道自己的后继。头结点不存储有效数据，它的作用是统一“在第一个元素前插入/删除”和“在中间插入/删除”的写法，减少边界情况。

读链表代码时，最容易卡住的是 move(i)。它返回的是某个位置对应的结点地址，因此链表插入通常会先找到“插入位置的前驱结点”，再改两条指针：新结点指向原后继，前驱结点指向新结点。与顺序表相比，链表不需要整体搬移元素，但想访问第 i 个元素必须从头沿 next 逐个走过去。

双链表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
template <class elemType>
class dLinkList: public list<elemType>
{
private:
struct node { //双链表中的结点类
    elemType data;
    node *prev, *next;
    node(const elemType &x, node *p = NULL, node *n = NULL) { data = x; next = n; prev = p; }
    node( ):next(NULL), prev(NULL) {}
    ~node() {}
};
    node *head, *tail; //头尾指针
    int currentLength; //表长
    node *move(int i) const; //返回第i个元素的地址
public:
    dLinkList() ;
    ~dLinkList() {clear(); delete head; delete tail;}
    void clear() ;
    int length() const {return currentLength;}
    void insert(int i, const elemType &x);
    void remove(int i);
    int search(const elemType &x) const ;
    elemType visit(int i) const;
    void traverse() const ;
};

//构造函数
template <class elemType>
dLinkList<elemType>::dLinkList()
{
    head = new node; //创建头结点
    tail = new node; //创建尾结点
    head->next = tail; //头结点指向尾结点
    tail->prev = head; //尾结点指向头结点
    currentLength = 0;
}

//插入
template <class elemType>
void dLinkList<elemType>::insert(int i, const elemType &x)
{
    node *pos, *tmp;
    pos = move(i); //注意，move需要自行实现
    tmp = new node(x, pos->prev, pos); //结点构造函数
    pos->prev->next = tmp; // 前驱的next指向新结点
    pos->prev = tmp;       // 后继的prev指向新结点
    ++currentLength;
}

//删除
template <class elemType>
void dLinkList<elemType>::remove(int i)
{
    node *pos;
    pos = move(i); //注意，move需要自行实现
    pos->prev->next = pos->next; // 前驱跳过待删结点
    pos->next->prev = pos->prev; // 后继回连待删结点的前驱
    delete pos;
    --currentLength;
}

双链表比单链表多维护一条反向指针 prev，因此删除某个已知结点时，不需要再从头寻找它的前驱。插入和删除的本质都是维护局部四条连接关系：新结点或待删结点的前驱、后继必须互相重新接好。代码中的 head 和 tail 都是哨兵结点，它们让空表、表头插入、表尾插入这些边界情况都能被统一处理。

双向链表中查找、访问、遍历等操作与单链表类似，只是需要注意前驱和后继指针的使用，此处不再实现。

单循环链表类

  • 一般单循环链表不带头结点。
  • Head 为头指针。（头指针和头结点有区别）
  • 插入操作时间复杂度为 O(1)，删除操作时间复杂度为 O(n)，查找操作时间复杂度为 O(n)。

单循环链表的最后一个结点不再指向 NULL，而是重新指向首元素，因此沿着 next 指针一直走会回到起点。它适合需要循环处理元素的场景，例如约瑟夫环或轮转调度。读这种结构时要特别注意终止条件：普通单链表可以用 p == NULL 停止，循环链表则通常要判断是否重新回到 head。

双循环链表类

  • 首元素中 prior 字段给出尾元素的地址，尾元素中 next 字段给出首元素的地址。
  • 一般也不设头尾结点（注意头/尾结点；头/尾指针；首/尾元素的区分）
  • 插入操作时间复杂度为 O(1)，删除操作时间复杂度为 O(n)，查找操作时间复杂度为 O(n)。

双循环链表同时保留前驱和后继，并把首尾结点连成环。相比单循环链表，它可以从任意结点向前或向后移动；相比普通双链表，它没有天然的 NULL 边界。实现时通常需要非常明确地约定 head 是指向首元素还是哨兵结点，否则空表、只有一个元素、删除首尾元素这些边界情况很容易写错。