【编织时空四：探究顺序表与链表的数据之旅】（上）：https://developer.aliyun.com/article/1424880
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.存储体系结构
- 寄存器（Registers）：寄存器是CPU内部的最快速存储，用于存储最常用的数据和指令。它们在执行指令时起着重要作用，速度非常快。
- 高速缓存（Cache）：高速缓存是位于中央处理器（CPU）和主存储器之间的一层快速存储，用于临时存放经常访问的数据和指令。它可以分为多个层次，如L1、L2和L3缓存，随着级别的升高，容量逐渐增大，但速度逐渐降低。
- 主存储器（Main Memory）：也称为RAM（Random Access Memory），主存储器是计算机中用于存放运行中程序和数据的地方。它是CPU能够直接访问的存储设备，速度比较快，但容量通常相对有限。
- 辅助存储器（Secondary Storage）：这包括各种长期存储设备，如硬盘驱动器、固态硬盘、光盘、磁带等。这些设备的容量通常很大，但速度较慢，用于持久性存储和备份。
- 虚拟内存（Virtual Memory）：虚拟内存是一种在主存和辅助存储之间创建的抽象层，允许程序使用比主存更大的地址空间。操作系统可以根据需要将数据从主存移到辅助存储，以优化内存使用。
2.局部性原理
存储体系结构的局部性原理是指在计算机程序执行过程中，访问内存的模式往往呈现出一定的规律性，即数据和指令的访问并不是完全随机的，而是倾向于集中在某些特定的内存区域或者特定的数据块上。这个原理分为两种类型：时间局部性和空间局部性。
时间局部性（Temporal Locality）：时间局部性指的是一个被访问过的内存位置在未来的一段时间内很可能会再次被访问。这意味着程序在不久的将来可能会多次使用相同的数据或指令。时间局部性的实现依赖于高速缓存，因为缓存可以暂时存储最近使用过的数据，从而在未来的访问中加速存取。
空间局部性（Spatial Locality）：空间局部性指的是在访问某个内存位置时，附近的内存位置也很可能会被访问。这种情况在程序中存在连续存储、数组访问等情况下特别明显。空间局部性的实现同样依赖于高速缓存，因为缓存可以在一个较小的区域内存储多个相邻的数据块。
局部性原理对计算机性能具有重要意义。通过充分利用局部性，计算机系统可以更有效地使用高速缓存，减少主存访问次数，从而提高数据访问的速度和效率。这对于减少存储层次之间的数据传输时间以及提高程序的整体性能至关重要。
举例来说，如果一个循环中多次使用相同的数组元素，由于时间局部性，这些数组元素会被缓存在高速缓存中，从而避免了多次访问主存。同样，如果一个算法中需要顺序访问数组的各个元素，由于空间局部性，缓存中可能会存储这些相邻的数据块，从而加速了后续的访问。
3.为什么顺序表的效率比链表效率高
顺序表：顺序表是一种将元素顺序存储在一块连续的内存区域中的数据结构。由于顺序表的元素在内存中是相邻存储的，因此它充分利用了空间局部性。当访问一个元素时，由于它的相邻元素也在内存中，这些相邻元素很可能也会被加载到高速缓存中，从而减少了主存访问的次数。此外，由于顺序表的元素是连续存储的，通过数组索引可以直接计算出元素的地址，避免了链表节点的跳转操作。
链表：链表是一种通过节点和指针连接元素的数据结构，它的元素在内存中不一定是连续存储的。在链表中，每个节点都包含了数据以及指向下一个节点的指针。这种非连续的存储方式可能导致空间局部性较差，因为在访问一个节点时，并不保证它的相邻节点会被加载到高速缓存中。这会导致更频繁的主存访问，从而降低了效率。
综上所述，顺序表相比链表具有更好的空间局部性。它的元素连续存储，使得访问一个元素时，附近的元素也可能在缓存中，从而减少了主存访问的需求，提高了数据访问的速度和效率。而链表的节点之间不一定相邻存储，导致空间局部性不如顺序表，因此链表在访问数据时可能需要更多的主存访问操作，从而效率相对较低。
需要注意的是，对于插入、删除等操作，链表在某些情况下可能更加灵活，因为它们不需要移动大量的数据，而顺序表在插入、删除操作时可能需要进行元素的移动，可能会带来一些开销。所以，在选择使用顺序表还是链表时，需要根据具体的应用场景和操作需求综合考虑。
