来用 C++ 写一个单链表吧!

链表结点

首先,我们定义链表结点 Node:

 1template <class EleTy>
 2class LinkedList {
 3 public:
 4  class Node {
 5   public:
 6    EleTy val;
 7    Node* next{nullptr};
 8    explicit Node() noexcept(true) {}
 9    explicit Node(EleTy val) noexcept(true) : val(val) {}
10    explicit Node(EleTy val, Node* next) noexcept(true)
11        : val(val), next(next) {}
12  };
13}

这里需要注意,对于 POD 类型,尽量设置一个默认值(尤其是关键的字段),从而避免栈上初始化沾染随机数据。

单链表有两个域:值和下一个结点。

链表构造、解构函数

首先需要一个 dummy head (伪头结点),可以帮我们省很多事情。

析构函数调用私有的 dispose 方法,将占据的资源释放。

 1 private:
 2  //  伪头结点
 3  Node dummy;
 4
 5  // 释放内存
 6  void dispose() noexcept(true) {
 7    auto llcur = dummy.next;
 8    while (llcur) {
 9      Node* next = llcur->next;
10      delete llcur;
11      llcur = next;
12    }
13    dummy.next = nullptr;
14  }
15
16 public:
17  //  空构造函数
18  LinkedList() {}
19
20  // 析构函数
21  ~LinkedList() { dispose(); }

支持初始化器列表

为了使用起来更方便,增加初始化器列表:

 1  // 用初始值构造
 2  LinkedList(initializer_list<EleTy> list) {
 3    auto it = list.begin();
 4    auto llcur = &dummy;
 5    while (it != list.end()) {
 6      llcur->next = new Node(*it);
 7      llcur = llcur->next;
 8      it++;
 9    }
10  }

拷贝构造函数

由于定义了析构函数,且我们的类确实动态分配了内存,所以应当定义拷贝构造函数实现深拷贝,避免 Double Free.

 1  // 由于定义了析构函数,因此必须定义拷贝构造函数
 2  LinkedList(LinkedList const& other) {
 3    auto othercur = other.dummy.next;
 4    auto tail_ = tail(true);
 5    while (othercur) {
 6      tail_->next = new Node(othercur->val);
 7      tail_ = tail_->next;
 8      othercur = othercur->next;
 9    }
10  }

这样对于类似

1LinkedList<int> h2 = h1;
2// 或者
3LinkedList<int> h3(h1);

这样的使用,也能从容应对。拷贝构造不用我们调用 dispose(),因为它的调用时机决定了尚未额外使用堆内存。

拷贝赋值函数

同理定义拷贝赋值函数。

 1  // 由于定义了析构函数,因此必须定义拷贝赋值函数
 2  LinkedList& operator=(LinkedList& other) {
 3    dispose();
 4    auto othercur = other.dummy.next;
 5    auto tail_ = tail(true);
 6    while (othercur) {
 7      tail_->next = new Node(othercur->val);
 8      tail_ = tail_->next;
 9      othercur = othercur->next;
10    }
11    return *this;
12  }

考虑到会有这样的使用:

1LinkedList<int> h2({1,2,3});
2h2 = h1;

因此我们必须对 h2 进行资源释放然后再拷贝 h1 的资源。这样保证 h2 所占据的资源会被正确释放,然后通过我们定义的拷贝赋值函数装载 h1 的值。

移动构造和移动赋值

为了支持移动,我们可以选择定义移动构造函数和移动赋值函数,这样更加高效。但二者也必须同时定义。

 1  // 支持移动
 2  LinkedList(LinkedList&& other) : dummy(other.dummy) {
 3    other.dummy.next = nullptr;
 4  }
 5  // 由于定义了移动构造函数,因此必须同时定义移动赋值函数
 6  LinkedList& operator=(LinkedList&& other) {
 7    this->dummy = other.dummy;
 8    other.dummy.next = nullptr;
 9    return *this;
10  }

可以看到,移动的情况,我们接收一个右值,直接夺取了其 dummy 成员的所有权。不必重复分配。

实现链表功能

