当前位置： 首页 >> 数据结构与算法 >> 数组与链表

---

数组与链表

2020-07-04 18:02:37 星期六  阅读：2366

---

####数组 数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。 线性表与非线性表的区别如下图。 线性表——数据排成一条线一样，每个线性表上的数据最多只有前后两个方向 非线性表——数据之间并不是简单地前后关系 ####数组的特点 - 随机访问 - - 随机访问就是根据下标访问，访问速度快；通过内存地址来访问；比如第一个元素的内存空间是1000-1003，则第N个元素的内存空间为1000 + n * 4，其中4表示每个元素的大小4字节。 为什么数组的下标从0开始？ 举个例子，如果数组的下标从1开始，则下标为3的内存地址为1000 + (3 -1) * 4 = 1008，但是如果数组的下标为从0开始，则下标为3的元素的内存地址为1000 + 3 * 4 = 1012，可以看出，从1开始的计算公式多了一个减法。当访问次数足够多时，这对很明显增加了CPU的计算负担。所以数组的下标都是从0开始 - 插入、删除数据非常低效； - - 当执行插入时，在插入点后的所有数据都需要挪位置； 当执行删除时，在删除元素后面的所有元素也需要向前挪位置； - 数组访问越界问题 - - 在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。 - 当可用连续内存小于数组需要的内存时，则数组会创建失败（因为数组是连续的内存块） #####容器能否代替数组 很多语言都提供了容器类，比如Java的ArrayList，Python中的list等。什么时候用数组、什么时候用容器呢？ - 如果特别关注性能，可选用数组； 如果数据大小已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组； 当要表示多维数组时，数组往往会更加直观。 在平时的业务开发中，可直接使用编程语言提供的容器类，如果是特别底层的开发，直接使用数组可能会更合适。 ####链表 链表的应用场景——LRU缓存淘汰算法。即：当缓存被占满时，哪些数据应该被清理出去。这就需要缓存淘汰策略来决定。 `链表并不需要连续的内存空间，通过指针将一组零散的内存块串联起来使用`。我们把内存块成为链表的结点，每个结点除了存储数据之外，还需要记录链表上下一个结点（对于双向链表，还需记录上一个结点）的内存地址。我们把这个记录下个结点地址的指针叫做后继指针。 **`链表的分类`** 2. 单链表 3. 双向链表 4. 循环链表（一种特殊的单链表） 5. 双向循环链表 #####链表的特点 插入效率比数组高（复杂度为O(1)，对于双向链表，删除给定指针指向的节点会比较高效。（因为删除某个结点之前需要先删除先驱结点和后驱结点的相应指针）。 因为在各个内存块（结点）上不仅要存储数据，还需要存储指针，因此相比数组，会浪费大量的内存空间。 #####数组与链表的对比 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。数组的缺点是大小固定，而链表没有大小的限制，天然支持动态扩容。 #####如何写好链表代码 如何写好链表代码并不是容易的事儿。比如链表反转，有序链表合并等。链表反转这几行代码写对的人不足10%。这里总结了几个写好链表代码的技巧； - 理解指针或引用的含义 - - 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 - 警惕指针丢失和内存泄漏 - 利用哨兵简化实现难度 - - 当向一个空链表中插入第一个节点，或者删除最后一个节点时，需要进行特殊处理。这个特殊处理会使得代码不简洁。所以引入哨兵节点，不管链表是不是空，head都会一直指向这个哨兵节点。对于有哨兵的链表，我们也叫做带头链表。 - 重点留意边界条件处理，主要检查一下几点： - - 如果链表为空，代码是否能正常工作； 如果链表只包含一个结点时，代码是否能正常工作； 如果链表只包含两个结点时，代码是否能正常工作； 代码逻辑在处理头结点和尾结点时，是否能正常工作。 - 举例画图，辅助思考 - 多写多练，没有捷径 写链表代码是最考验逻辑思维能力的，链表写的好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密，所以很多面试官喜欢让人手写链表代码。下面列出了5种常见的链表操作，这几个操作能写熟练，保证以后再也不会害怕写链表代码 ``` 单链表反转； 链表中环的检测； 两个有序的链表合并； 删除链表倒数第N个结点； 求链表中间的节点 ```