从Java看数组和链表的区别

2017-01-01 10:46

首先,二者都属于数据结构的范畴。
数组一旦初始化,长度就不能改变。链表长度可以改变,可以动态的增加节点数据,操作比较灵活;
数组是可以有一维二维三维。。。属于非线性结构,链表是线性结构;
数组访问元素依靠下角标,比如查找第n是数据,直接arrn-1,时间复杂度是O(1)。链表访问元素得从头开始依次查找,根据引用找到下一个节点,时间复杂度是O(n);
数组插入删除中间数据比较麻烦,时间复杂度是O(n)。链表插入删除比较方便,时间复杂度是O(1);
所以如果需要快速访问数据并且涉及很少插入删除操作那么就选用数组。如果涉及比较多的删除插入那么选用链表;
数组在栈内存中存储引用,在堆内存中存储对象。链表存储在堆内存中,由于存储在堆内存中,需要手动分配内存;
数组在内存中是连续存储的,链表不是连续的。

http://blog.csdn.net/u014672511/article/details/46911661