单向链表的C++实现(增删改查)

---

tags: C++ DSA SingleLinkedList

写在前面

温习一下单链表, 然后通过C++实现出来, 虽然花了一些时间在不必要的报错上, 但是对于熟悉C++的面向对象,链表操作等还是很有必要的, 下面给出完整代码:dsa/Single_Linked_List.cpp at main · Apocaly-pse/dsa (github.com).

几点创新

1. 以传入数组方式构造链表, 使构造变得方便.
2. 重载输出操作符, 方便查看结果.
3. 重载[]下标操作符以访问节点的指针, 实现修改任意位置的节点值的函数, 使用起来更加方便.
4. 在插入和删除函数的实现上, 先实现对任意位置的增删, 然后给出删除头尾的函数实现, 在一定程度上简化代码.
5. 配合析构函数释放链表占用的内存, 参考¹.

代码

声明(结点和链表)

先来看类的声明部分:

#ifndef Linked_List
#define Linked_List
#include 
#include 


using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next1) : val(x), next(next1) {}
};

class LinkedList {
public:
    LinkedList() : head(nullptr) {}
    LinkedList(int head_val) : head(new ListNode(head_val)) {}
    LinkedList(int head_val, vector<int> rest);
    LinkedList(vector<int> nodes);
    
    ~LinkedList();

    void print();
    ListNode* first();
    ListNode* last();
    int len();

    // visit by pos
    /* int& operator[](int pos); */
    ListNode* operator[](int pos);
    ListNode* visit(int pos);

    // insert by pos
    void insert(int pos, int val);
    void append(int val);
    void add2head(int val);

    // delete by pos
    void pop(int pos);
    void pop_back();
    void pop_front();
    
    // delete by value
    void remove(int val, int cnt = 1);           // delete val cnt times
    void modify(int val, int node, int cnt = 1); // modify val->node cnt times
    int find(int node);                          // not found:-1


private:
    ListNode* head;
};

ostream& operator<<(ostream& os, ListNode* lp);

#endif // !LinkedList
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

生成单链表(构造函数)

1. 默认构造函数通过为头结点传入nullptr的方式完成.
2. 有参构造, 3种:
   • 传入数值作为链表头结点的值.
   • 传入头结点以及剩余节点的数组
   • 直接读取链表各个值组成的数组.

直接遍历读取然后向后添加节点值即可.

