温故：线性表 - leobert's blog

温故：线性表|数据结构

对数据结构 - 线性表 进行温故，以期获新知

温故系列是我尝试的一种新学习总结方式，在 阅历增长时，总结旧闻，以 期获 新知，并不断迭代。了解更多

本次温故时间：2021年3月

注：部分图片来自网络检索，未找到出处，内容仅供学习，如有侵权，可留言联系 要求删除 或者 要求指明出处

基本概念

线性表 ，全名为 线性存储结构，是一种 有序数据项 的 集合，其中每个数据项都有 唯一 的 前驱 和 后继， 注意：第一个没有前驱，最后一个没有后继。

新数据项加入到数据集中时，只会加入到原有某个数据项 之前 或者 之后

table1

从上图我们可以理解，线性表是将数据项串起来 之后 存入物理空间 的一种数据结构。

table1

不同的存储方式，衍生出两种实现方式：

将数据 依次存储 在 连续的整块 物理空间中，是 顺序存储结构 又称 顺序表；
将数据 分散存储 在物理空间中，并能够存储数据项之间的 前、后驱 关系，是 链式存储结构 ，又称 链表；

顺序表

其性质可以直接对应到 数组，具有随机读写能力，使用需要先初始化，获取 整块的存储空间，如果使用中需要扩容，则需要先分配一块新的存储空间，并进行内容复制。

链表

普通链表又称单链表，用于存储逻辑关系为 "一对一" 的数据。

与顺序表不同，链表不限制数据的物理存储状态，即数据项的物理存储位置是随机的。

每个 节点 对应一个数据项，包含了两部分信息：

数据元素本身，其所在的区域称为 数据域；
指向 直接后继元素 的指针，所在的区域称为 指针域；

头指针 ：一个普通的指针，它的特点是永远指向链表第一个节点的位置。

头节点 ：一个 不存任何数据 的空节点。不是必须的，但可以解决一些实际问题：

链表数据变动时，需要维护 链表的引用地址 即 头指针 的问题
遍历时，不需要对第一个节点进行特殊处理

首元节点 ：链表中第一个存有数据的节点为首元节点。

静态链表

比较早期的时候，并不能像C语言那样灵活的操作指针，于是用 数组代替指针 来描述单链表。这种用数组描述的链表叫做静态链表，这种描述方法叫做 游标实现法。

算法题小练手

206.反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）

迭代思路：遍历整个链表，将每个节点的next指向前驱，返回链表的尾端节点即可。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    ListNode tmp = null;
    while (curr != null) {
        tmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

递归思路： 递：将结点的 后继 作为新的链表头节点，调用reverseList，直到进行到原始链表的尾端时，即 node.next 为 null 时。此时开始归，返回新链表头节点

归：归的过程中，反转链表的方向，设原先有 a.next = b, 现在需要转变为 b.next = a, 即 a.next.next = a,

边界问题：

因为是在归中处理，所以相当于是从 原链表尾端 开始处理反转，开始位置不用担心
结束位置需要注意，必须将其的 next 改为 null，即 a.next = null

我们再用数学归纳法复盘一下：令长度为l （L的小写，部分字体下看起来像数字1，特此说明），原链表头结点为head

当l=0时，直接返回null，head也是null
当l=1时，直接返回head
当l=2时：
- 取head的next，作为新链表先进入处理，返回结果即newHead，新链表长度l=1，直接返回了,确实是期望的反转链表的头节点
- 反转两者(即 head 与 head.next)前后驱关系，head.next.next = head，处理head的next 为 null
- 返回newHead
当l=3时：
- 取head的next，作为新链表先进入处理，返回的newHead 是期望的 反转链表的头结点
- 处理head 与 head.next 的前后驱关系，head.next.next = head，处理head的next 为 null
- 返回newHead

......

当l=n，n>3时：
- 取head的next，作为新链表先进入处理，返回的newHead 是期望的 反转链表的头结点
- 处理head 与 head.next 的前后驱关系，head.next.next = head，处理head的next 为 null
- 返回newHead
当l=n+1,n>3时：
- 取head的next，作为新链表先进入处理，返回的newHead 是期望的 反转链表的头结点
- 处理head 与 head.next 的前后驱关系，head.next.next = head，处理head的next 为 null
- 返回newHead

我们依据数学归纳法，得出：l=0或l=1时，返回head，l >= 2时，处理方式一致，不再誊写

public ListNode reverseList(ListNode head) {
    //l=0时，head为null；l=1时，head.next 为null。 均直接返回head，归的特殊处理
    if (head == null || head.next == null) {
        return head;
    }
    //递
    ListNode newHead = reverseList(head.next);
    
    //归的处理
    //反转 head 与 head.next 的前后驱关系
    head.next.next = head;
    head.next = null;
    
    //返回newHead
    return newHead;
}

温故总结

作为比较基础的内容，在更复杂的数据结构中，线性表可能会作为底层实现。在实际应用中，我们用到 单链表 的地方不会太多。

在算法练手环节中，突然发现一个 很趁手 的东西，以为考虑 递归实现 思路时，我总是要非常仔细的思考边界问题。

但这次突然发现，若能够 被递归实现，一定可以用 数学归纳法 论证 做法的正确性，推导过程可以 完善地 讨论边界问题。并且其推导过程非常 人性化。

这篇内容很短，就到此结束了。