抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

list的实现

就业学习开发测试手撕STLlist的实现

发布于：2025年7月1日

次浏览

首先介绍一下C++中class和struct的区别吧

  • struct默认访问权限和默认继承方式都是public，对外部都是可见的，方便访问，如果用class还得设置public
  • class都是private
  • struct一般用于简单的数据结构，用于打包一些数据成员
  • class一般用于封装行为和数据的复杂类型，有继承、多态等等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T>
class myList{
private:
    struct Node{
        T data;
        Node* next;
        Node* prev;

        Node(const T& data_, Node* next_ = nullptr, Node* prev_ = nullptr) : data(data_), next(next_), prev(prev_) {}
    };
    Node* head;
    Node* tail;
    size_t current_size;

public:

};

  • 每个节点都是一个结构体，有三样东西

    • data是节点的数据，类型为T
    • next是一个指针，指向下一个节点
    • prev是一个指针，指向上一个节点

  • struct里面也有构造函数，进行了初始化

  • 还有着头节点head和尾部节点prev

1
2
3
4
5
myList() : head(nullptr), tail(nullptr), current_size(0) {}
~myList(){
    clear();
}

同样有构造函数和析构函数，clear下面实现

接下来就是功能的编写了

push_back的实现

1
2
3
4
5
6
7
8
void push_back(const T& value){
    Node* temp = new Node(value, nullptr, tail);
    if (tail) tail -> next = temp;
    else head = temp;

    tail = temp;
    current_size++;
}

  • 首先为传进来的值创建一个节点，这个节点的next指针肯定是空的（因为新加进来的），prev指针，肯定指向之前链表的尾部

  • 这个节点的前后指针处理好了，就要考虑之前链表尾部的节点了，也要处理一下这个节点的前后指针

    • 如果之前是有节点的，那么就把这个节点的next指针也指向新加进来的节点，prev指针已经在创建节点到时候就弄好了
    • 如果之前根本没有节点，也就是tail是空的，那么头节点也就是最新加进来的节点

  • 然后就是尾部节点要更新为最新加进来的节点

  • 尺寸+1

  • 这边注意不能delete temp，这样的话会释放这个节点对应的内存空间，就会破坏链表结构了，但是可以把temp置空，因为temp本来就是一个临时的，但其他除了函数他就会自己销毁，加不加都一样

pop_back和pop_front的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void pop_back(){
    Node* temp = tail -> prev;
    delete tail;
    tail = temp;

    if (tail) tail -> next = nullptr;
    else head = nullptr;
    current_size--;
}

void pop_front(){
    Node* temp = head -> next;
    delete head;
    head = temp;

    if (head) head -> prev = nullptr;
    else tail = nullptr;
    current_size--;
}

这边讲其中一个就行，原理都差不多

  • 首先就是直接删除了尾部节点，并得到新的尾部节点tail
  • 接下去就开始处理新尾部节点的指针问题
  • 然后看看弹出的前一个节点是否存在
    • 如果存在，就把新尾部节点的next指针 为空
    • 如果不存在，说明链表中已经没有节点了，头节点指针 置空
  • 尺寸-1

size获取长度

1
2
3
4
size_t size(){
    return current_size;
}

clear清空list

1
2
3
4
5
6
7
8
9
void clear(){
    while (head){
        Node* temp = head;
        head = head -> next;
        delete temp;
    }
    tail = nullptr;
    current_size = 0;
}
  • 需要考虑节点占用的内存，所以要循环释放，不能直接current_size = 0
  • 从前往后删除，处理完头节点之后记得把尾节点指针也置空
  • 尺寸为0

