性能优化-数组和链表，队列和栈

数组

数组的内存是连续的，不同的语言有着不同的分配内存规则。有的需要开始的时候指定长度，有的不需要（当数组的长度不够的时候会分配一个新的更长的内存，然后把原来的数据复制过来，这个操作很费时），访问数组中第n个数据的时间花费是O(1)，但是要在数组中查找一个指定的数据则是O(N)。

数组内存示意图

当向数组中插入或者删除数据的时候，最好的情况是在数组的末尾进行操作，时间复杂度是O(1)，但是最坏情况是插入或者删除第一个数据，时间复杂度是O(N)。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是O(N)。

数组插入删除示意图

链表

链表的内存不是连续的。通过指针将各个内存单元链接在一起，不是环形的链表会有一个或者二个节点的指针指向NULL（单项一个，双向两个）。链表不需要提前指定长度，也不会出现长度不够的问题，当需要存储数据的时候分配一块内存并将这块内存插入链表中。

单向链表示意图 双向链表示意图 环形的链表

在链表中查找第n个数据以及查找指定的数据的时间复杂度是O(N)，但是插入和删除数据的时间复杂度是O(1)，因为只需要调整指针就可以（插入的时候你需要知道插入的数据的前一个数据或者后一个数据，所以双向的更灵活，但是单向和双向都不能向一个方向遍历出所有的数据，所以环形链表诞生了）

链表删除 链表插入

队列

这个数据结构是先进先出的，就像排队买东西一样，先来的先买，数组或者是链表都能实现它，队列只允许在队尾添加数据，在队头删除数据。但是可以查看队头和队尾的数据。还有一种是双端队列，在两端都可以插入和删除

双端队列 队列

栈

这个数据结构是先进后出的，先放进去的数据会被后放进去的数据压到下面，数组或者是链表都能实现它，栈中的数据的所有操作都是在栈的顶部完成的，只可以查看栈顶部的数据，只能够向栈的顶部压入数据，也只能从栈的顶部弹出数据。

栈

点击这里可以看到作者的其他文章

欢迎转载，转载请标明出处