侵入式链表
将链表的指针域放在数据结构中，而不是在链表节点中
适用于一个数据结构需要在多个链表中存在的情况
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| struct ListNode {
ListNode *next;
explicit ListNode() : next(nullptr) {}
};
template <class T> struct Node {
T val;
ListNode node;
explicit Node(T val) : val(val) {}
};
template <class T> struct List {
ListNode *head;
List() : head(nullptr) {}
void push_front(T val) {
Node<T> *node = new Node<T>(val);
node->node.next = head;
head = &node->node;
}
};
|
变量使用 C 语言的宏定义，可以通过 struct 的成员变量指针获取到结构体的地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define list_entry(type, member, ptr) container_of(type, member, ptr)
#define container_of(type, member, ptr) \
({ \
const typeof(((type *)0)->member) *__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); \
})
#define offsetof(type, member) ((size_t) & ((type *)0)->member)
int main() {
List<int> list = List<int>();
for (int i = 0; i < 10; i++) {
list.push_front(i);
}
auto *head = list.head;
while (head != nullptr) {
std::cout << list_entry(Node<int>, node, head)->val << std::endl;
head = head->next;
}
return 0;
}
|
trick
在 C 语言的宏定义中，({}) 是 GNU C 扩展中的一种语法，称为 语句表达式（Statement Expressions）。允许在宏或代码中使用多个语句，并返回最后一行的一个值（使用这种语法最后一行需要加上;，如果只使用 {}，也可以返回最后一行的值，同时不用加上;）
下面两种写法都是合法的
1
2
| int a = {1};
int b = ({1;});
|