数据结构：单向链表的基本操作

• 访问元素方便，时间复杂度为 O(1)
• 插入和删除不方便

2. 链式结构

把数据元素存放在任意的存储单元里，这组存储单元可以说连续的，也可以是不连续的。 2) 特性：

• 访问元素不便，需要遍历，时间复杂度为 O(n)
• 插入和删除数据方便

3. 索引结构

根据地址就可以找到对应的关键字。可以理解成一个黄页，你根据一个人的名字，就可以找到他的电话。所以索引存储又被称为直接寻址。数组就是一个常见的索引存储结构，可以通过下标来直接访问。索引表是有序的。

4. 散列结构（哈希结构）

'散列存储'名字中的'散列'就是常听到的 hash（哈希值），hash 是通过一种算法来运算出来的，比如 MD5。在这种存储格式下，地址会通过 hash 算法来运算成一个相同长度的 hash 值，然后存放这个 hash 值，而不是直接存放地址。在访问关键字的时候会通过运算解码 hash 值，然后再访问。

算法

算法是解决问题的步骤，不同的数据结构决定了所对应的算法不同。

1. 特性

输入、输出、有穷性、确定性、可行性。

2. 设计

准正确性、健壮性、可读性、时间和空间效率。

3. 算法好坏的度量——算法效率

时间复杂度、空间复杂度。

线性表

零个或多个数据元素的有限序列。

1. 顺序表

以顺序结构存储的线性表。

2. 链表

1. 定义：以链式结构存储的线性表。
2. 特性：

• 一个节点分为数据域和指针域，数据域存放当前节点的数据部分，指针域存放链表的下一个节点（后继位置）的地址。
• 链表的第一个节点的存储位置叫做头指针，第一个节点叫头节点。线性链表的最后一个节点指针为 NULL。头节点的后一个节点是首节点，头节点的数据域可以不存储任何信息，一般对链表的操作是从首节点开始，但是删除链表的尾删方式是从头节点开始的。
• 头指针和头节点的异同

链表的基本操作

编写程序时要充分考虑空链表、只有一个有效节点、用户输入数据为 NULL 等特殊情况的排查。在判断条件中要考虑到逻辑与的短路特性，基本操作的前提都是在链表内完成的。

1. 创建链表

指针域的定义如下所示。

2. 增加节点

1) 头插

从头部插入，先插入的后输出。例如头插：1, 2, 3, 4；打印输出是：4, 3, 2, 1。

• Step 1: 创建一个新节点并给值。
• Step 2: 让新节点指向原首节点：将原首节点的地址存在新节点的指针域。
• Step 3: 让头节点指向新节点：将新节点的地址存放在头节点指针域中。 Step 2 和 Step 3 的顺序不可以变，如果 Step 3 先操作，头节点的指针域信息会被覆盖，首节点的地址会丢失。

2) 尾插

从尾部插入，先插入的先输出。例如尾插：1, 2, 3, 4；打印输出是：1, 2, 3, 4。

• Step 1: 创建一个新节点并给值，将新节点的指针域初始化为 NULL。
• Step 2: 找到尾节点。
• Step 3: 链接链表：将新节点的地址存放到当前尾节点的指针域，链接成功后，新节点是新的尾节点。 p_new->pnext = NULL; 必须写，因为此时插入的节点是尾节点，尾节点指针域必须为空。

3. 删除节点

1) 头删

• Step 1: 定义一个指针变量指向首节点。
• Step 2: 链接节点：让头节点指向即将删除的节点的下一个节点：将首节点的下一个节点地址装入头的指针域。
• Step 3: 释放 p 所在的空间。 链表只有一个节点时也适用。

2) 尾删

• Step 1: 找到尾节点的前一个节点，由于边界条件的判断需要两次 next，指针 p 必须从头节点（phead）开始遍历，而不是从首节点（phead->pnext）开始，主要是为了安全处理链表只有一个有效节点的边界情况。当头节点作为起始点时，当链表仅有一个节点时，p->pnext->pnext 直接为 NULL，循环不会执行，可直接释放尾节点并更新头节点的指针；若从首节点开始，此时 p 即为尾节点，p->pnext 为 NULL，访问 p->pnext->pnext 会导致对空指针解引用，引发段错误。因此，从头节点出发能统一处理各种节点数量情况，避免非法内存访问。
• Step 2: 释放尾节点。
• Step 3: 将尾节点的前一个节点指针域设为 NULL。

4. 修改节点

• Step 1: 从头节点开始比较，找到指定值所在的节点。while((p != NULL) && (p->data != old)) 这里的条件不能调换顺序，因为如果调换为 (p->data != old) && (p != NULL)，当 p 为 NULL 时，会先访问 p->data 导致段错误。目前的顺序是正确的，利用了逻辑与的短路特性。
• Step 2: 将指定节点的值修改为指定值。 以下 if 条件语句中 && (p->data == old) 这个判断是多余的。因为循环结束的条件只有两种可能：
• p == NULL（遍历完链表没找到）
• p->data == old（找到了） 所以只要 p != NULL，就一定是找到了目标节点。

5. 查找节点

• Step 1: 从头节点开始遍历查找指定值所在的节点。
• Step 2: 找到指定节点后返回节点地址，若链表为空或遍历结束未找到则返回 NULL。while 的条件语句也不可以调换顺序，因为逻辑与的短路特性存在，指定值和节点数据域相等的前提应该是在链表内。

6. 补充

1. 判断链表是否为空 在非空链表中，判断链表是否只有一个有效节点是：phead->pnext->pnext == NULL；

2. 遍历打印链表数据域

3. 计算链表长度