本文主要是介绍2021-04-11，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

List集合

• 1. List接口简介
• • 1.1 ArrayList和LinkedList
  • 1.2 Vector和Stack
  • 1.3 Vector 类和 ArrayList 类的区别
• 2. ArrayList
• • 2.1 ArrayList 要点
  • 2.2 ArrayList 原理
  • • 2.2-1 ArrayList 的数据结构
    • 2.2-2 ArrayList 的get方法
    • 2.2-3 ArrayList 的add方法
    • 2.2-4 ArrayList 的remove方法
• 3. LinkedList
• • 3.1 LinkedList 要点
  • 3.2 LinkedList 原理
  • • 3.2-1 LinkedList 数据结构
    • 3.2-2 LinkedList 的get方法
    • 3.2-3 LinkedList 的add方法
    • 3.2-4 LinkedList 的remove方法

1. List接口简介

1.List接口继承Collection接口，实现了List接口的类称为List集合。

2.在List集合中允许出现重复的元素，所有元素以线性方式进行存储，可以通过索引来访问集合中指定的元素。List集合的元素的存储顺序和取出顺序一致。

1.1 ArrayList和LinkedList

ArrayList和LinkedList是List 最常用的实现类。

差别：
	ArrayList 基于动态数组实现，存在容量限制，当元素数超过最大容量时，会自动扩容。
	LinkedList 基于双向链表实现，不存在容量限制。

	ArrayList 随机访问速度较快，随机插入、删除速度较慢
	LinkedList 随机插入、删除速度较快，随机访问速度较慢。
相同：
	ArrayList 和 LinkedList 都是线程不安全的。

1.2 Vector和Stack

Vector 和 Stack 是作为线程安全的 List 实现。
Vector 和 ArrayList 类似，也实现了 List 接口。但是， Vector 中的主要方法都是 synchronized 方法

1.3 Vector 类和 ArrayList 类的区别

2. ArrayList

2.1 ArrayList 要点

ArrayList是一个数组队列（动态数组），默认初始容量为10，当数组容量不够时会自动扩容到原来的1.5倍。所以在初始化ArrayList时，为其指定合适的初始化容量，可以减少扩容产生的性能消耗。

ArrayList的构造方法

2.2 ArrayList 原理

2.2-1 ArrayList 的数据结构

ArrayList 包含了两个重要的元素：elementData 和 size。

// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 对象数组 ，添加保存到集合中的元素
transient Object[] elementData;
// 数组长度
private int size;

2.2-2 ArrayList 的get方法

get方法是通过数组下标获取元素
源码:

// 获取第 index 个元素
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

2.2-3 ArrayList 的add方法

add元素有两种方法：一种是添加到数组末尾；一种是添加到数组的任意位置
源码:

// 添加元素到数组末尾
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 添加元素到任意位置
public void add(int index, E element) {
	rangeCheckForAdd(index);

	ensureCapacityInternal(size + 1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
					 size - index);
	elementData[index] = element;
	size++;
}

两种添加元素方法的不同点是：

添加元素到任意位置，会导致在该位置后的所有元素都需要重新排列；
而添加元素到数组末尾，在没有发生扩容的前提下，是不会有元素复制排序过程的。

ArrayList 执行添加元素动作（add 方法）时，调用 ensureCapacityInternal 方法来保证容量足够。

如果容量足够时，将数据作为数组中 size+1 位置上的元素写入，并将 size 自增 1。
如果容量不够时，需要使用 grow 方法进行扩容数组，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
扩容操作实际上是调用 Arrays.copyOf() 把原数组拷贝为一个新数组，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

2.2-4 ArrayList 的remove方法

当删除一个有效元素后，会对集合进行重新排序，删除元素后面的元素会 index+1。
源码:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

3. LinkedList

3.1 LinkedList 要点

LinkedList 基于双链表结构实现。由于是双链表，所以顺序访问会非常高效，而随机访问效率比较低。删除速度较快，随机访问速度较慢。

3.2 LinkedList 原理

3.2-1 LinkedList 数据结构

LinkedList 内部维护了一个双链表。
LinkedList 通过 Node 类型的头尾指针（first 和 last）来访问数据。

// 链表长度
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;

Node 是 LinkedList 的内部类，它表示链表中的元素实例。Node 中包含三个元素：

prev 是该节点的上一个节点；
next 是该节点的下一个节点；
item 是该节点所包含的值。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    ...
}

3.2-2 LinkedList 的get方法

 public static void main(String[] args) {  
    LinkedList<String> list = new LinkedList<String>();  
    list.add("1");  
    list.add("2");  
    list.add("3");  
    list.add("4");  
    list.add("5");  
    System.out.println("索引的第一个元素是 : " + list.get(0));
    System.out.println("链表的第一个元素是 : " + list.getFirst());  
    System.out.println("链表最后一个元素是 : " + list.getLast());  
  }  

源码

public E get(int index) {
	checkElementIndex(index);
	return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

3.2-3 LinkedList 的add方法

LinkedList 有多种添加元素方法：

add(E e)：默认添加元素方法（插入尾部）
add(int index, E element)：添加元素到任意位置
addFirst(E e)：在头部添加元素
addLast(E e)：在尾部添加元素

public static void main(String[] a) {  
    LinkedList list = new LinkedList();  
    list.add("A");  
    list.add("B");  
    list.add("C");  
    list.add("D");  
    list.add(2,"E");
    list.addFirst("X");  
    list.addLast("Z");  
    System.out.println(list);   //[X, A, B, E, C, D, Z]
  } 
  //通过迭代器遍历输出
  Iterator iterator = list.iterator();
        while (iterator.hasNext()){
        System.out.println(iterator.next());
  }

add算法如下：

将新添加的数据包装为 Node；
如果往头部添加元素，将头指针 first 指向新的 Node，之前的 first 对象的 prev 指向新的 Node。
如果是向尾部添加元素，则将尾指针 last 指向新的 Node，之前的 last 对象的 next 指向新的 Node。

3.2-4 LinkedList 的remove方法

public static void main(String[] a) {   
    LinkedList list = new LinkedList();  
    list.add("A");  
    list.add("B");  
    list.add("C");  
    list.add("D");  
    list.remove(0);//删除索引的第一个元素
    list.removeFirst();  //也是删除第一个元素
    list.removeLast();  //删除最后一个元素
    System.out.println(list);  
  }  

remove原理：
要删除的当前节点，如果有上一个节点，则让上一个节点指向当前节点的下一个节点；如果有下一个节点，则让下一个节点指向当前节点的上一个节点

这篇关于2021-04-11的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！