数据结构--数组、单向链表、双向链表

线性表：

顺序线性表和链表

顺序线性表：

1. 就是数组（c语言），初始化固定数组的大小，申请连续的内存分配。
2. 可能面临的问题有：数组边界溢出，不够存，需要重新申请新的连续的内存空间，造成内存浪费，性能下降，拓展性差。
3. 数组实际大小可能没有等于初始化定义的，也造成内存浪费。
4. 但是相对链表来说，数组的优点是通过数组下标可以快速找到数据的内存地址，查找效率高（o（1）），但是相反，插入和删除数据，后面的数据都要进行移动，效率低（o（n））。

链表：

1. 分为单向链表、双向链表、循环链表等。
2. 跟数组最大的不同的是，链表是不连续的内存，其利用的是整合碎片内存空间起来组成一个链表，合理利用和节约了内存空间，提高性能。
3. 数据变动不会受到类似数组边界等限制，动态能力比较高，拓展性好。
4. 单向链表查找数据的效率需要从表头一步一步的往下找，查找效率低（o（n））。
5. 双向链表就是为了解决查找效率问题而诞生的，其可以从链表的任何一个位置从两边开始寻找，使用二分法查找的效率明显提高了，查找效率最高的还是数组。
6. 双向链表比单向链表多了一个属性，来指向上一个节点的地址，其查找效率是用过牺牲空间换时间的做法。
7. 链表的插入和删除效率（o（1））比数组高，因为它不涉及到后面整组数据的变动，只需要前或者前后的指向属性做修改就可以了。

单向链表结构图：

用面向对象的思想就是有两个属性，一个是值，一个是指向。末尾的指针指向空值

双向链表结构图：

有三个属性，一个是值，一个是前一个节点的指针 ，一个是下一个节点的指针，前后的指针指向空值

总结：

本作品采用《CC 协议》，转载必须注明作者和本文链接