Lists

一、链表的基本概念

  • 定义: 链表是一种有限的、有序的数据项序列，称为元素（elements）。
  • 表示法: 使用符号表示为 \(<a0, a1, …, an-1>\)。
  • 元素位置: 每个元素在链表中都有一个位置。
  • 类型: 每个元素可以是任意类型，但所有元素必须是同一类型。
  • 长度: 链表的长度是当前存储的元素数量。
  • 空链表: 空链表不包含任何元素。
  • 头和尾: 链表的开始称为头（head），结束称为尾（tail）。

二、链表的常见操作

  • 插入（insert）
  • 追加（append）
  • 删除（delete/remove）
  • 查找（find）
  • 判断是否为空（isEmpty）
  • 移动到上一个元素（prev）
  • 移动到下一个元素（next）
  • 获取当前元素的位置（currPos）
  • 移动到指定位置（moveToPos）
  • 移动到链表开始位置（moveToStart）
  • 获取链表长度（length）

三、链表的实现

1. 列表抽象数据类型（ADT）

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
// 定义一个模板类 List，表示一个抽象列表（List ADT）
// 模板类型 E 表示列表中元素的类型
template <typename E>
class List {
public:
    // 构造函数，默认构造一个 List 对象
    List() {}

    // 虚析构函数，确保派生类对象可以被正确销毁
    virtual ~List() {}

    // 在列表中插入元素 item
    // 返回插入操作是否成功
    virtual bool insert(const E& item) = 0;

    // 在列表的尾部追加元素 item
    // 返回追加操作是否成功
    virtual bool append(const E& item) = 0;

    // 从列表中移除当前元素
    // 通过引用参数 E& 返回被移除的元素
    // 返回移除操作是否成功
    virtual bool remove(E&) = 0;

    // 清空列表，移除所有元素
    virtual void clear() = 0;

    // 将当前指针移动到列表的开始位置
    virtual void moveToStart() = 0;

    // 将当前指针移动到列表的结束位置（即最后一个元素的后面）
    virtual void moveToEnd() = 0;

    // 将当前指针移动到当前元素的前一个元素
    virtual void prev() = 0;

    // 将当前指针移动到当前元素的下一个元素
    virtual void next() = 0;

    // 返回当前指针的位置（索引）
    virtual int currPos() const = 0;

    // 移动当前指针到指定位置 pos
    virtual void moveToPos(int pos) = 0;

    // 其他操作...
};

2. 标准链表实现

2.1 数组实现的链表

  • 思想: 预先分配一个大小为 MAX_SIZE 的大数组。
  • 变量跟踪:
    • 当前大小 count
    • 当前定位 curr_position

插入操作:

  • 平均情况下，需要移动一半的元素。
  • 最坏情况下，插入位置为 0，需要移动所有 N 项，时间复杂度为 \(O(N)\)。
  • 最好情况下，时间复杂度为 \(\Theta(1)\)。

插入代码示例:

1
2
3
4
5
6
7
8
9
void insert(const E& it) {
    Assert(listSize >= maxSize, "Exceed capacity");
    // 向上移动元素
    for (int i = listSize; i > curr; i--) {
        listArray[i] = listArray[i - 1]; 
    }
    listArray[curr] = it; // 插入元素
    listSize++; // 增加链表大小
}

删除操作:

  • 只需移动当前元素之后的元素。
  • 时间复杂度为 \(\Theta(1)\)（最好情况下），\(\Theta(n)\)（最坏和平均情况下）。

删除代码示例:

1
2
3
4
5
6
7
8
9
E remove() {
    Assert((curr >= 0) && (curr < listSize), "no element");
    E it = listArray[curr]; // 复制元素
    for (int i = curr; i < listSize - 1; i++) {
        listArray[i] = listArray[i + 1]; // 向下移动元素
    }
    listSize--; // 减小大小
    return it;
}

2.2 指针实现的链表（链表）

  • 动态内存分配: 需要时为新的链表元素分配内存。
  • 节点结构:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 简单的单链表节点实现
template <typename E>
class Link {
public:
    E element;  // 此节点的值
    Link *next; // 指向列表中下一个节点的指针

    // 构造函数，接受元素值和下一个节点指针
    Link(const E& elemval, Link* nextval = NULL) {
        element = elemval;  
        next = nextval; 
    }
    
    // 默认构造函数，只初始化下一个指针
    Link(Link* nextval = NULL) {
        next = nextval; 
    }
};

