Java基础之集合List（ArrayList， LinkedList 和 Vector 的区别）

喜欢ヅ旅行 2024-04-17 06:06 44阅读 0赞

## List ##

### List是一个接口，实现类常用的有 ArrayList,LinkedList和Vector ###

### ArrayList ###

##### 1. 基于数组实现的的， 根据容量大小利用Arrays.copyOf方法实现动态扩容。 #####

源码
    
        // elementData 动态数组
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        
        // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是{} 空数组， DEFAULT_CAPACITY是10
        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
        
        // 可见list数组的默认长度为10
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }    
    
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

简单的实现原理

public class ListDemo {
    
        // 定义初始数组
        String[] arr = {};
    
        // 数组扩容
        public void dilatation(int capacity) {
            arr = Arrays.copyOf(arr, capacity);
    
        }
    
        public static void main(String[] a) {
            ListDemo listDemo = new ListDemo();
            System.out.println(listDemo.arr.length);
            System.out.println(Arrays.toString(listDemo.arr));
            // 扩容后给数组赋值
            listDemo.dilatation(1);
            listDemo.arr[0] = "222";
            System.out.println(listDemo.arr.length);
            System.out.println(Arrays.toString(listDemo.arr));
              // 扩容后给数组赋值
            listDemo.dilatation(2);
            listDemo.arr[1] = "333";
            System.out.println(listDemo.arr.length);
            System.out.println(Arrays.toString(listDemo.arr));
        }
    
    }

##### 2. ArrayList 是有序的，可以看到新增的数据是根据size，集合的大小插入的 #####

源码
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

##### 3. ArrayList 中查询更快捷，因为是根据数组下标进行查询。 #####

源码
        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }
        
        E elementData(int index) {
            return (E) elementData[index];
        }

##### 4. ArrayList 添加删除操作效率低，是因为每次增加或删除时要对数组容量进行修改。 System.arraycopy()实现数组的复制 #####

System.arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
    
    src 原数组
    srcPos 原数组复制的起始位置（下标）
    dest 目标数组
    destPos 目标数组的起始位置（下标）
    length 复制数组的长度
    
    
    举例
        public static void main(String[] a) {
            // 我要将 4,7,9 替换成了7,9,8
            Integer[] arr = {2,6,5,4,7,9,8,1,3};
    
            // 将 arr源数组从第下标4 开始复制3位 也就是 7,9,8  替换arr目标数组中下标3 开始的三位4,7,9。也就是将 4,7,9 替换成了7,9,8
            System.arraycopy(arr, 4, arr, 3, 3 );
    
            System.out.println(Arrays.toString(arr));
        }

源码
        // 删除
        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;
        }
        // 添加
        
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        
        // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是{} 空数组， DEFAULT_CAPACITY是10
        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
        
        // 可见list数组的默认长度为10
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }    
    
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

##### 5. ArrayList 对于修改效率高，因为是根据下标直接获取到目标对象，直接修改 #####

源码
        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

### LinkedList ###

LinkedList源码中有这样几个对象属性

1.  first 第一个节点
2.  last 最后一个节点

节点类有这样几个信息

1.  item 本身的信息
2.  next 下一个节点对象
3.  prev 上一个节点对象

源码
        private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

#### 1. 基于链表实现，每一个节点中都会保存当前节点，上一个节点和下一个节点。 ####

#### 2. 添加更快捷，因为不需要跟ArrayList一样需要考虑容量问题。只需要创建新的节点，就行了。 ####

源码
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
        
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

#### 3. 删除我不认为会快捷多少。因为链表也不能直接找到要删除的节点，只能根据第一个节点和最后一个节点来找 ####

源码
        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        
            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;
            }
        }
        
            E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }

源码说明：

1.  调用remove(int index) 删除
2.  程序或根据node(int index) 找到要删除的节点。这块我认为数据量大的时候也是很耗时的。  
    先根据集合大小和查找对象的位置决定是从最后一个开始比对还是从第一个节点开始比对。最终获取要删除的节点
3.  unlink(Node x) 删除节点方法。根据x节点的信息，取出上一个节点（prev）和下一个节点（prev）。将上一个节点保存的下一个节点修改为x节点的下一个节点，将下一个节点的上一个节点修改为x节点的上一个节点，最后删除此节点

#### 4. 修改数据 也要执行node(int index) 找到要修改的节点，然后直接修改此节点的item信息 ####

#### 5. 查询会比ArrayList慢很多了。也是因为执行node(int index) 在数据量大时比较耗时 ####

#### 6. LinkedList也是有序的 ####

## 总结 ArrayList 和 LinkedList 的区别 ##

1.  ArrayList是基于数组实现的，LinkedList是基于链表实现的
2.  在ArrayList中查找和修改数据会比LinkedList中快很多
3.  LinkedList新增数据会比ArrayList快很多
4.  对于删除我觉得两个都是很费时的。ArrayList删除时，是将删除元素之后的数据，复制进原数组从删除元素开始的位置，在将列表最后一个元素设为null。而LinkedList因为不能直接定位到要删除的节点。所以也是比较费时。

### Vector ###

Vector也是一个类似于ArrayList的是的可变长度的数组类型，它的内部也是使用数组来存放数据对象的。  
但不同于ArrayList的是Vector类中的操作集合的方法基本都是synchronized关键字修饰的。也就是线程安全的

public synchronized boolean add(E e) {
            modCount++;
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = e;
            return true;
        }
        public synchronized E set(int index, E element) {
            if (index >= elementCount)
                throw new ArrayIndexOutOfBoundsException(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
        .
        .
        .

### List遍历 ###

List<String> list = new ArrayList<>();
            list.add("sss");
            list.add("ddd");
    
            // 第一种（jdk1.8）
            list.forEach(str -> {
                System.out.println(str);
            });
    
            // 第二种
            for (String s : list) {
                System.out.println(s);
            }
    
            // 第三种
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }