深圳幻海软件技术有限公司 欢迎您！
更多

ArrayList和LinkedList

2023-05-08

int list add
目录ArrayList1.ArrayList简介2.ArrayList使用2.1ArrayList的构造  2.2ArrayList常见操作2.3ArrayList的遍历2.4ArrayList的扩容机制3.ArrayList的具体使用4.ArrayList的问题5.ArrayL

目录

ArrayList

1.ArrayList简介

2.ArrayList使用

2.1ArrayList的构造 

 2.2ArrayList常见操作

2.3ArrayList的遍历

2.4ArrayList的扩容机制

3.ArrayList的具体使用

4.ArrayList的问题

5.ArrayList的缺陷

LinkedList

1.LinkedList的模拟实现

2.LinkedList的使用

2.1什么是LinkedList

2.2LinkedList的使用

ArrayList和LinkedList的区别

ArrayList

1.ArrayList简介

在集合框架中， ArrayList 是一个普通的类，实现了 List 接口，具体框架图如下：
【 说明 】
1. ArrayList 是以泛型方式实现的，使用时必须要先实例化
2. ArrayList 实现了 RandomAccess 接口，表明 ArrayList 支持随机访问
3. ArrayList 实现了 Cloneable 接口，表明 ArrayList 是可以 clone 的
4. ArrayList 实现了 Serializable 接口，表明 ArrayList 是支持序列化的
5. 和 Vector 不同， ArrayList 不是线程安全的，在单线程下可以使用，在多线程中可以选择 Vector 或者
CopyOnWriteArrayList
6. ArrayList 底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.ArrayList使用

2.1ArrayList的构造 

  1. public static void main(String[] args) {
  2.     // ArrayList创建，推荐写法
  3.     // 构造一个空的列表
  4.     List<Integer> list1 = new ArrayList<>();
  5.     // 构造一个具有10个容量的列表
  6.     List<Integer> list2 = new ArrayList<>(10);
  7.     list2.add(1);
  8.     list2.add(2);
  9.     list2.add(3);
  10.     // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
  11.     // list3构造好之后，与list中的元素一致
  12.     ArrayList<Integer> list3 = new ArrayList<>(list2);
  13.     // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
  14.     List list4 = new ArrayList();
  15.     list4.add("111");
  16.     list4.add(100);
  17. }

 2.2ArrayList常见操作

ArrayList 虽然提供的方法比较多，但是常用方法如下所示，需要用到其他方法时，同学们自行查看 ArrayList 的帮助文档。
方法解释
boolean add (E e)
尾插 e
void add (int index, E element)
将 e 插入到 index 位置
boolean addAll (Collection<? extends E> c)
尾插 c 中的元素
E remove (int index)
删除 index 位置元素
boolean remove (Object o)
删除遇到的第一个 o
E get (int index)
获取下标 index 位置元素
E set (int index, E element)
将下标 index 位置元素设置为 element
void clear ()
清空
boolean contains (Object o)
判断 o 是否在线性表中
int indexOf (Object o)
返回第一个 o 所在下标
int lastIndexOf (Object o)
返回最后一个 o 的下标
List<E> subList (int fromIndex, int toIndex)
截取部分 list 
  1. public static void main(String[] args) {
  2.     List<String> list = new ArrayList<>();
  3.     list.add("JavaSE");
  4.     list.add("JavaWeb");
  5.     list.add("JavaEE");
  6.     list.add("JVM");
  7.     list.add("测试课程");
  8.     System.out.println(list);
  9.     // 获取list中有效元素个数
  10.     System.out.println(list.size());
  11.     // 获取和设置index位置上的元素，注意index必须介于[0, size)间
  12.     System.out.println(list.get(1));
  13.     list.set(1, "JavaWEB");
  14.     System.out.println(list.get(1));
  15.     // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
  16.     list.add(1, "Java数据结构");
  17.     System.out.println(list);
  18.     // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
  19.     list.remove("JVM");
  20.     System.out.println(list);
  21.     // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
  22.     list.remove(list.size()-1);
  23.     System.out.println(list);
  24.     // 检测list中是否包含指定元素，包含返回true，否则返回false
  25.     if(list.contains("测试课程")){
  26.     list.add("测试课程");
  27.     }
  28.     // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
  29.     list.add("JavaSE");
  30.     System.out.println(list.indexOf("JavaSE"));
  31.     System.out.println(list.lastIndexOf("JavaSE"));
  32.     // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
  33.     List<String> ret = list.subList(0, 4);
  34.     System.out.println(ret);
  35.     list.clear();
  36.     System.out.println(list.size());
  37. }