2.3 链表类的实现

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
// 类 LList 
// 继承抽象类 List
template <typename E>
class LList : public List<E> {
private:
    Link<E>* head; // 指向列表头部的指针
    Link<E>* tail; // 指向最后一个元素的指针
    Link<E>* curr; // 访问当前元素
    int cnt;      // 列表大小

    // 初始化列表
    void init() // 由构造函数使用 
    {  
        curr = tail = head = new Link<E>; // 初始化一个空头节点
        cnt = 0;  // 列表长度为 0
    }

    // 移除所有节点，清空列表
    void removeall() // 由析构函数使用
    {   
        while(head != NULL) { 
            curr = head; 
            head = head->next; // 逐个移动到下一个节点
            delete curr;      // 删除当前节点
        }
    }
};

3. 链表的插入与删除

3.1 插入

  • 创建一个新的链表节点，存储新元素。
  • 设置新节点的 next 字段。
  • 设置当前节点的 next 字段。

插入代码示例:

1
2
3
4
5
6
7
8
9
// 在当前位插入节点
public:
    void insert(const E& it) {
        // 创建新节点并将其插入到 curr 之后
        curr->next = new Link<E>(it, curr->next);  	
        if (tail == curr) tail = curr->next; // 如果 curr 是尾节点，则更新尾指针
        cnt++; // 增加列表大小
    }

追加节点

1
2
3
4
5
6
// 在列表的尾部追加节点
void append(const E& it) {
    tail = tail->next = new Link<E>(it, NULL); // 创建新节点并链接到当前尾节点
    cnt++; // 增加列表大小
}

3.2 删除

  • 删除节点只需重新定向指针。
  • 记得回收已删除节点占用的空间。

删除代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
// 移除并返回当前元素
E remove() {
    E it = curr->next->element; // 获取要移除的节点的元素
    Link<E>* ltemp = curr->next; // 保存要删除的节点
    if (tail == curr->next) 
        tail = curr; // 如果要移除的节点是尾节点，更新尾指针
    curr->next = curr->next->next; // 将 curr 的下一个节点指向要删除节点的下一个节点
    delete ltemp;  // 删除节点，回收内存
    cnt--; // 减少列表大小
    return it; // 返回被移除的元素
}

3.3 当前指针移动操作

向前移动

1
2
3
4
5
6
7
// Next – 将 curr 移动一个位置朝向尾部
void next() { // 如果已经在末尾则不变
    if (curr != tail) { 
        curr = curr->next; // 移动 curr 指向下一个节点
    }
}

向后移动

1
2
3
4
5
6
7
8
9
// Prev – 将 curr 移动一个位置朝向头部 
void prev() {
    if (curr == head) return; // 如果 curr 是头节点，则没有前一个元素
    Link<E>* temp = head;
    // 向下列表移动直到前一个元素
    while (temp->next != curr) temp = temp->next; // 遍历找到前一个节点
    curr = temp; // 更新 curr 为前一个节点
}

四、链表与数组的空间效率比较

空间复杂度比较

在使用不同的数据结构实现列表时，内存占用是一个重要考虑因素。以下是数组实现与链表实现的空间复杂度比较：

数组实现的空间复杂度

假设列表中当前元素的数量为 $ n $，指针的大小为 $ P $，数据元素的大小为 $ E $，则使用数组实现时，总大小计算如下：

$ = (n + 1) P + n E $

  • $ n + 1 $ 是为了存储 $ n $ 个元素的指针以及一个额外的指针来跟踪列表的末尾。
  • $ n E $ 是存储 $ n $ 个数据元素所需的空间。

链表实现的空间复杂度

对于链表实现，总大小为：

$ = (2n + 2) P + n E $

  • $ 2n $ 是因为每个节点有两个指针（当前节点指针和下一个节点指针）。
  • 额外的两个 $ P $ 是为头指针和尾指针所保留的空间。
  • $ n E $ 是存储 $ n $ 个数据元素所需的空间。

示例

假设 $ n = 1000 \(，\) P = 4 \(，\) E = 4 $：

  • 数组总大小： $ = (1000 + 1) + 1000 = 8004 $

  • 链表总大小： $ = (2 + 2) + 1000 = 8008 $

  • 动态内存分配：链表通过动态内存分配，能够根据需要为新元素分配内存，减少了空间浪费。

  • 插入与删除效率：链表在插入和删除操作中，重定向指针的过程是高效的，但需要回收已删除节点的内存。

  • 空间效率：链表在元素数量变化范围广泛或未知时更为高效，而对于已知大小的列表，数组实现通常会更节省空间。