链表的大多数操作都比较简单,但交换是比较复杂的一个,因此我们着重实现一下交换:

 1  void _swap(Node* aPrev, Node* a, Node* bPrev, Node* b) {
 2    auto aNext = a->next, bNext = b->next;
 3
 4    // 情况1 aPrev-->a-->b-->bNext
 5    if (aNext == b) {
 6      aPrev->next = b;
 7      b->next = a;
 8      a->next = bNext;
 9    }
10    // 情况2 bPrev-->b-->a-->aNext
11    else if (bNext == a) {
12      bPrev->next = a;
13      a->next = b;
14      b->next = aNext;
15    }
16    // 情况3 aPrev->a-->aNext...->bPrev-->b-->bNext
17    else {
18      aPrev->next = b;
19      bPrev->next = a;
20      a->next = bNext;
21      b->next = aNext;
22    }
23  }
24
25  // 获取一个节点的前一个节点
26  Node* prevOf(Node* a) {
27    auto cur = &dummy;
28    while (cur->next) {
29      if (cur->next == a) {
30        return cur;
31      }
32      cur = cur->next;
33    }
34    return nullptr;
35  }
36  // 交换两个节点
37  void swap(Node* a, Node* b) {
38    auto aPrev = prevOf(a), bPref = prevOf(b);
39    _swap(aPrev, a, bPref, b);
40  }

链表中两个节点的交换需要分两个大类讨论。

  • 相邻。则需要三步完成交换,根据相邻的先后位置决定三步如何完成。

  • 不相邻。则比较简单,直接建立新的链接即可。

实现其他功能

