【编织时空四：探究顺序表与链表的数据之旅】

本章重点

• 链表的分类

• 带头双向循环链表接口实现

• 顺序表和链表的区别

• 缓存利用率参考存储体系结构 以及 局部原理性。

一、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环 

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

二、带头双向循环链表接口实现

1.申请结点：struct ListNode* BuyLTNode(LTDataType x)

动态申请结点，函数返回的是一个指针类型，用malloc开辟一个LTNode大小的空间，并用node指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把要存的数据x存到newnode指向的空间里面，把指针置为空。

// 申请结点
struct ListNode* BuyLTNode(LTDataType x)
{struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->prev = node;node->next = node;return node;
}

2.初始化：struct ListNode* LTInit()

// 初始化
void LTInit(struct ListNode* phead)
{phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;
}

我们首先看看这个初始化有什么问题嘛？

phead为空指针，说明我们的初始化没有效果，这是因为phead是函数里面的形参，出了作用域就销毁，plsit仍然是空指针，形参的改变不能影响实参，但是我们可以通过返回phead的地址解决问题。

单链表开始是没有节点的，可以定义一个指向空指针的结点指针，但是此链表不同，需要在初始化函数中创建个头结点，它不用存储有效数据。因为链表是循环的，在最开始需要让头结点的next和pre指向头结点自己。

因为其他函数也不需要用二级指针（因为头结点指针是不会变的，变的是next和pre，改变的是结构体，只需要用结构体针即可，也就是一级指针）为了保持一致此函数也不用二级指针，把返回类型设置为结构体指针类型。

// 初始化 - 改变实参plsit
struct ListNode* LTInit()
{struct ListNode* phead = BuyLTNode(-1);phead->prev = phead;phead->next = phead;return phead;
}

3.尾插：void LTPushBack(struct ListNode* phead, LTDataType x)

尾插首先要找到尾结点，再将要尾插的结点与尾结点和带头结点链接，由于是带头结点，所以此处不需要关注头结点为空的问题。

// 尾插
void LTPushBack(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* tail = phead->prev;struct ListNode* newnode = BuyLTNode(x);newnode->prev = tail;tail->next = newnode;newnode->next = phead;phead->prev = newnode;}

4.尾删：void LTPopBack(struct ListNode* phead)

尾删只需要找到尾结点的前驱结点，再把带头结点和前驱结点链接，释放尾结点就完成了尾删。

不过这里需要处理一下只有带头结点的删除，此时真正的链表为空，此时就不能删除了。

