链表
一组任意的存储单元存储线性表存储元素,可以线性也不可不线性,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串。
单链表
我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。
随机访问O(n)
我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。
而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。
双向链表
循环链表
插入和删除O(1)
双向循环链表
总结:
链表适合插入和删除 不适合随机访问 和数组相比,链表更适合插入、删除操作频繁的场景,查询的时间复杂度较高。不过,在具体软件开发中,要对数组和链表的各种性能进行对比,综合来选择使用两者中的哪一个
链表代码的书写
- 要注意链表指针丢失和内存泄漏
x->next=p->next
p->next=x
利用哨兵简化实现难度
new_node->next = p->next;
p->next = new_node;
然后有两种情况
1、空头,也就是第一个头结点是空的 可以存储数据的
但是,当我们要向一个空链表中插入第一个结点,刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理,其中 head 表示链表的头结点。所以,从这段代码,我们可以发现,对于单链表的插入操作,第一个结点和其他结点的插入逻辑是不一样的。 if (head == null) { head = new_node; }
2、非空头
删除
if (head->next == null) {
head = null;
}
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
代码:https://github.com/saber/algorithm/blob/master/src/list/single_list.hpp