关于ArrayList和LinkedList详细区别,在链表的排序这些最好统统说一下

时间:2022-05-24 22:05:47
关于ArrayList和LinkedList详细区别,在链表的排序这些最好统统说一下,今天面试问了下这个,居然面试官给我说出了很大一推。我想详细的了解一下这两个的区别

7 个解决方案

#1


看看JDK的帮助吧
ArrayList
引用
List 接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行,也就是说,添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行(大体上讲)。与用于 LinkedList 实现的常数因子相比,此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

LinkedList
引用
List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列 (deque)。

此类实现 Queue 接口,为 add、poll 等提供先进先出队列操作。其他堆栈和双端队列操作可以根据标准列表操作方便地进行再次强制转换。虽然它们可能比等效列表操作运行稍快,但是将其包括在这里主要是出于方便考虑。

所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。

#2


注意, 虽然它们可能比等效列表操作运行稍快,但是将其包括在这里主要是出于方便考虑。 

#3


ArrayList
1、它是用数组结构来实现的;
2、随机访问效率高;
3、不适合经常作插入删除操作;
4、对容量不确定的效率较低,可能经常要对元素进行复制;
5、可以包含null元素;


LinkedList
1、它是用链表结构来实现的;
2、随机访问效率低;
3、适合作插入删除操作;
4、可以很好解决容量的不确定性;
5、可以包含null元素;
6、适合用来作为栈数据结构


看下面补兖。。。。

#4


要我说,也只能说个三四个

#5


说白了,就是数据结构中的双向链表(所以如果要用ListIterator,最好使用LinkedList)与顺序表.

最好看看源码才有更深体会.

#6


正如楼上所说的 就是一个事类似数组,一个类似指针
只是很多代码不用自己写 高效
希望对你有帮助

#7


别的说不上来,但一个数组结构,一个链表结构应该明白吧,数据结构中重点讲过这两种,数组插入删除慢,因为要移动所有插入或删除位置的后面的元素,但查找快,因为有数组下标,直接访问,链表的话相反,查找得从第一个或最后一个开始,一个一个通过next来查找,但插入删除快,因为它只影响到插入或删除位置的前后2个元素(当然,单向链表的话如果是头结点或尾结点也可能只影响一个元素)

#1


看看JDK的帮助吧
ArrayList
引用
List 接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间 运行,也就是说,添加 n 个元素需要 O(n) 时间。其他所有操作都以线性时间运行(大体上讲)。与用于 LinkedList 实现的常数因子相比,此实现的常数因子较低。

每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。

在添加大量元素前,应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

LinkedList
引用
List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列 (deque)。

此类实现 Queue 接口,为 add、poll 等提供先进先出队列操作。其他堆栈和双端队列操作可以根据标准列表操作方便地进行再次强制转换。虽然它们可能比等效列表操作运行稍快,但是将其包括在这里主要是出于方便考虑。

所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。

#2


注意, 虽然它们可能比等效列表操作运行稍快,但是将其包括在这里主要是出于方便考虑。 

#3


ArrayList
1、它是用数组结构来实现的;
2、随机访问效率高;
3、不适合经常作插入删除操作;
4、对容量不确定的效率较低,可能经常要对元素进行复制;
5、可以包含null元素;


LinkedList
1、它是用链表结构来实现的;
2、随机访问效率低;
3、适合作插入删除操作;
4、可以很好解决容量的不确定性;
5、可以包含null元素;
6、适合用来作为栈数据结构


看下面补兖。。。。

#4


要我说,也只能说个三四个

#5


说白了,就是数据结构中的双向链表(所以如果要用ListIterator,最好使用LinkedList)与顺序表.

最好看看源码才有更深体会.

#6


正如楼上所说的 就是一个事类似数组,一个类似指针
只是很多代码不用自己写 高效
希望对你有帮助

#7


别的说不上来,但一个数组结构,一个链表结构应该明白吧,数据结构中重点讲过这两种,数组插入删除慢,因为要移动所有插入或删除位置的后面的元素,但查找快,因为有数组下标,直接访问,链表的话相反,查找得从第一个或最后一个开始,一个一个通过next来查找,但插入删除快,因为它只影响到插入或删除位置的前后2个元素(当然,单向链表的话如果是头结点或尾结点也可能只影响一个元素)