作为数据结构的基础，线性表有2种类型，一个是数组，另外一个是链表。 大家也都知道他们的基本知识，比如 数组在内存中是一块连续的内存地址，而链表在内存中是不连续的，是靠每一个节点来记录相邻结点位置关系。
相信大家也都知道他们的基础知识，比如 数组因为是一块连续的空间，所以需要找出数组中任何位置元素的值，根据 首地址 和每个元素占用的空间，一计算，我们就能好找到 目标元素的地址，从而找到这个地址保存的值，复杂度为O（1）。 但是通常情况下，删除 和插入就需要将数组的元素 全部都移动一次。
而链表因为在内存中存储的位置 不需要连续，所以插入 和删除操作时 只需要更改目标位置 前后结点的指针指向即可，所以复杂度为O(1), 但是当需要进行查找操作，只能从到到尾开始遍历，所以复杂度就是O(n)。
作为数据的基本类型，很多语言都需要包含 int, string等数据类型，但同时为了支持 更多的特性，编程语言还支持数组，字典等数据类型。 但是你有没有思考过一个问题，为什么很多语言只有 数组，但是一般链表都需要自己实现呢？
首先说明一点的是，即使目前的编程语言没有原生支持链表，但是并不能说明 链表并没有什么价值，我们就不需要学习它了。下面简单罗列 链表的应用场景，
1、文件系统：
通常当你格式化硬盘时会让你选择fat32、ntfs格式，其实就是让你选择存储链表空间规模及格式。为提高系统效率，你有时需要做文件碎片整理，这说明一个文件的数据不一定是连续存放的，那么操作系统是如何知道把不连续的数据合成一个文件提供给你的呢？其实就是通过访问一个指向文件数据区的链表得到的。
2、LRU缓存
可以通过HashMap+双向链表实现。HashMap保证通过key访问数据的时间为O(1)，双向链表则按照访问时间的顺序依次穿过每个数据。
3、git
git里面每次commit都是创建一个node，node包含了删减后的新文件，然后node指向前一个commit的node。git checkout、delete branch、merge、rebase这些基本上都是以链表操作为主。git应该算是对linked list很好的应用。不用linked list应该很难高效地实现git提供的功能。
发现没有，其实链表的应用场景挺多的，实际上内存池、操作系统的进程管理、网络通信协议栈的trunk管理等都用到了链表的思想。
所以现在回答标题的问题：
编程语言作为一个工具，开发出来的程序 对于计算机来说，只会是一部分，集中管理，因为在同一个内存块，方便查询等操作，同时因为数组的连续性。每次cpu缓存 也会把相邻的数据加入缓存。增加其效率。
链表的数据 相对松散，通常将其应用于一个具体项目，或者应用到主体，比如git, 文件系统。
网友评论