// 尾删
void LTPopBack(struct ListNode* phead)
{assert(phead);assert(phead->next != phead);//链表为空struct ListNode* tail = phead->prev;struct ListNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->next = tailPrev;}

5.头插：void LTPushFront(struct ListNode* phead, LTDataType x)

头插需要注意顺序，如果先让phead和newnode链接，那么就找不到phead结点的后续结点，这样就无法让newnode和phead结点的后续结点链接。

// 头插
void LTPushFront(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* newnode = BuyLTNode(x);//顺序不可颠倒newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

6.头删：void LTPopFront(struct ListNode* phead)

// 头删
void LTPopFront(struct ListNode* phead)
{assert(phead);assert(phead->next != phead);//链表为空struct ListNode* first = phead->next;struct ListNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}

7.链表长度：int LTSize(struct ListNode* phead)

        求链表长度，先把头结点下一个结点存到cur中，再用while循环遍历终止条件是cur等于头结点，用size++记录长度，并更新cur，最后返回size，32位机器下是无符号整型size_t。
（ 此类型可以提高代码的可移植性，有效性，可读性。此链表长度可能是字符型或者数组整型，他可以提供一种可移植方法来声明与系统中可寻址的内存区域一致的长度，而且被设计的足够大，能表示内存中任意对象的大小）

        注意这里求链表长度不需要求带头结点，我们有时也经常看到由于带头结点的数据没有使用，就有的书上会把该数据存储上链表的长度size=phead->data，然后插入数据phead->data++,删除phead->--，但是这有个限制，这种写法只适合int类型，如果我们写出char类型的数据，存储几个数据char就保存不了，char类型的phead->data一直++最后就会溢出，所以不建议这种写法。

// 链表长度
int LTSize(struct ListNode* phead)
{assert(phead);int size = 0;struct ListNode* cur = phead->next;while (cur != phead){size++;cur = cur->next;}return size;
}

8.在pos的前面进行插入：void LTInsert(struct ListNode* pos, LTDataType x)

断言pos，不能为空，插入数据先申请一结点放到定义的newnode指针变量中，为了不用考虑插入顺序，先把pos前面的存到posPrev中，然后就可以随意链接：
posPrev指向新节点，新节点前驱指针指向posPrev，新节点指向pos，pos前驱指针指向新节点。

// 在pos的前面进行插入
void LTInsert(struct ListNode* pos, LTDataType x)
{assert(pos);struct ListNode* posPrev = pos->prev;struct ListNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

9.删除pos位置的结点：void LTErase(struct ListNode* pos)

删除把pos位置之前的结点直接指向pos的下一个结点，把pos下一个结点的前驱指针指向pos之前的结点。

// 删除pos位置的结点
void LTErase(struct ListNode* pos)
{assert(pos);struct ListNode* posPrev = pos->prev;struct ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

 

10.双向链表查找：struct ListNode* ListFind(struct ListNode* phead, LTDataType x)

查找把头结点下一个结点存到cur，然后用while循环遍历，终止条件是cur等于头结点指针，如果cur等于x，直接返回cur指针，再更新cur，最后遍历完返回NULL，表示没有该数据。

// 双向链表查找
struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
{assert(phead);struct ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

11.销毁：void LTDestroy(struct ListNode* phead)

释放链表从头开始释放，把头结点下一个结点存到cur中，再用用while循环，终止条件是cur不等于头指针，在里面把cur下一个指针存到next中，释放掉cur，再把next更新为cur。最后头结点也是申请的，也得释放。

这里需要注意，由于形参的改变不会影响实参，我们在函数内部将phead置空是无意义的，我们需要在函数外面调用LTDestroy函数后，需要手动将phead置空。

// 销毁
void LTDestroy(struct ListNode* phead)
{assert(phead);struct ListNode* cur = phead->next;while (cur != phead){struct ListNode* next = cur->next;free(cur);cur = next;}free(phead);
}

12.打印：void LTPrint(struct ListNode* phead)

打印链表，先断言phead，它不能为空，再把头结点下个地址存到cur中，用while循环去遍历，终止条件是等于头指针停止，因为他是循环的，并更新cur。

// 打印
void LTPrint(struct ListNode* phead)
{assert(phead);printf("phead<=>");struct ListNode* cur = phead->next;while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}
}

三、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定 连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除 元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要 扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

四、缓存利用率参考存储体系结构 以及 局部原理性。

1.存储体系结构

1. 寄存器（Registers）：寄存器是CPU内部的最快速存储，用于存储最常用的数据和指令。它们在执行指令时起着重要作用，速度非常快。

2. 高速缓存（Cache）：高速缓存是位于中央处理器（CPU）和主存储器之间的一层快速存储，用于临时存放经常访问的数据和指令。它可以分为多个层次，如L1、L2和L3缓存，随着级别的升高，容量逐渐增大，但速度逐渐降低。

3. 主存储器（Main Memory）：也称为RAM（Random Access Memory），主存储器是计算机中用于存放运行中程序和数据的地方。它是CPU能够直接访问的存储设备，速度比较快，但容量通常相对有限。

4. 辅助存储器（Secondary Storage）：这包括各种长期存储设备，如硬盘驱动器、固态硬盘、光盘、磁带等。这些设备的容量通常很大，但速度较慢，用于持久性存储和备份。

5. 虚拟内存（Virtual Memory）：虚拟内存是一种在主存和辅助存储之间创建的抽象层，允许程序使用比主存更大的地址空间。操作系统可以根据需要将数据从主存移到辅助存储，以优化内存使用。

2.局部性原理

        存储体系结构的局部性原理是指在计算机程序执行过程中，访问内存的模式往往呈现出一定的规律性，即数据和指令的访问并不是完全随机的，而是倾向于集中在某些特定的内存区域或者特定的数据块上。这个原理分为两种类型：时间局部性和空间局部性。

1. 时间局部性（Temporal Locality）：时间局部性指的是一个被访问过的内存位置在未来的一段时间内很可能会再次被访问。这意味着程序在不久的将来可能会多次使用相同的数据或指令。时间局部性的实现依赖于高速缓存，因为缓存可以暂时存储最近使用过的数据，从而在未来的访问中加速存取。

2. 空间局部性（Spatial Locality）：空间局部性指的是在访问某个内存位置时，附近的内存位置也很可能会被访问。这种情况在程序中存在连续存储、数组访问等情况下特别明显。空间局部性的实现同样依赖于高速缓存，因为缓存可以在一个较小的区域内存储多个相邻的数据块。

        局部性原理对计算机性能具有重要意义。通过充分利用局部性，计算机系统可以更有效地使用高速缓存，减少主存访问次数，从而提高数据访问的速度和效率。这对于减少存储层次之间的数据传输时间以及提高程序的整体性能至关重要。

        举例来说，如果一个循环中多次使用相同的数组元素，由于时间局部性，这些数组元素会被缓存在高速缓存中，从而避免了多次访问主存。同样，如果一个算法中需要顺序访问数组的各个元素，由于空间局部性，缓存中可能会存储这些相邻的数据块，从而加速了后续的访问。

3.为什么顺序表的效率比链表效率高

1. 顺序表：顺序表是一种将元素顺序存储在一块连续的内存区域中的数据结构。由于顺序表的元素在内存中是相邻存储的，因此它充分利用了空间局部性。当访问一个元素时，由于它的相邻元素也在内存中，这些相邻元素很可能也会被加载到高速缓存中，从而减少了主存访问的次数。此外，由于顺序表的元素是连续存储的，通过数组索引可以直接计算出元素的地址，避免了链表节点的跳转操作。

2. 链表：链表是一种通过节点和指针连接元素的数据结构，它的元素在内存中不一定是连续存储的。在链表中，每个节点都包含了数据以及指向下一个节点的指针。这种非连续的存储方式可能导致空间局部性较差，因为在访问一个节点时，并不保证它的相邻节点会被加载到高速缓存中。这会导致更频繁的主存访问，从而降低了效率。

        综上所述，顺序表相比链表具有更好的空间局部性。它的元素连续存储，使得访问一个元素时，附近的元素也可能在缓存中，从而减少了主存访问的需求，提高了数据访问的速度和效率。而链表的节点之间不一定相邻存储，导致空间局部性不如顺序表，因此链表在访问数据时可能需要更多的主存访问操作，从而效率相对较低。

        需要注意的是，对于插入、删除等操作，链表在某些情况下可能更加灵活，因为它们不需要移动大量的数据，而顺序表在插入、删除操作时可能需要进行元素的移动，可能会带来一些开销。所以，在选择使用顺序表还是链表时，需要根据具体的应用场景和操作需求综合考虑。

本章结束啦！！！