链表
实现
构建链表
单向链表
单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用于连接当前节点和下一节点。
struct Node {
int value;
Node *next;
};双向链表
双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个节点、当前节点、下一个节点。
struct Node {
int value;
Node *left;
Node *right;
};向链表写入数据
单向链表
-
初始化待插入的数据
node ； -
将
node 的next 指针指向p 的下一个节点； -
将
p 的next 指针指向node 。void insert_node(int i, Node *p) { Node *node = new Node; node->value = i; node->next = p->next; p->next = node; }单向循环链表
-
初始化待插入的数据
node ； -
判断给定链表
p 是否为空； -
若为空，则将
node 的next 指针和p 都指向自己； -
否则，将
node 的next 指针指向p 的下一个节点； -
将
p 的next 指针指向node 。void insert_node(int i, Node *p) { Node *node = new Node; node->value = i; node->next = NULL; if (p == NULL) { p = node; node->next = node; } else { node->next = p->next; p->next = node; } }双向循环链表
在向双向循环链表插入数据时，除了要判断给定链表是否为空外，还要同时修改左、右两个指针。
-
初始化待插入的数据
node ； -
判断给定链表
p 是否为空； -
若为空，则将
node 的left 和right 指针，以及p 都指向自己； -
否则，将
node 的left 指针指向p ; -
将
node 的right 指针指向p 的右节点; -
将
p 的右节点的left 指针指向node ; -
将
p 的right 指针指向node 。void insert_node(int i, Node *p) { Node *node = new Node; node->value = i; if (p == NULL) { p = node; node->left = node; node->right = node; } else { node->right = p; node->right = p->right; p->right->left = node; p->right = node; } }从链表中删除数据
单向（循环）链表 :
设待删除节点为
-
将
p 的下一个节点的值赋给p ，以抹掉{p}_{value} ; -
新建一个临时节点
t 存放p_{next} 的地址 ; -
将
p 的next 指针指向p 的下下个节点，以抹掉p_{next} ; -
删除
t 。此时虽然原节点p 的地址还在使用，删除的是原节点p_{next} 的地址，但p 的数据被p->next 覆盖，p 名存实亡。void delete_node(Node *p) { p->value = p->next->value; Node *t = p->next; p->next = p->next->next; delete t; }双向循环链表
-
将
p 的左节点的右指针指向p 的右节点； -
将
p 的右节点的左指针指向p 的左节点； -
新建一个临时节点
t 存放p 的地址； -
将
p 的右节点地址赋值给p ，以避免p 变成悬垂指针； -
删除
t 。void delete_node(Node *&p) { p->left->right = p->right; p->right->left = p->left; Node *t = p; p = p->right; delete t; }
技巧
异或链表
异或链表（XOR Linked List）本质上还是双向链表，但它利用按位异或的值，仅用一个指针的大小便可实现双向链表的功能。
在结构体 Node 中定义