2.3ArrayList的遍历

ArrayList 可以使用三方方式遍历： for 循环 + 下标、 foreach 、使用迭代器 
  1. public static void main(String[] args) {
  2.     List<Integer> list = new ArrayList<>();
  3.     list.add(1);
  4.     list.add(2);
  5.     list.add(3);
  6.     list.add(4);
  7.     list.add(5);
  8.     // 使用下标+for遍历
  9.     for (int i = 0; i < list.size(); i++) {
  10.     System.out.print(list.get(i) + " ");
  11.     }
  12.     System.out.println();
  13.     // 借助foreach遍历
  14.     for (Integer integer : list) {
  15.     System.out.print(integer + " ");
  16.     }
  17.     System.out.println();
  18.     Iterator<Integer> it = list.listIterator();
  19.     while(it.hasNext()){
  20.     System.out.print(it.next() + " ");
  21.     }
  22.     System.out.println();
  23. }
注意：
1. ArrayList 最长使用的遍历方式是： for 循环 + 下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

2.4ArrayList的扩容机制

ArrayList 是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是 ArrayList 源码中扩容方式： 
  1. Object[] elementData; // 存放元素的空间
  2. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
  3. private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
  4. public boolean add(E e) {
  5.     ensureCapacityInternal(size + 1); // Increments modCount!!
  6.     elementData[size++] = e;
  7.     return true;
  8. }
  9. private void ensureCapacityInternal(int minCapacity) {
  10.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  11. }
  12. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  13.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  14.     return Math.max(DEFAULT_CAPACITY, minCapacity);
  15.     }
  16.     return minCapacity;
  17. }
  18. private void ensureExplicitCapacity(int minCapacity) {
  19.     modCount++;
  20.     // overflow-conscious code
  21.     if (minCapacity - elementData.length > 0)
  22.     grow(minCapacity);
  23. }
  24. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  25. private void grow(int minCapacity) {
  26.     // 获取旧空间大小
  27.     int oldCapacity = elementData.length;
  28.     // 预计按照1.5倍方式扩容
  29.     int newCapacity = oldCapacity + (oldCapacity >> 1);
  30.     // 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
  31.     if (newCapacity - minCapacity < 0)
  32.     newCapacity = minCapacity;
  33.     // 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
  34.     if (newCapacity - MAX_ARRAY_SIZE > 0)
  35.     newCapacity = hugeCapacity(minCapacity);
  36.     // 调用copyOf扩容
  37.     elementData = Arrays.copyOf(elementData, newCapacity);
  38. }
  39. private static int hugeCapacity(int minCapacity) {
  40.     // 如果minCapacity小于0，抛出OutOfMemoryError异常
  41.     if (minCapacity < 0)
  42.     throw new OutOfMemoryError();
  43.     return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
  44. }
【 总结 】
1. 检测是否真正需要扩容，如果是调用 grow 准备扩容
2. 预估需要库容的大小
  • 初步预估按照1.5倍大小扩容
  • 如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
  • 真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用 copyOf 进行扩容

3.ArrayList的具体使用