重写[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T& operator[](size_t index) {
    if (index >= current_size)
        throw std::out_of_range("越界访问");

    Node* temp = head;
    for (size_t i = 0; i < index; i++) {
        temp = temp->next;
    }
    return temp->data;
}

const T& operator[](size_t index) const {
    if (index >= current_size)
        throw std::out_of_range("越界访问");

    Node* temp = head;
    for (size_t i = 0; i < index; i++) {
        temp = temp->next;
    }
    return temp->data;
}
  • 因为链表的节点都是相互连接的，从前往后即可

empty 检测链表是否为空

1
2
3
bool empty(){
    return current_size == 0;
}

find函数是找值所对应节点的数据的地址

1
2
3
4
5
6
7
8
9
T* find(const T& val){
    Node* temp = head;
    while (temp && temp -> data != val){
        temp = temp -> next;
    }
    if (temp) return &temp -> data;
    else return nullptr;
}

  • 就是循环遍历直到找到那个值对应的第一个节点，然后返回节点数据的指针，也就是地址

remove函数的实现，去除值为val的第一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void remove(const T& val){
    Node* temp = head;
    while (temp && temp -> data != val){
        temp = temp -> next;
    }
    if(!temp) return;
    if (temp != head && temp != tail){
        temp -> prev -> next = temp -> next;
        temp -> next -> prev = temp -> prev;
    } else if (temp == head && temp == tail){
        head = nullptr;
        tail = nullptr;
    } else if (temp == head){
        head = head -> next;
        head -> prev = nullptr;
    } else {
        tail = tail -> prev;
        tail -> next = nullptr;
    }
    delete temp;
    temp = nullptr;
    current_size--;
}
  • 首先要先找到这个节点，找不到就直接return
  • 然后要删除这个节点的时候，要分四种情况
    • 如果是中间节点的话，要处理好这个节点的前节点和后节点的指针关系
    • 如果只有一个节点的情况下（即是头节点，又是尾节点），要把头尾指针置空
    • 如果只是头节点，处理好第二个节点的prev指针，同时更新头节点
    • 如果只是尾节点，处理好倒二个节点的next指针，同时更新尾节点
  • 最后释放temp指向的内存空间（delete释放，但实际上temp仍指向这块内存），并且把这个指针置空（可选，防止悬挂指针）
  • 尺寸-1

然后是迭代器接口的编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node* begin(){
    return head;
}

Node* end(){
    return nullptr;
}

const Node* begin() const {
    return head;
}

const Node* end() const {
    return nullptr;
}

那肯定还是比不上标准的STL库，完整代码如下

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
#include <stdexcept>
#include <cstddef>
#include <algorithm>
using namespace std;

template <typename T>
class myList{
private:
    struct Node{
        T data;
        Node* next;
        Node* prev;

        Node(const T& data_, Node* next_ = nullptr, Node* prev_ = nullptr) : data(data_), next(next_), prev(prev_) {}
    };
    Node* head;
    Node* tail;
    size_t current_size;

public:
    myList() : head(nullptr), tail(nullptr), current_size(0) {}
    ~myList(){
        clear();
    }

    void push_back(const T& value){
        Node* temp = new Node(value, nullptr, tail);
        if (tail) tail -> next = temp;
        else head = temp;

        tail = temp;
        current_size++;
    }

    void pop_back(){
        Node* temp = tail -> prev;
        delete tail;
        tail = temp;

        if (tail) tail -> next = nullptr;
        else head = nullptr;
        current_size--;
    }

    void pop_front(){
        Node* temp = head -> next;
        delete head;
        head = temp;

        if (head) head -> prev = nullptr;
        else tail = nullptr;
        current_size--;
    }

    size_t size(){
        return current_size;
    }

    void clear(){
        while (head){
            Node* temp = head;
            head = head -> next;
            delete temp;
        }
        tail = nullptr;
        current_size = 0;
    }

    T& operator[](size_t index) {
        if (index >= current_size)
            throw std::out_of_range("越界访问");

        Node* temp = head;
        for (size_t i = 0; i < index; i++) {
            temp = temp->next;
        }
        return temp->data;
    }

    const T& operator[](size_t index) const {
        if (index >= current_size)
            throw std::out_of_range("越界访问");

        Node* temp = head;
        for (size_t i = 0; i < index; i++) {
            temp = temp->next;
        }
        return temp->data;
    }

    bool empty(){
        return current_size == 0;
    }

    T* find(const T& val){
        Node* temp = head;
        while (temp && temp -> data != val){
            temp = temp -> next;
        }
        if (temp) return &temp -> data;
        else return nullptr;
    }

    void remove(const T& val){
        Node* temp = head;
        while (temp && temp -> data != val){
            temp = temp -> next;
        }
        if(!temp) return;
        if (temp != head && temp != tail){
            temp -> prev -> next = temp -> next;
            temp -> next -> prev = temp -> prev;
        } else if (temp == head && temp == tail){
            head = nullptr;
            tail = nullptr;
        } else if (temp == head){
            head = head -> next;
            head -> prev = nullptr;
        } else {
            tail = tail -> prev;
            tail -> next = nullptr;
        }
        delete temp;
        temp = nullptr;
        current_size--;
    }

    Node* begin(){
        return head;
    }

    Node* end(){
        return nullptr;
    }

    const Node* begin() const {
        return head;
    }

    const Node* end() const {
        return nullptr;
    }

};

测试用例如下

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
#include <iostream>
#include <string>


int main() {
    myList<int> lst;

    std::cout << "== 测试 push_back ==" << std::endl;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);

    for (auto p = lst.begin(); p; p = p->next) {
        std::cout << p->data << " ";
    }
    std::cout << std::endl;

    std::cout << "== 测试 pop_back ==" << std::endl;
    lst.pop_back();

    for (auto p = lst.begin(); p; p = p->next) {
        std::cout << p->data << " ";
    }
    std::cout << std::endl;

    std::cout << "== 测试 pop_front ==" << std::endl;
    lst.pop_front();

    for (auto p = lst.begin(); p; p = p->next) {
        std::cout << p->data << " ";
    }
    std::cout << std::endl;

    std::cout << "== 测试 operator[] ==" << std::endl;
    try {
        std::cout << "lst[0] = " << lst[0] << std::endl;
        std::cout << "lst[1] = " << lst[1] << std::endl; // 越界
    } catch (const std::out_of_range& e) {
        std::cout << "异常捕获：" << e.what() << std::endl;
    }

    std::cout << "== 测试 find ==" << std::endl;
    int* p = lst.find(20);
    if (p) std::cout << "找到元素: " << *p << std::endl;
    else std::cout << "未找到元素" << std::endl;

    std::cout << "== 测试 remove ==" << std::endl;
    lst.push_back(40);
    lst.push_back(50);
    lst.remove(40); // 删除中间
    lst.remove(20); // 删除头
    lst.remove(50); // 删除尾

    for (auto p = lst.begin(); p; p = p->next) {
        std::cout << p->data << " ";
    }
    std::cout << std::endl;

    std::cout << "== 测试 clear ==" << std::endl;
    lst.clear();
    std::cout << "是否为空: " << (lst.empty() ? "是" : "否") << std::endl;

    return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
== 测试 push_back ==
10 20 30 
== 测试 pop_back ==
10 20 
== 测试 pop_front ==
20 
== 测试 operator[] ==
lst[0] = 20
lst[1] = 异常捕获：越界访问
== 测试 find ==
找到元素: 20
== 测试 remove ==

== 测试 clear ==
是否为空: 是

更新于：2025年7月4日

评论

评论区