Data Structures in C++：栈和队列的链表实现

数组和链表的区别：
数组因为内存连续，随机访问性强，可通过下标进行快速定位，查找速度快；但在插入和删除效率低，都需要移动数据，对内存空间要求高，必须有足够的连续内存空间。

链表相比数组操作更加灵活，尤其在插入和删除上，不需要额外的数据移动，效率更高只需要改变指针的指向，不需要连续内存，利用率更高；但不能随机查找，必须从第一个元素开始遍历，查找效率低。

单链表和双链表的区别：

• 单链表只有一个指向下一结点的指针next，只能单向读取。
• 双链表除了next外，还有一个指向前一结点的指针prev，可以快速找到前一结点，因此查找和删除的效率更高；但链接域占用了更多的额外内存。

双链表为什么查找和删除的效率更高？

1. 删除结点时，单链表一定要得到待删除结点的前驱。一种方法是在定位待删除结点的同时一路保存当前结点的前驱；另一种方法是在定位到待删除结点之后，从单链表表头开始重新定位前驱。尽管通常会采用方法一，但它们的效率是一样的，指针总共需要移动 $2i$2i 次。而双向链表不需要定位前驱结点，因此删除结点时指针只需要移动 $i$i 次。
2. 查找结点时，双链表可以借用二分法的思路，从head（首节点）向后查找，同时从last（尾节点）向前查找，因此效率更高。

为什么市场上单链表的使用多于双链表呢？

1. 从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，总共需要额外 n*length的内存空间（指针length在32位系统中是4字节，在64位中是8字节）
2. 如果不追求时间效率就会采用 以时间换空间 的做法，是一种工程总体上的衡量。

以上参考：浅谈单链表与双链表的区别