简单的洗牌算法 
  1. public class Card {
  2.     public int rank; // 牌面值
  3.     public String suit; // 花色
  4.     @Override
  5.     public String toString() {
  6.     return String.format("[%s %d]", suit, rank);
  7.     }
  8. }
  1. import java.util.List;
  2. import java.util.ArrayList;
  3. import java.util.Random;
  4. public class CardDemo {
  5.     public static final String[] SUITS = {"♠", "♥", "♣", "♦"};
  6.     // 买一副牌
  7.     private static List<Card> buyDeck() {
  8.         List<Card> deck = new ArrayList<>(52);
  9.         for (int i = 0; i < 4; i++) {
  10.             for (int j = 1; j <= 13; j++) {
  11.             String suit = SUITS[i];
  12.             int rank = j;
  13.             Card card = new Card();
  14.             card.rank = rank;
  15.             card.suit = suit;
  16.             deck.add(card);
  17.             }
  18.         }
  19.         return deck;
  20.     }
  21.     private static void swap(List<Card> deck, int i, int j) {
  22.         Card t = deck.get(i);
  23.         deck.set(i, deck.get(j));
  24.         deck.set(j, t);
  25.     }
  26.     private static void shuffle(List<Card> deck) {
  27.         Random random = new Random(20190905);
  28.         for (int i = deck.size() - 1; i > 0; i--) {
  29.         int r = random.nextInt(i);
  30.         swap(deck, i, r);
  31.         }
  32.     }
  33.     public static void main(String[] args) {
  34.         List<Card> deck = buyDeck();
  35.         System.out.println("刚买回来的牌:");
  36.         System.out.println(deck);
  37.         shuffle(deck);
  38.         System.out.println("洗过的牌:");
  39.         System.out.println(deck);
  40.         // 三个人，每个人轮流抓 5 张牌
  41.         List<List<Card>> hands = new ArrayList<>();
  42.         hands.add(new ArrayList<>());
  43.         hands.add(new ArrayList<>());
  44.         hands.add(new ArrayList<>());
  45.         for (int i = 0; i < 5; i++) {
  46.             for (int j = 0; j < 3; j++) {
  47.             hands.get(j).add(deck.remove(0));
  48.             }
  49.         }
  50.         System.out.println("剩余的牌:");
  51.         System.out.println(deck);
  52.         System.out.println("A 手中的牌:");
  53.         System.out.println(hands.get(0));
  54.         System.out.println("B 手中的牌:");
  55.         System.out.println(hands.get(1));
  56.         System.out.println("C 手中的牌:");
  57.         System.out.println(hands.get(2));
  58.     }
  59. }