完整代码实现

数组实现

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cassert>

template <typename E>
class ArrayList {
private:
    E* listArray;      // 存储元素的数组
    int listSize;      // 当前存储的元素数量
    int maxSize;       // 数组的最大容量
    int curr;          // 当前指针位置

public:
    // 构造函数
    ArrayList(int size = 100) {
        maxSize = size;
        listSize = 0;
        listArray = new E[maxSize]; // 动态分配数组内存
        curr = 0;                   // 初始时 curr 指向第一个元素
    }

    // 析构函数
    ~ArrayList() {
        delete[] listArray; // 释放动态分配的内存
    }

    // 插入操作
    void insert(const E& it) {
        assert(listSize < maxSize && "Exceed capacity"); // 检查是否超出容量
        for (int i = listSize; i > curr; i--) { // 向上移动元素
            listArray[i] = listArray[i - 1];
        }
        listArray[curr] = it; // 插入新元素
        listSize++; // 增加列表大小
    }

    // 追加操作
    void append(const E& it) {
        assert(listSize < maxSize && "Exceed capacity"); // 检查是否超出容量
        listArray[listSize++] = it; // 直接在末尾插入新元素
    }

    // 删除操作
    E remove() {
        assert((curr >= 0) && (curr < listSize) && "No element to remove"); // 检查是否有元素可删除
        E it = listArray[curr]; // 复制要删除的元素
        for (int i = curr; i < listSize - 1; i++) { // 向下移动元素
            listArray[i] = listArray[i + 1];
        }
        listSize--; // 减少列表大小
        return it; // 返回被移除的元素
    }

    // 查找元素
    int find(const E& it) const {
        for (int i = 0; i < listSize; i++) {
            if (listArray[i] == it) return i; // 找到元素返回索引
        }
        return -1; // 未找到元素返回 -1
    }

    // 判断链表是否为空
    bool isEmpty() const {
        return listSize == 0; // 空链表
    }

    // 获取当前元素的位置
    int currPos() const {
        return curr; // 返回当前指针位置
    }

    // 移动到指定位置
    void moveToPos(int pos) {
        assert(pos >= 0 && pos < listSize); // 检查位置有效性
        curr = pos; // 移动当前指针到指定位置
    }

    // 移动到链表开始位置
    void moveToStart() {
        curr = 0; // 将当前指针移动到开始
    }

    // 移动到链表结束位置
    void moveToEnd() {
        curr = listSize; // 将当前指针移动到末尾
    }

    // 获取链表的长度
    int length() const {
        return listSize; // 返回当前存储的元素数量
    }

    // 打印链表元素
    void print() const {
        for (int i = 0; i < listSize; i++) {
            std::cout << listArray[i] << " "; // 输出元素
        }
        std::cout << std::endl; // 换行
    }
};

int main() {
    ArrayList<int> myList;

    myList.append(10);
    myList.append(20);
    myList.insert(15); // 在索引 1 处插入元素 15

    std::cout << "List after insertions: ";
    myList.print(); // 输出: 10 15 20

    myList.remove(); // 删除当前元素 (15)
    std::cout << "List after removal: ";
    myList.print(); // 输出: 10 20

    std::cout << "Current position: " << myList.currPos() << std::endl; // 输出当前指针位置
    std::cout << "Length of list: " << myList.length() << std::endl; // 输出列表长度

    return 0;
}

链表实现

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <cassert>

// 抽象类 List
template <typename E>
class List {
public:
    virtual ~List() {}

    virtual bool insert(const E& item) = 0;    // 插入元素
    virtual bool append(const E& item) = 0;    // 追加元素
    virtual bool remove(E&) = 0;                // 移除当前元素
    virtual void clear() = 0;                   // 清空列表
    virtual void moveToStart() = 0;             // 移动到列表开始位置
    virtual void moveToEnd() = 0;               // 移动到列表结束位置
    virtual void prev() = 0;                    // 移动到当前元素的前一个元素
    virtual void next() = 0;                    // 移动到当前元素的下一个元素
    virtual int currPos() const = 0;            // 返回当前元素的位置
    virtual void moveToPos(int pos) = 0;        // 移动到指定位置
    virtual int length() const = 0;             // 获取链表长度
};

