[数据结构与算法]数据结构---链表

目录

一：概念及结构

1.1：概念

1.2：结构

1.2.1：单向或者双向

1.2.2：带头或者不带头

1.2.3：循环或者非循环?

1.2.4：无头单向非循环链表

1.2.5：无头双向链表

二：链表的实现

尾插法：

?头插法：

删除第一次出现关键字e的结点：

删除所有值为key的结点：??

?是否包含关键字e在单链表中：

?得到单链表的长度：

将链表中每个结点值域拼接成一个字符串返回：?

任意位置插入，第一个数据结点为0号下标：

一：概念及结构

1.1：概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

顺序表：底层是一段连续空间---物理上是连续的，逻辑上也是连续的。

链表：物理上不一定连续，逻辑连续。链表中的元素存储在一个一个的节点当中。

1.2：结构

1.2.1：单向或者双向

1.2.2：带头或者不带头

1.2.3：循环或者非循环

1.2.4：无头单向非循环链表

结构简单，一般不会单独用来存数据。

1.2.5：无头双向链表

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

二：链表的实现

尾插法：

情况一：链表如果为空，新结点插入后就是链表第一个结点

情况二：链表不空

?头插法：

情况一：如果链表为空，链表使用新结点

情况二：链表不空

删除第一次出现关键字e的结点：

删除所有值为key的结点：?

?是否包含关键字e在单链表中：

?得到单链表的长度：

将链表中每个结点值域拼接成一个字符串返回：?

任意位置插入，第一个数据结点为0号下标：

1. 检测测试是否合法
2. 找到index位置的结点，并保存其前一个
3. 插入新结点