004.线性表9-17

@author: 小甲鱼

4.线性表的链式存储结构

1.特点：

1.用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。
2.除了存储数据元素信息外，还要存储它的后记元素的存放地址(指针)。

数据域是：存储数据元素信息的域。
指针域是：存储直接后继位置的域。
指针或者链是：指针域中存储的信息。
结点是：这2部分信息组成数据元素称为存储映像/节点(Node)。

n个结点链接成一个链表，即为线性表(a1, a2, a3, ..., an)的链式存储结构。

2.单链表

此链表的每一个结点中只包含一个指针域，叫做单链表。
特点：
1.空间大小不需要指定，就像租房一样，可以随时更换。
2.数据存储结构是随机的，哪里有空间，哪里就可以存放数据。

我们把第一个结点的存储位置叫做：头指针，最后一个结点指针为空(NULL 或者 ^ )

读取方式：
1. 从头结点开始找，直到接到为止
2. 时间复杂度： O(n)
插入方式：

1.改变指向的地址
2.时间复杂度： O(1)

头指针和头结点的异同:

• 头指针:

  • 1.头指针是指链表指向第一个结点的指针；若链表有头结点，而是指向头结点的指针。
  • 2.头指针具有标识作用，所以常用头指针冠以链表的名字(指针变量的名字)
  • 3.无论链表是否为空，头指针均不为空。
  • 4.头指针是链表的必要元素。

• 头结点:

  • 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(当也可以用来存放链表的长度)。
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点起操作域其它结点的操作就统一了。
  • 头结点不一定是链表的必需要素。




插入方式：
1.头插法

2.尾插法


3.静态链表

概念：用数组描述的链表叫做静态链表。这种描述方法叫游标实现法。
目的：为了给没有指针的编程语言设计一种单链表的实现方式。

1.原理分析

链表空间的.首元素存放的是：链表元素空间为空，下标最小的元素.
链表空间的.尾元素存放的是：游标指向链表元素的首元素.
链表元素的.首元素存放的是：结束下标的下一个.
链表元素的.尾元素存放的是：0，表示结束。

1.插入元素：
插入B，我们要找到A和C的位置，然后将A的游标指向B，然后将B的游标指向C.




1.删除元素：
删除C，我们只是数据清空，然后把指向指向C元素的下标。
而链表空间首位置0的下标直线，C的下标。





4.腾讯面试题：

普通方法：

快慢指针：
2个指针AB同时指向，A个指针是B指针的2倍。
当A指针刚好到终点的时候，B指针刚好到的中间位置。


5.循环链表

就是将单链表的终端结点的指针 指向 头结点，使其头尾相接，我们称为：单循环链表，简称循环链表。



判断循环一次是否完毕：
单链表是：head->next是否为null。
循环链表：head->next是否为head。





终止条件： A-B-A，那么就该结束叻。

循环链表的首位结点，时间复杂度都是： O(1)



6.判断单链表中是否有环



方法1: 从0开始

AB二人，A每走一步，B都得从0开始走；
当A走了7步，回到了3；而B从0开始走，发现只走了3步；
所以：AB步数不想等，出现矛盾，存在环。

方法2: 快慢指针

AB二人， A走1步，B走2步，如果有环，那么迟早要相撞。

7.双向链表


双向链表的结点结构：

双向链表的插入操作：

双向链表的删除操作：

双向链表的循环链表：