基础2丨链表

链表

一组任意的存储单元存储线性表存储元素,可以线性也不可不线性,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串。

单链表

我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 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

作者: 王药酒

药 酒 本 酒 | 备 考 事 业 编 中