LinkedList::LinkedList(int head_val, vector<int> rest) {
    head = new ListNode(head_val);
    auto cur = head;
    for (auto i : rest) {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
}

LinkedList::LinkedList(vector<int> nodes) {
    if (nodes.empty()) return;
    head = new ListNode(nodes[0]);
    auto cur = head;
    for (auto i = nodes.begin() + 1; i < nodes.end(); i++) {
        cur->next = new ListNode(*i);
        cur = cur->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

析构函数

需要设置临时变量来读取待释放内存的当前节点的next指针信息, 然后循环删除即可. 需要注意最后的一个节点需要在循环体外删除.

LinkedList::~LinkedList() {
    ListNode* cur;
    while (head->next) {
        cur = head->next;
        delete head;
        head = cur;
    }
    delete head;
}
1
2
3
4
5
6
7
8
9

输出格式化

这里通过节点进行输出, 但是要注意, 重载的操作符为全局的而非成员函数.

ostream& operator<<(ostream& os, ListNode* lp) {
    if (lp == nullptr) return os << "∅" << endl;
    ListNode* cur = lp;
    while (cur != nullptr) {
        os << cur->val << " -> ";
        cur = cur->next;
    }
    os << "∅";
    return os << endl;
}

void LinkedList::print() { cout << head; }
1
2
3
4
5
6
7
8
9
10
11
12

头尾结点和长度

这两个比较简单, 直接遍历即可:

ListNode* LinkedList::first() { return head; }

ListNode* LinkedList::last() {
    auto cur = head;
    while (cur->next) cur = cur->next;
    return cur;
}

int LinkedList::len() {
    int size = 0;
    auto cur = head;
    while (cur) {
        size++;
        cur = cur->next;
    }
    return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

重载下标运算符访问(更改)节点值

这个算是一个比较独特的点, 针对链表进行下标操作, 然后通过下标给出任意位置的结点值, 并且可以通过下标修改对应位置节点的值.

下面给出两种实现, 我个人愿意采用第二种, 因为第一种是针对数值的, 返回的为节点的数值, 但是不能对节点进行修改值的操作, 而第二种就可以通过读取到的节点指针操作对应节点的值.

注意, 这两个版本因为形参列表是一样的, 所以不能共存, 在GitHub给出的代码中我加上了注释.

int& LinkedList::operator[](int pos) {
    if (head == nullptr) {
        cerr << "Attempt to get value from a NULL LinkedList\n";
        exit(1);
    }
    if (pos > len() - 1 || pos < 0) {
        cerr << "Wrong pos!\n";
        exit(1);
    }
    auto cur = head;
    while (pos--) cur = cur->next;
    return cur->val;
}

ListNode* LinkedList::operator[](int pos) {
    if (head == nullptr) {
        cerr << "Attempt to get value from a NULL LinkedList\n";
        exit(1);
    }
    if (pos > len() - 1 || pos < 0) {
        cerr << "Wrong pos!\n";
        exit(1);
    }
    auto cur = head;
    while (pos--) cur = cur->next;
    return cur;
}
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

增加元素

这里给出了对任意位置处进行增加元素, 以及两个特殊版本:

1. 头插法
2. 尾插法

void LinkedList::insert(int pos, int val) {
    if (pos >= len()) {
        auto cur = last();
        cur->next = new ListNode(val);
    } else if (pos <= 0) {
        auto cur = head;
        head = new ListNode(val);
        head->next = cur;
    } else {
        auto pre = head;
        while (--pos) {
            pre = pre->next;
        }
        auto cur = pre->next;
        pre->next = new ListNode(val, cur);
    }
}

void LinkedList::add2head(int val) { insert(0, val); }
void LinkedList::append(int val) { insert(len(), val); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除元素(基于位置)

同插入函数的实现思路, 这里给出了基于位置的删除链表中元素的函数实现.

void LinkedList::pop(int pos) {
    if (head == nullptr) {
        cout << "Attempt to delete a NULL LinkedList!" << endl;
    } else if (head->next == nullptr) {
        head = nullptr;
    } else {
        if (pos >= len() - 1) {
            auto cur = head;
            while (cur->next && cur->next->next) cur = cur->next;
            cur->next = nullptr;
        } else if (pos <= 0) {
            auto cur = head->next;
            delete head;
            head = cur;
        } else {
            auto cur = head;
            while (--pos) cur = cur->next;
            cur->next = cur->next->next;
        }
    }
}
void LinkedList::pop_front() { pop(0); }
void LinkedList::pop_back() { pop(len()); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

查找元素

在给出基于值的结点删除函数之前, 先给出查找元素的函数, 之后实现删除元素函数时就可以调用了find()了.

int LinkedList::find(int node) {
    if (head == nullptr) return -1;
    auto cur = head;
    int pos{};
    while (cur) {
        if (cur->val == node) return pos;
        pos++;
        cur = cur->next;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11

删除元素(基于值)

这里我给出了一个默认参数, cnt, 默认值为1, 用于指定删除的次数.

void LinkedList::remove(int val, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to delete\n";
            break;
        } else
            pop(idx);
    } while (--cnt);
}
1
2
3
4
5
6
7
8
9
10

这里用while也是可以的, 但是为了直观还是写成do...while了.

修改元素

这里也要用到find()函数, 注意下标访问的时候要先解引用this, 然后通过下标运算符取值进行修改.

// modify val->node cnt times
void LinkedList::modify(int val, int node, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to modify\n";
            break;
        } else {
            /* visit(idx)->val = node; */
            (*this)[idx]->val = node;
        }
    } while (--cnt);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

调用方法

最后给出调用方法, 大家也可以测试一下, 看看有没有什么改进建议.

// === test func === ===//
void test_ctor() {
    LinkedList ll1(12);
    ll1.print();

    LinkedList ll2(1, {2, 3, 4});
    ll2.print();

    LinkedList ll3({1, 2, 3, 4});
    ll3.print();
    /*
       12 -> ∅
        1 -> 2 -> 3 -> 4 -> ∅
        1 -> 2 -> 3 -> 4 -> ∅
    */
}

void test_func() {
    LinkedList ll1({1, 2, 3, 4});
    /* LinkedList ll1({1, 2}); */
    /* LinkedList ll1; */
    cout << "ll1=";
    ll1.print();
    cout << "len(ll1)=" << ll1.len() << endl;
    /* cout << ll1.first()->val << endl; */
    /* cout << ll1.last()->val << endl; */
    /* ll1.append(5); */
    /* ll1.pop(0); */
    /* ll1.pop_back(); */
    /* ll1.insert(4, 12); */
    /* ll1.add2head(9); */
    /* cout << "ll1.find(2):" << ll1.find(2) << endl; */
    /* cout << "ll1.find(12):" << ll1.find(12) << endl; */
    ll1.append(1);
    /* ll1.remove(1, 3); */
    cout << "ll1[0]=" << ll1[0]->val << endl;
    /* cout << "ll1[9]=" << ll1[9] << endl; */
    ll1.modify(1, 11, 3);
    ll1.print();
}
int main(int argc, char* argv[]) {
    /* test_ctor(); */
    test_func();
    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

ref

---

1. 单链表的析构函数_jiang111_111shan的博客-CSDN博客_链表的析构函数; ↩︎