# 来用 C++ 写一个单链表吧！

## 链表结点

`````` 1template <class EleTy>
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}
``````

## 链表构造、解构函数

`````` 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  //  空构造函数
19
20  // 析构函数
``````

## 支持初始化器列表

`````` 1  // 用初始值构造
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  }
``````

## 拷贝构造函数

`````` 1  // 由于定义了析构函数，因此必须定义拷贝构造函数
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// 或者
``````

## 拷贝赋值函数

`````` 1  // 由于定义了析构函数，因此必须定义拷贝赋值函数
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;
``````

## 移动构造和移动赋值

`````` 1  // 支持移动
3    other.dummy.next = nullptr;
4  }
5  // 由于定义了移动构造函数，因此必须同时定义移动赋值函数
7    this->dummy = other.dummy;
8    other.dummy.next = nullptr;
9    return *this;
10  }
``````

## 实现链表功能

`````` 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>
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  //  空构造函数
57
58  // 用初始值构造
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  // 析构函数
70
71  // 由于定义了析构函数，因此必须定义拷贝构造函数
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  // 由于定义了析构函数，因此必须定义拷贝赋值函数
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  // 支持移动
96    other.dummy.next = nullptr;
97  }
98  // 由于定义了移动构造函数，因此必须同时定义移动赋值函数
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);
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
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}
``````

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