数组和链表的区别_相对于数组链表的特点之一是长度不固定

作者：2023面试高手 | 2024-06-05 11:50:56

踩

相对于数组链表的特点之一是长度不固定

1、大小区别

数组大小是固定的，一开始定义多长就是多长，不能改变；

链表大小不固定，可以再申请内存，增加长度；

2、存储方式不同

数组存储在栈中，存储位置连续；

链表存储在堆中，存储位置不连续；

3、定位的时间复杂度不同

数组定位元素的时间复杂度是O(1),随机访问速度快;

链表定位元素的时间复杂度是O(n),随机访问速度较慢;

3、插入和删除的时间复杂度不同

不管插入位置已知不已知，每次插入一个元素就需要移动已有元素,数组的时间复杂度均为O(n);

链表在插入位置未知时，需遍历指针，找到插入位置，时间复杂度为O(n),在插入位置已知的情况下，直接插入即可，时间复杂度为O(1),删除/添加数据的效率很高。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/676379