链表的基本操作

发表于 更新于 分类于 阅读次数：
链表的基本操作 C/C++实现

单链表

插入

将q节点插入到p后面

1
2
3
4
void InsertNode(LinkedList *p, LinkedList *q) {
    q -> next = p -> next;
    p -> next = q;
}

如果是将节点插入在表头呢，分两种情况

    1. 含有头节点的单链表

此时和上面类似，一共两步

1
2
s -> next = head -> next;
head -> next = s;
    1. 不含头节点的单链表
1
2
s -> next = head;
head = s;

删除

删除q节点

1
2
3
4
void DeleteNode(LinkedList *p,LinkedList *q) {
    p -> next = q -> next;
    free(q);
}

同样的，删除第一个节点时，有无头节点的单链表在删除时的操作也不一样

有头节点时

1
2
head -> next = head -> next -> next;
free(node);

无头节点

1
2
head = head -> next;
free(node);

双链表

插入

1
2
3
4
s -> next = p -> next;
p -> next = s;
s -> prior = p;
s -> next -> prior = s;

删除

1
2
3
4
5
6
7
p -> next = s -> next; 
p -> next -> prior = p;
free(s);
// 若不使用p指针
s -> prior -> next = s -> next;
s -> next -> prior = s -> prior;
free(s);