【灵魂 | 数据结构与算法】线性表（数组&链表）原理详解 + 实战代码

🤵‍♂️ 个人主页: @AI_magician 📡主页地址： 作者简介：CSDN内容合伙人，全栈领域优质创作者。 👨‍💻景愿：旨在于能和更多的热爱计算机的伙伴一起成长！！🐱‍🏍 🙋‍♂️声明：本人目前大学就读于大二，研究兴趣方向人工智能&硬件（虽然硬件还没开始玩，但一直很感兴趣！希望大佬带带）

该文章收录专栏 [✨— 《深入解析机器学习：从原理到应用的全面指南》 —✨]

@toc

数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。由于数组有连续的内存空间和相同类型的数据,内存访问机制 - 任意访问(随机访问)

有这么一种说法,之所以数组下标从0开始, 是因为在内存访问机制中可以减少一次减号运算 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式： a[k]_address = base_address + k * type_size

与之对应的也有两个问题,插入数据和删除数据,需要移动大量的内存,而实际中的动态数组需要划出大量的内存块迁移,会导致内存碎片问题,

在面对这个场景, JVM 标记清除垃圾回收算法的核心思想先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

此外还要警惕数据越界问题,很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。

数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。(也就是继续运行,你发现不了!!)

实际上,有很多容器已经被开发优化好,比如 Java 中的 ArrayList、C++ STL 中的vector。在项目开发中，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容(将空间自动扩容为 1.5 倍大小。)。不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

1.Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。

2.如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

链表

三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表, 双向循环链表。由于链表性质, 一般不会出现内存碎片问题.

我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。(当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。)

如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

代码要写好链表有以下几点：

1. 了解理解指针或引用的含义（地址调用）
2. 警惕指针丢失和内存泄漏：特别是在删除操作中，避免丢失和未释放资源
3. 利用哨兵机制简化链表代码

LCR 018. 验证回文串（链表、字符串，正则表达式）

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

• 1 <= s.length <= 2 * 105
• 字符串 s 由 ASCII 字符组成

这里通过re正则表达式进行筛选，其实有一个现成的内置函数 - isalnum()（检测字符串是否由字母和数字组成）

class Solution:
    def isPalindrome(self, s: str) -> bool:
        re_s = str.lower("".join(re.findall("[0-9a-zA-Z]+", s))) # match the parten
        lens = len(re_s) 
        for i in range(int(lens/2)):
            if re_s[i] != re_s[lens -1 - i]: 
                return False
        return True

该方法通过索引进行遍历判断，其实可以运用语言的反装语句，如果二者相同即可

class Solution:
    def isPalindrome(self, s: str) -> bool:
        re_s = str.lower("".join(re.findall("[0-9a-zA-Z]+", s)))
        return re_s == re_s[::-1]

在时间复杂度上需要扫描字符串为 O（n), 空间复杂度为O（n)

此外还有在字符串本身进行操作，使得空间复杂度为O（1）,主要是操作索引，可读性差一点，判断条件和操作较多，复杂度也比较大一点

class Solution:
    def isPalindrome(self, s: str) -> bool:
        lens = len(s)
        left, right = 0, lens - 1
        while (left < right): # stay cycle
            while left < right and not s[left].isalnum(): # judge
                left +=1
            while left < right and not s[right].isalnum():
                right -=1
            if s[left].lower() != s[right].lower() :
                return False
            left ,right = left +1,right-1
        return True

除此之外，其还可以联系链表的操作（反转链表，快慢链表步) ，以及联系栈（前一半入栈出栈和后半部分比较)