这个文章算是第一篇具有博客性质的文章（我估计），一方面是想写一点我对于这两种数据结构的一些思考，以及与我学习生活的关联；另一方面是锻炼文字能力，只有真的一个字一个字敲键盘才发现自己有时候连一个通顺的句子都写不出来。这俩数据结构虽然是看起来很简单的东西，但是我从接触编程到现在发觉这俩东西蕴含的能量其实很大。
能把这俩放在一起比较的，目前我能想到的就是数据结构考试中会出现，或者实习面试可能会出现，不过都是作为简单的东西出现。事实上的确原理都很简单，但是谈到应用就很夯了。
我在大一上入门编程的时候学习的是Python，最基础的数据结构就是列表了，而且当时学的时候很开心，因为啥都能往里面放，比如整数、浮点数、字符串，甚至是列表、集合等等。做简单算法题也很舒服，输入的东西一般想都不用想就直接往列表里面装，想用谁或者修改就直接用索引取出来就行了，真的是方便的不得了。除了取值，还可以在常数时间内在末尾append值。【注：python列表存的是引用，底层有开销。】
在大一下学习了链表，真的是不比不知道一比吓一跳，真的是麻烦死了（我个人感觉是这样的）。一方面想写个链表要专门搞个类来写，另一方面访问或者修改某个节点都要从头遍历一遍。不过，有个好处是一个节点可以装很多的东西，比如装一个整数一个字符串，只需要保证有一个连接着后续节点的指针即可。
此外，做有关链表的算法题也是很烧脑，最恶心的就是无法随机存取，在写题的时候需要动脑子想怎么遍历才不会出错，才能找到想要的那个值。比如反转链表之类的。
这个时候我就已经发现数组和链表有一些很显然的区别点了：
- 数组可以随机存取，对于访问值是O(1)复杂度的，十分方便；而链表只能顺序访问，要访问某个结点是需要O(n)复杂度的。
- 做简单算法题能用数组就用数组，尽量别碰链表。
- 数组保存的东西往往是比较固定的或者已知大小的；而链表保存的东西是可以自定义的，只需要保证有一个后续节点指针来作链接即可。
不过，链表并不只是只能用来做线性的存储方式，每个节点从原先的存一个后续节点指针改为存多个节点指针，便成了树。那有关树的问题往往是数组不好解决的了，比如二叉树、红黑树之类，在实际应用中各种树结构以其独特的优点得以大放光彩，比如查找效率和插入效率极高的红黑树。那这种情况下数组显然是没法碰瓷的。
在大二上，我学习了ICS课程，算是第一次正式接触到C语言和其比较底层的东西。说实话我第一次看到C语言的时候，有一种很奇怪的感觉，就是为啥每个变量都要在名字前面加上类型啊？你看人家Python多方便，直接写名字就行了。我当时还因为这个东西和一个朋友吵了半天，他当时说的是那是因为你没有遇到过大工程，写Python不带类型你到用的时候都不知道你引用的东西到底是个字符串还是个整数。我那时还不知道Python也可以在变量名处写类型名（比如def f(num: int) -> int），还相当不服气他说的话，坚持觉得C语言这样写类型很繁琐且不好看。除此之外还有为啥数组只能放一种数据类型啊？这样哪有python方便呢？【注：C语言会在运行时强制类型检查，python中的类型注解只是给人看的提示，即使在上面例子中num传入一个字符串也不会报错】
在ICS课程中首先就介绍了计算机的内存是一个大的数组，每个位置存一个字节的数据。接着又学了C语言中各个类型的大小，比如一般来说short是2字节，int是4字节等等。还学了大端序和小端序，即在内存中字节之间存放的顺序。
我在某天突然又想到了我在之前和朋友争吵的那个问题，比如在C语言中我定义了一个数组int array[3]，然后写int a = array[1]，这个变量a前面的int真的是有必要写的吗？我假如写成short a可以吗？
事实上是可以的，而这也是为什么需要添加类型的原因。首先，数组中的数据是顺序存储的，在上面的例子中3个int是连续放着的，4字节4字节挨着的。接着，array[1]其实只是一个指针解引用后的值，相当于是*(array + 1)，这里由于array存的是以4字节为单位的数据，加1就是加4个字节，所以这个指针实际上指向的是第二个int的起始地址。最后，正是由于这个a前面写的是int，才会从这个地址处读取int的4个字节的数据，并把字节顺序颠倒（由于是小端序）得到最终a的结果。假设a的类型写成short，那无所谓呀，直接从刚刚这个地址处读取2个字节的数据颠倒给a即可。然而这显然是没有意义的（一般来说）。虽然我感觉这个东西对于其他人来说是很小儿科的，但是确实是困惑了我很久，并在学习到这里的时候才发现是底层存储所安排好的。
这里我其实是搞懂了一个事实，也就是类型会影响读取长度。但是，这并不是解释为什么C语言需要在变量前写类型的原因。后来，学到了汇编语言，这才发现，C代码的类型是会影响汇编代码的，在生成每条机器码之前，编译器是需要知道每个操作数的大小和操作类型的，以及需要知道内存布局应该是如何做的。也就是说写类型是C语言设计所决定的。
有关C语言设计决定的还有在编译期间确定内存布局，这一点在学习struct和union结构的时候感受最深，当时是第一次知晓struct的内容在内存布局原来是如此规矩成方圆，这里就不多赘述具体原则了。
再后来，在ICS中第一次碰到需要用到链表的应该是虚拟内存管理的部分，在管理空闲内存的时候用到了链表来把一个个空闲的内存块串起来，加上各种分配算法实现高效的动态内存分配。
我记得最深刻的就是在描述隐式空闲链表的部分，对于节点的设计是如此之精妙。还记得前面说的树的结构吗？在那个时候，我傻傻地认为链表的每个节点顶多就存个后续几个指针，再存个数据，就已经对其利用很足了；没想到在这里能对其进一步“压榨”。对于一个节点，当前节点指针指的是这个节点本身的数据的起始地址；然而，这个节点的起始地址却在节点指针之前–在数据起始地址之前，还存着一个4字节（或8字节）的合并了的数据，即当前节点的大小 和 当前节点是否是空闲状态 的 或运算 的 结果，具体可以看一下上图，真的是精妙至极，算是把位运算玩的炉火纯青了（为什么能这样合并？因为每一个块的大小都是8字节的倍数，保证了起始地址是按照8字节对齐的，也就意味着其低3位都是0。在取节点大小的时候把低3位置0即可）。此外还有节点末尾的信息，和头部一致来保证能够遍历链表。
这里我们整理一下思绪，原本的链表都是保证存一个后续指针，可能会存有数据；这里的链表并没有显式地存后续指针，而是选择了存当前节点的大小，从而利用指针地址运算（加上节点大小）即可得到前后节点的指针。至于为什么能这样做？那当然得益于内存大数组的连续性了啊！毕竟，这里管理的是空闲内存块，它们是连续的，当然可以用地址运算来获取前后块了啊！所以，在这个应用中，数组是地基，链表是地基上面的一个个楼房，由于地基的连续性保证了楼房也在紧紧挨着，方便了相邻楼房之间的互访。此时二者已不再是割裂的数据结构了，而是互利互惠的关系了。
除了这里有利用到链表，还有在编写一个小型proxy时，对于来自server的内容进行LRU缓存时也有用到。具体地，维护一个双向链表，头部表示最近使用的内容和URL，尾部表示最远使用的内容和URL。每次URL访问都会将其对应的节点移到链表的开头，若整个链表满了，只需要把末尾的节点抛弃即可。尽管在实现上颇有做双向链表算法题时候的烧脑感，但是原理还是易懂的。
这里还想再谈谈数组没法碰瓷的链表应用：红黑树。就仅仅拿Linux来说，光是一个红黑树就被用在了好几个部分，这里引用来自Linux Weekly News的一段话：
There are a number of red-black trees in use in the kernel. The deadline and CFQ I/O schedulers employ rbtrees to track requests; the packet CD/DVD driver does the same. The high-resolution timer code uses an rbtree to organize outstanding timer requests. The ext3 filesystem tracks directory entries in a red-black tree. Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the “hierarchical token bucket” scheduler.
比如在调度模块中有CFS调度算法利用红黑树来管理可运行进程，在虚拟内存管理模块中的vm_area_struct有红黑树节点来管理虚拟地址空间区域，在高性能网络服务中的epoll机制中有红黑树来管理连接文件描述符和其数据……这足以看出红黑树的威力了吧！此外，还记得上面提到的链表节点的写法吗？要存后续指针和当前节点的数据内容。然而在Linux中却采用了另一种天才般的方式：把红黑树的节点反向保存在数据内容结构体当中，然后对于节点本身依然维护着一颗红黑树。也就是说，从原先的数据保存在节点里，变成了节点保存在数据里了。有关红黑树在Linux中具体的实现这里也不在赘述，可参考：
Linux虚拟内存系统与红黑树的应用浅析