这里我直接给出完整的代码吧:

  1template <class EleTy>
  2class LinkedList {
  3 public:
  4  class Node {
  5   public:
  6    EleTy val;
  7    // 确保默认值是 nullptr
  8    Node* next{nullptr};
  9    explicit Node() noexcept(true) {}
 10    explicit Node(EleTy val) noexcept(true) : val(val) {}
 11    explicit Node(EleTy val, Node* next) noexcept(true)
 12        : val(val), next(next) {}
 13  };
 14
 15 private:
 16  //  伪头结点
 17  Node dummy;
 18
 19  // 释放内存
 20  void dispose() noexcept(true) {
 21    auto llcur = dummy.next;
 22    while (llcur) {
 23      Node* next = llcur->next;
 24      delete llcur;
 25      llcur = next;
 26    }
 27    dummy.next = nullptr;
 28  }
 29
 30  void _swap(Node* aPrev, Node* a, Node* bPrev, Node* b) {
 31    auto aNext = a->next, bNext = b->next;
 32
 33    // 情况1 aPrev-->a-->b-->bNext
 34    if (aNext == b) {
 35      aPrev->next = b;
 36      b->next = a;
 37      a->next = bNext;
 38    }
 39    // 情况2 bPrev-->b-->a-->aNext
 40    else if (bNext == a) {
 41      bPrev->next = a;
 42      a->next = b;
 43      b->next = aNext;
 44    }
 45    // 情况3 aPrev->a-->aNext...->bPrev-->b-->bNext
 46    else {
 47      aPrev->next = b;
 48      bPrev->next = a;
 49      a->next = bNext;
 50      b->next = aNext;
 51    }
 52  }
 53
 54 public:
 55  //  空构造函数
 56  LinkedList() {}
 57
 58  // 用初始值构造
 59  LinkedList(initializer_list<EleTy> list) {
 60    auto it = list.begin();
 61    auto llcur = &dummy;
 62    while (it != list.end()) {
 63      llcur->next = new Node(*it);
 64      llcur = llcur->next;
 65      it++;
 66    }
 67  }
 68  // 析构函数
 69  ~LinkedList() { dispose(); }
 70
 71  // 由于定义了析构函数,因此必须定义拷贝构造函数
 72  LinkedList(LinkedList const& other) {
 73    auto othercur = other.dummy.next;
 74    auto tail_ = tail(true);
 75    while (othercur) {
 76      tail_->next = new Node(othercur->val);
 77      tail_ = tail_->next;
 78      othercur = othercur->next;
 79    }
 80  }
 81
 82  // 由于定义了析构函数,因此必须定义拷贝赋值函数
 83  LinkedList& operator=(LinkedList& other) {
 84    dispose();
 85    auto othercur = other.dummy.next;
 86    auto tail_ = tail(true);
 87    while (othercur) {
 88      tail_->next = new Node(othercur->val);
 89      tail_ = tail_->next;
 90      othercur = othercur->next;
 91    }
 92    return *this;
 93  }
 94  // 支持移动
 95  LinkedList(LinkedList&& other) : dummy(other.dummy) {
 96    other.dummy.next = nullptr;
 97  }
 98  // 由于定义了移动构造函数,因此必须同时定义移动赋值函数
 99  LinkedList& operator=(LinkedList&& other) {
100    this->dummy = other.dummy;
101    other.dummy.next = nullptr;
102    return *this;
103  }
104  Node* first(EleTy val) {
105    auto llcur = dummy.next;
106    while (llcur) {
107      if (llcur->val == val) {
108        return llcur;
109      }
110      llcur = llcur->next;
111    }
112    return nullptr;
113  }
114  void push_back(EleTy val) { tail(true)->next = new Node(val); }
115  void push_back(initializer_list<EleTy> vals) {
116    auto it = vals.begin();
117    auto cur = tail(true);
118    while (it != vals.end()) {
119      cur->next = new Node(*it);
120      cur = cur->next;
121      it++;
122    }
123  }
124  // 获取尾部元素。如果 get_dummy 为真,则允许获取伪头节点
125  Node* tail(bool get_dummy = false) {
126    Node* prev = get_dummy ? &dummy : nullptr;
127    auto llcur = dummy.next;
128    while (llcur) {
129      prev = llcur;
130      llcur = llcur->next;
131    }
132    return prev;
133  }
134  Node* prevTail() {
135    Node* prev = &dummy;
136    auto llcur = prev->next;
137    while (llcur->next) {
138      prev = llcur;
139      llcur = llcur->next;
140    }
141    return prev;
142  }
143  void show(string prefix = "list ") {
144    auto llcur = dummy.next;
145    std::cout << prefix << "at " << this << " = ";
146    while (llcur) {
147      std::cout << llcur->val << " ";
148      llcur = llcur->next;
149    }
150    std::cout << std::endl;
151  }
152  // 获取一个节点的前一个节点
153  Node* prevOf(Node* a) {
154    auto cur = &dummy;
155    while (cur->next) {
156      if (cur->next == a) {
157        return cur;
158      }
159      cur = cur->next;
160    }
161    return nullptr;
162  }
163  // 交换两个节点
164  void swap(Node* a, Node* b) {
165    auto aPrev = prevOf(a), bPref = prevOf(b);
166    _swap(aPrev, a, bPref, b);
167  }
168  void insert_after(Node* pos, EleTy val) {
169    auto newNode = new Node(val);
170    newNode->next = pos->next;
171    pos->next = newNode;
172  }
173  void insert_at(int index, EleTy val) {
174    assert(index >= 0);
175    auto cur = &dummy;
176    while (index-- > 0) {
177      cur = cur->next;
178    }
179    insert_after(cur, val);
180  }
181};
182int main() {
183  LinkedList h1({1, 2, 3, 4});
184  h1.swap(h1.first(4), h1.first(3));
185  h1.show("h1: ");
186  h1.push_back({1, 2});
187  h1.show("h1: ");
188  h1.insert_after(h1.first(3), 9);
189  h1.insert_at(0, 8);
190  LinkedList<int> h3;
191  h3 = std::move(h1);
192  h1.show("h1: ");
193  h3.show("h3: ");
194
195  LinkedList h4({1, 2, 3, 4});
196  h4 = h3;
197  h4.show("h4: ");
198
199  LinkedList<string> h2({"aa", "bb"});
200  h2.swap(h2.first("aa"), h2.first("bb"));
201  h2.show("h2: ");
202  h2.push_back({"cc"});
203  h2.push_back("dd");
204  h2.show("h2: ");
205  return 0;
206}

编译时,可以采用 -fsanitize=address 选项,或者使用 valgrind

1valgrind --tool=memcheck --leak-check=full

这样能够第一时间发现内存泄漏。

个人感觉现在工具这么完善了,内存泄漏或者重复释放的检测基本上(只要各个分支都覆盖执行)问题不大。困难的地方不在于定位内存泄漏的分配位置,而在于定位泄漏的根本原因。我的经验是使用二分法。

如果有可以改进的地方,还望读者赐教!

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志