实现

构建链表

单向链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用于连接当前节点和下一节点。

CPP

struct Node {
	int value;
	Node *next;
};

双向链表

双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个节点、当前节点、下一个节点。

CPP

struct Node {
	int value;	
	Node *left;
	Node *right;
};

向链表写入数据

单向链表

初始化待插入的数据 $node$ ；
将 $node$ 的 $next$ 指针指向 $p$ 的下一个节点；
将 $p$ 的 $next$ 指针指向 $node$ 。

CPP

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$ 。

CPP

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$ 。

CPP

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_{next}

的值覆盖给

p

即可，从此同时更新

p

的下下个节点。

将 $p$ 的下一个节点的值赋给 $p$ ，以抹掉 ${p}_{value}$ ;
新建一个临时节点 $t$ 存放 $p_{next}$ 的地址 ;
将 $p$ 的 $next$ 指针指向 $p$ 的下下个节点，以抹掉 $p_{next}$ ;
删除 $t$ 。此时虽然原节点 $p$ 的地址还在使用，删除的是原节点 $p_{next}$ 的地址，但 $p$ 的数据被 $p->next$ 覆盖， $p$ 名存实亡。

CPP

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$ 。

CPP

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 中定义

lr = left\operatorname{xor}right

，即前后两个地址的按位异或值。正向遍历时用前一个元素的地址异或当前节点的

lr

可得到后一个元素的地址，反向遍历时用后一个元素的地址异或当前节点的

lr

又可得到前一个元素的地址。这样一来，便可以用一般的内存实现双向链表同样的功能。

链表

文章操作

实现

构建链表

单向链表

双向链表

向链表写入数据

单向链表

单向循环链表

双向循环链表

从链表中删除数据

单向（循环）链表 :

双向循环链表

技巧

异或链表

相关推荐

评论

链表