// 链表节点
template <typename E>
class Link {
public:
    E element;       // 节点值
    Link* next;     // 指向下一个节点的指针

    Link(const E& elemval, Link* nextval = nullptr)
        : element(elemval), next(nextval) {}

    Link(Link* nextval = nullptr)
        : next(nextval) {}
};

// 链表类 LList
template <typename E>
class LList : public List<E> {
private:
    Link<E>* head;  // 指向头节点的指针
    Link<E>* tail;  // 指向尾节点的指针
    Link<E>* curr;  // 当前节点
    int cnt;        // 列表大小

    void init() {
        curr = tail = head = new Link<E>();  // 初始化一个空头节点
        cnt = 0;                              // 列表长度为0
    }

    void removeAll() {
        while (head != nullptr) {
            curr = head;
            head = head->next;                // 逐个移动到下一个节点
            delete curr;                      // 删除当前节点
        }
    }

public:
    LList() { init(); }                       // 构造函数

    ~LList() { removeAll(); delete head; }   // 析构函数

    // 插入元素
    bool insert(const E& it) override {
        curr->next = new Link<E>(it, curr->next);
        if (tail == curr) tail = curr->next; // 如果 curr 是尾节点，更新尾指针
        cnt++;                                 // 增加列表大小
        return true;
    }

    // 追加元素
    bool append(const E& it) override {
        tail = tail->next = new Link<E>(it, nullptr); // 创建新节点并链接到当前尾节点
        cnt++;                                         // 增加列表大小
        return true;
    }

    // 移除当前元素
    bool remove(E& it) override {
        if (curr->next == nullptr) return false; // 无元素可移除
        it = curr->next->element;                 // 获取要移除的节点的元素
        Link<E>* ltemp = curr->next;              // 保存要删除的节点
        if (tail == curr->next)                    // 如果要移除的是尾节点
            tail = curr;                          // 更新尾指针
        curr->next = curr->next->next;            // 跳过要删除的节点
        delete ltemp;                              // 删除节点
        cnt--;                                     // 减少列表大小
        return true;
    }

    // 清空列表
    void clear() override {
        removeAll();                              // 删除所有节点
        init();                                   // 重新初始化
    }

    // 移动到列表开始位置
    void moveToStart() override {
        curr = head;                              // curr 指向头节点
    }

    // 移动到列表结束位置
    void moveToEnd() override {
        curr = tail;                              // curr 指向尾节点
    }

    // 向前移动
    void prev() override {
        if (curr == head) return;                 // 如果 curr 是头节点，则没有前一个元素
        Link<E>* temp = head;
        while (temp->next != curr)               // 遍历找到前一个节点
            temp = temp->next;
        curr = temp;                              // 更新 curr 为前一个节点
    }

    // 向后移动
    void next() override {
        if (curr != tail)                         // 如果不在尾节点
            curr = curr->next;                    // 移动 curr 指向下一个节点
    }

    // 返回当前元素的位置
    int currPos() const override {
        Link<E>* temp = head;
        int pos = 0;
        while (temp != curr) {
            temp = temp->next;
            pos++;
        }
        return pos;                               // 返回当前位置
    }

    // 移动到指定位置
    void moveToPos(int pos) override {
        if (pos < 0 || pos > cnt) return;       // 无效位置
        curr = head;                             // 从头节点开始
        for (int i = 0; i < pos; i++)            // 遍历到指定位置
            curr = curr->next;
    }

    // 获取链表长度
    int length() const override {
        return cnt;                              // 返回链表大小
    }

    // 打印链表元素（辅助函数）
    void printList() {
        Link<E>* temp = head->next;              // 从头节点的下一个开始
        while (temp != nullptr) {
            std::cout << temp->element << " ";   // 打印元素
            temp = temp->next;                    // 移动到下一个节点
        }
        std::cout << std::endl;
    }
};

// 测试链表实现
int main() {
    LList<int> myList;

    myList.append(1);
    myList.append(2);
    myList.append(3);
    myList.insert(0); // 在当前节点（头）插入0

    std::cout << "List after insertions: ";
    myList.printList(); // 输出: 0 1 2 3

    int removedItem;
    myList.remove(removedItem);
    std::cout << "Removed item: " << removedItem << std::endl;

    std::cout << "List after removal: ";
    myList.printList(); // 输出: 1 2 3

    return 0;
}