数据结构与算法--链表

2019-07-16 本文已影响0人 zhujunhua

数组和链接的内存分配情况：

数组/链表的内存分配

下面介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。

单链表

单链表
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。
其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

循环链表
当要处理的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题。

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针prev 指向前面的结点。

双向链表
Java中的LinkedHashMap就是使用了双向链表的数据结构。

时间复杂度

缓存淘汰策略，常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

对于指针的理解：
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

插入结点时，一定要注意操作的顺序；删除链表结点时，也一定要记得手动释放内存空间。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

带头链表