单向链表操作
更新结点
如果不考虑查找结点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。
C
singly_linked_list_t *singly_linked_list_set(singly_linked_list_t *list, int index, T elem) {
if (list == NULL) {
return NULL;
}
if (index < 0 || index >= list->size) {
fprintf(stderr, "Error: index out of bound.\n");
return list;
}
node_t *node = list->head;
for (int i = 0; i < index; i++) {
node = node->next;
}
node->data = elem;
return list;
}插入结点
链表插入结点，分为 3 种情况：
-
尾部插入
把最后一个结点的
next指针指向新插入的结点。 -
中间插入
先把新结点的
next指针指向插入位置的结点，再将插入位置的前置结点的next指针指向新结点。 -
头部插入
先把新结点的
next指针指向原先的头结点，再把新结点设置为链表的头结点。
互动实验
单向链表插入
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
知识测验
题目
将新结点 X 插到单向链表的原头结点 A 前面，不额外保存旧 head。哪个指针更新顺序正确？
只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组考虑扩容的问题。如果不考虑插入之前的查找元素的过程，只考虑纯粹的插入操作，时间复杂度是 。
C
singly_linked_list_t *singly_linked_list_insert(singly_linked_list_t *list, int index, T elem) {
if (list == NULL) {
return NULL;
}
if (index < 0 || index > list->size) {
fprintf(stderr, "Error: index out of bound.\n");
return list;
}
node_t *node = singly_linked_list_node_create(elem);
if (index == 0) {
node->next = list->head;
list->head = node;
if (list->tail == NULL) {
list->tail = node;
}
} else {
node_t *prev = list->head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
node->next = prev->next;
prev->next = node;
if (node->next == NULL) {
list->tail = node;
}
}
list->size++;
return list;
}删除结点
链表的删除操作也分 3 种情况：
-
尾部删除
把倒数第二个结点的
next指针指向空。 -
中间删除
把要删除的结点的前置结点的
next指针，指向要删除结点的下一个结点。 -
头部删除
把链表的头结点设置为原先头结点的
next指针。
互动实验
单向链表删除
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
许多高级语言，如 Java，拥有自动化的垃圾回收机制，所以不用刻意去释放被删除的结点，只要没有外部引用指向它们，被删除的结点会被自动回收。
如果不考虑删除操作之前的查找的过程，只考虑纯粹的删除操作，时间复杂度是 。
C
T singly_linked_list_remove(singly_linked_list_t *list, int index) {
if (list == NULL || index < 0 || index >= list->size) {
exit(1);
}
node_t *node;
if (index == 0) {
node = list->head;
list->head = node->next;
if (list->tail == node) {
list->tail = NULL;
}
} else {
node_t *prev = list->head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
node = prev->next;
prev->next = node->next;
if (list->tail == node) {
list->tail = prev;
}
}
T elem = node->data;
free(node);
list->size--;
return elem;
}反转链表
反转一个链表需要调整链表中指针的方向。
递归反转法的实现思想是从链表的尾结点开始，依次向前遍历，遍历过程依次改变各结点的指向，即令其指向前一个结点。
而迭代反转法的实现思想非常直接，就是从当前链表的首结点开始，一直遍历至链表尾部，期间会逐个改变所遍历到的结点的指针域，令其指向前一个结点。
互动实验
反转单向链表
访问权限PRO
PRO EXCLUSIVE探索不止于此
尊享 Pro 权益解锁完整互动实验、进阶解析与精选参考答案。
C
static node_t *__singly_linked_list_reverse_recursive(node_t *node) {
if (node == NULL || node->next == NULL) {
return node;
}
node_t *new_head = __singly_linked_list_reverse_recursive(node->next);
node->next->next = node;
node->next = NULL;
return new_head;
}
singly_linked_list_t *singly_linked_list_reverse(singly_linked_list_t *list) {
node_t *prev = NULL;
node_t *current = list->head;
while (current != NULL) {
node_t *next = current->next;
current->next = prev;
prev = current;
current = next;
}
list->tail = list->head;
list->head = prev;
return list;
}