一、在C语言下数组array与链表linklist各自的优点和缺陷
数组可以通过下标访问，随机访问效率高，链表需要通过指针遍历，访问效率低。
数组在分配空间后不能再改变大小，如果满了之后再放东西就必须重新分配一个较大的内存空间，将原来的数组内容拷贝进去。而链表可以随意插入，比数组灵活。
存相同的数据，链表占用的内存空间大，因为要分配额外的内存存下一个节点的内存地址。
ArrayList
ArrayList是动态扩展数组，底层是用数组实现，插入位置有三种情况，从首位插入，中间位置插入，尾部插入。线性表的插入删除操作都是通过移动来实现的，由于数组长度固定不变，插入数据时，需要一个新的数组。1.当添加数据是在首位插入时，先将新的数据放入到新的数组内，然后将原始数组中的数据复制到新的数组。
2.当数据插入的位置是中间位置时，先将插入位置前面的数据先放到新的数组里，再放新的数据，再复制旧的数据完成添加。3.数据尾部插入，由于不会影响其他元素，因此会直接插入到后面。
同样，删除按位置也有三种情况：1.从头部删除，删除头结点然后移动后面的数据
2.从中间指定位置删除，找到要删除数据的位置，删除后，后面的数据移动.3.从尾部删除：直接删除尾部数据完成删除操作。
LinkedList
LinkedList是双向链表的数据结构，底层是用链表实现，是由相互引用的节点组成的双向链表，当插入数据到某个位置时，这个数据会形成一个新的节点，然后改变链表中对应的两个节点的引用关系就可以完成插入。同样，删除数据时，删除对应节点的引用就可以完成删除操作。
延伸阅读：
二、链表与数组的主要区别
（1）数组的元素个数是固定的,而组成链表的结点个数可按需要增减;
（2）数组元素的存诸单元在数组定义时分配，链表结点的存储单元在程序执行时动态向系统申请:
（3）数组中的元素顺序关系由元素在数组中的位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。
（4）对于不是固定长度的列表,用可能最大长度的数组来描述，会浪费许多内存空间。
（5）对于元素的插人、删除操作非常频繁的列表处理场合,用数组表示列表也是不适宜的。若用链表实现，会使程序结构清晰，处理的方法也较为简便。
例如：在一个列表中间要插人一个新元素，如用数组表示列表，为完成插人工作，插人处之后的全部元素必须向后移动一个位置空出的位置用于存储新元素。
对于在一个列表中删除一个元素情况，为保持数组中元素相对位置连续递增，删除处之后的元素都得向前移一个位置。如用链表实现列表.链表结点的插人或删除操作不再需要移动结点，只需改变相关的结点中的后继结点指针的值即可，与结点的实际存储位置无关。
京公网安备 11010802030320号