运行结果 
  1. 刚买回来的牌:
  2. [[♠ 1], [♠ 2], [♠ 3], [♠ 4], [♠ 5], [♠ 6], [♠ 7], [♠ 8], [♠ 9], [♠ 10], [♠ 11], [♠ 12], [♠ 13], [♥ 1], [♥ 2], [♥ 3], [♥ 4], [♥ 5], [♥ 6], [♥ 7],
  3. [♥ 8], [♥ 9], [♥ 10], [♥ 11], [♥ 12], [♥ 13], [♣ 1], [♣ 2], [♣ 3], [♣ 4], [♣ 5], [♣ 6], [♣ 7], [♣ 8], [♣ 9], [♣ 10], [♣ 11], [♣ 12], [♣
  4. 13], [♦ 1], [♦ 2], [♦ 3], [♦ 4], [♦ 5], [♦ 6], [♦ 7], [♦ 8], [♦ 9], [♦ 10], [♦ 11], [♦ 12], [♦ 13]]
  5. 洗过的牌:
  6. [[♥ 11], [♥ 6], [♣ 13], [♣ 10], [♥ 13], [♠ 2], [♦ 1], [♥ 9], [♥ 12], [♦ 5], [♥ 8], [♠ 6], [♠ 3], [♥ 5], [♥ 1], [♦ 6], [♦ 13], [♣ 12], [♦ 12],
  7. [♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠
  8. 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]
  9. 剩余的牌:
  10. [[♦ 6], [♦ 13], [♣ 12], [♦ 12], [♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦
  11. 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]
  12. A 手中的牌:
  13. [[♥ 11], [♣ 10], [♦ 1], [♦ 5], [♠ 3]]
  14. B 手中的牌:
  15. [[♥ 6], [♥ 13], [♥ 9], [♥ 8], [♥ 5]]
  16. C 手中的牌:
  17. [[♣ 13], [♠ 2], [♥ 12], [♠ 6], [♥ 1]]

4.ArrayList的问题

1. ArrayList 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200 ，我们再继续插入了5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

5.ArrayList的缺陷

通过源码知道， ArrayList 底层使用数组来存储元素：
由于其底层是一段连续空间，当 在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。

LinkedList

1.LinkedList的模拟实现

  1. // 2、无头双向链表实现
  2. public class MyLinkedList {
  3.     //头插法
  4.     public void addFirst(int data){ }
  5.     //尾插法
  6.     public void addLast(int data){}
  7.     //任意位置插入,第一个数据节点为0号下标
  8.     public void addIndex(int index,int data){}
  9.     //查找是否包含关键字key是否在单链表当中
  10.     public boolean contains(int key){}
  11.     //删除第一次出现关键字为key的节点
  12.     public void remove(int key){}
  13.     //删除所有值为key的节点
  14.     public void removeAllKey(int key){}
  15.     //得到单链表的长度
  16.     public int size(){}
  17.     public void display(){}
  18.     public void clear(){}
  19. }

2.LinkedList的使用

2.1什么是LinkedList

LinkedList 的底层是双向链表结构 ( 链表后面介绍 ) ，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

 在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】
        1. LinkedList实现了 List 接口
        2. LinkedList的底层使用了双向链表
        3. LinkedList没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问
        4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)
        5. LinkedList比较适合任意位置插入的场景

2.2LinkedList的使用

LinkedList 的构造 

  1. public static void main(String[] args) {
  2.     // 构造一个空的LinkedList
  3.     List<Integer> list1 = new LinkedList<>();
  4.     List<String> list2 = new java.util.ArrayList<>();
  5.     list2.add("JavaSE");
  6.     list2.add("JavaWeb");
  7.     list2.add("JavaEE");
  8.     // 使用ArrayList构造LinkedList
  9.     List<String> list3 = new LinkedList<>(list2);
  10. }

 LinkedList的其他常用方法介绍

方法解释
boolean add (E e)
尾插 e
void add (int index, E element)
将 e 插入到 index 位置
boolean addAll (Collection<? extends E> c)
尾插 c 中的元素
E remove (int index)
删除 index 位置元素
boolean remove (Object o)
删除遇到的第一个 o
E get (int index)
获取下标 index 位置元素
E set (int index, E element)
将下标 index 位置元素设置为 element
void clear ()
清空
boolean contains (Object o)
判断 o 是否在线性表中
int indexOf (Object o)
返回第一个 o 所在下标
int lastIndexOf (Object o)
返回最后一个 o 的下标
List<E> subList (int fromIndex, int toIndex)
截取部分 list 
  1. public static void main(String[] args) {
  2.     LinkedList<Integer> list = new LinkedList<>();
  3.     list.add(1); // add(elem): 表示尾插
  4.     list.add(2);
  5.     list.add(3);
  6.     list.add(4);
  7.     list.add(5);
  8.     list.add(6);
  9.     list.add(7);
  10.     System.out.println(list.size());
  11.     System.out.println(list);
  12.     // 在起始位置插入0
  13.     list.add(0, 0); // add(index, elem): 在index位置插入元素elem
  14.     System.out.println(list);
  15.     list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
  16.     list.removeFirst(); // removeFirst(): 删除第一个元素
  17.     list.removeLast(); // removeLast(): 删除最后元素
  18.     list.remove(1); // remove(index): 删除index位置的元素
  19.     System.out.println(list);
  20.     // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
  21.     if(!list.contains(1)){
  22.         list.add(0, 1);
  23.     }
  24.     list.add(1);
  25.     System.out.println(list);
  26.     System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
  27.     System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
  28.     int elem = list.get(0); // get(index): 获取指定位置元素
  29.     list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
  30.     System.out.println(list);
  31.     // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  32.     List<Integer> copy = list.subList(0, 3); 
  33.     System.out.println(list);
  34.     System.out.println(copy);
  35.     list.clear(); // 将list中元素清空
  36.     System.out.println(list.size());
  37. }
LinkedList 的遍历 
  1. public static void main(String[] args) {
  2.     LinkedList<Integer> list = new LinkedList<>();
  3.     list.add(1); // add(elem): 表示尾插
  4.     list.add(2);
  5.     list.add(3);
  6.     list.add(4);
  7.     list.add(5);
  8.     list.add(6);
  9.     list.add(7);
  10.     System.out.println(list.size());
  11.     // foreach遍历
  12.     for (int e:list) {
  13.         System.out.print(e + " ");
  14.     }
  15.     System.out.println();
  16.     // 使用迭代器遍历---正向遍历
  17.     ListIterator<Integer> it = list.listIterator();
  18.     while(it.hasNext()){
  19.         System.out.print(it.next()+ " ");
  20.     }
  21.     System.out.println();
  22.     // 使用反向迭代器---反向遍历
  23.     ListIterator<Integer> rit = list.listIterator(list.size());
  24.     while (rit.hasPrevious()){
  25.         System.out.print(rit.previous() +" ");
  26.     }
  27.     System.out.println();
  28. }

ArrayList和LinkedList的区别

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45765 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