首页 > 其他分享 >2. List

2. List

时间:2024-12-22 21:44:02浏览次数:10  
标签:LinkedList ArrayList List Vector 数组 复杂度

Java的List是非常常用的数据类型,List是有序的集合,可以包含重复的元素,提供了按索引访问的方式,继承自Collection。
Java List一共三个实现类:分别是ArrayList、Vector和LinkedList。

  1. ArrayList(数组)
    ArrayList是最常用的List实现类,内部是通过Array(数组)实现的,Array(数组)是基于索引(index)的数据结构,是数组动态扩容实现,它使用索引在数组中搜索和读取数据很快,占用连续的内存空间。
    Array获取数据的时间复杂度是O(1),但要删除数据的开销却是很大,因为这需要重排数组中的所有数据,删除数据后需要把后面所有的数据前移,时间复杂度为O(n)。
    因此它适合随机查找和遍历,不适合插入和删除。
    ArrayList的toArray()方法返回一个数组,asList()返回一个列表

  2. Vector(数组实现 线程同步)
    Vector与ArrayList一样,也是通过数组实现的, 不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。

  3. LinkedList(链表)
    LinkedList内部是用链表结构存储数据的,很适合数据的动态插入和删除,不需要连续的内存空间。
    LinkedList随机访问速度慢,需要从头节点开始遍历,时间复杂度为O(n),在中间插入和删除元素较快,只需要修改节点的引用,时间复杂度为O(1),

标签:LinkedList,ArrayList,List,Vector,数组,复杂度
From: https://www.cnblogs.com/tim-zuo/p/18622598

相关文章