Appearance
简介
链表由若干节点前后连接而成。
- 「数组」支持
访问任意一个位置的元素(随机访问),而「链表」不支持。 - 「链表」支持在任意位置
插入或删除元素,而「数组」不支持。
链表节点
用一个结构体表示链表的节点,其中可以存储任意数据。每个节点有 prev
和 next
两个指针,指向前后相邻的节点。
cpp
struct Node {
int val; // 数据(可以是任意类型)
Node *prev, *next; // 指针
};
初始化
初始化链表时,额外建立两个节点 head
和 tail
代表链表的头尾,把实际节点存储在 head
与 tail
之间,简化链表边界的判断。
cpp
Node *head, *tail;
void init() {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = next;
}
插入/删除节点
如何在
建立节点
删除节点运用到类似的方法。
cpp
// 在节点 u 后插入数据为 val 的新节点
void insert(Node *u, int val) {
v = new Node(), v->val = val; // step 1
u->next->prev = v, v->next = u->next; // step 2
u->next = v, v->prev = u; // step 3
}
// 删除节点 p
void remove(Node *p) {
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
}
查找节点
cpp
// 返回链表中第一个出现的值为 val 的节点指针
Node* indexOf(int val) {
for (Node *p = head->next; p != tail; p = p->next)
if (p->val == val) return p;
return NULL;
}
清空链表
cpp
void clear() {
while(head != tail) {
head = head->next;
delete head->prev;
}
delete tail;
}
使用数组模拟链表
使用指针需要动态分配空间,效率低且不稳定。
使用数组模拟链表是更可靠的做法。
cpp
struct Node {
int val;
int prev, next;
} node[];
int head, tail, tot;
void init() {
head = 0, tail = 1, tot = 2;
node[head].next = tail;
node[tail].prev = head;
}
void insert(int p, int val) {
int q = ++ tot; node[q].val = val;
node[node[p].next].prev = q;
node[q].next = node[p].next;
node[p].next = q;
node[q].next = p;
}
void remove(int p) {
node[node[p].prev].next = node[p].next;
node[node[p].next].prev = node[p].prev;
}
int indexOf(int val) {
for (int p = node[head].next; p != tail; p = node[p].next)
if (node[p].val == val)
return p;
return -1;
}
void clear() {
head = tail = tot = 0;
memset(node, 0, sizeof node);
}