小甲鱼数据结构学习笔记——线性表（链式存储结构）

线性表链式存储结构定义

• 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。
• 链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）
• 把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，也称为结点（Node）
• n个结点链接成为一个链表，即为线性表（a1，a2，a3…an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
  

单链表

• 链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空（NULL）
• 头指针
  • 头结点的数据域一般不存储任何信息
  • 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
  • 头指针具有标识作用，所以常用头指针冠以链表的名字
  • 无论链表是否为空，头指针均不为空。
  • 头指针是链表的必要元素
• 头结点
  • 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（但也可以用来存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了。
  • 头结点不一定是链表的必须要素
    

单链表的读取

• 由于单链表的结构中没有定义表长，所以不能实现知道要循环多少次，因此也就不方便使用for来控制循环。
• 时间复杂度为O（n）。

单链表的插入

单链表的删除

• 对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

头插法建立单链表

头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，知道结束为止。简单来说就是把新加进的元素放在表头后的第一个位置。

尾插法建立单链表

头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。

单链表的整表删除

算法思路：

• 声明结点p和q；
• 将第一个结点赋值给p，下一个结点赋值给q；
• 循环执行释放p和将q赋值给p的操作。
  

单链表结构和顺序存储结构的优缺点

• 存储分配方式：
  • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
  • 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
• 时间性能：
  • 查找
    • 顺序存储结构O（1）
    • 单链表O（n）
  • 插入和删除
    • 顺序存储结构需要平均移动表长一半的元素，时间为O（n）
    • 单链表在计算出某位置的指针后，插入和删除时间仅为O（1）
• 空间性能：
  • 顺序存储结构需要预分配存储空间，分大了容易造成空间浪费，分小了容易发生数据溢出。
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
    结论：
• 若线性表需要频繁的查找，很少进行插入或删除操作，宜采用顺序存储结构
• 若需要频繁的插入或删除，则宜采用单链表结构
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不用考虑存储空间的问题

顺序结构和单链表结构各种操作的动画演示在视频的10：10处动画演示
本博客是用于自己学习小甲鱼数据结构的学习总结
B站地址为小甲鱼数据结构学习