JavaArrayList与LinkedList使用方法详解

Java ArrayList Java LinkedList 2022-11-13 19:11:39 424人浏览安东尼

Python 官方文档：入门教程 => 点击学习

摘要

目录前言ArrayList和LinkedListList的方法ArrayListaddremoveLinkedListremoveget和peekpushArrayList和Link

前言

最近参加了21天打卡活动，希望可以让自己养成写博客的习惯…

ArrayList和LinkedList

ArrayList和LinkedList都是常用的List类型，两者都继承了AbstratctList，并实现List接口。

List的方法

列举一些常见的方法，ArrayList和LinkedList会实现List里面的方法

方法	描述
boolean isEmpty()	判断当前列表是否为空
boolean contains(Object o)	是否包含这个元素
T[] toArray(T[] a)
boolean add(E e)	添加一个元素
boolean remove(Object o)	移除
boolean containsAll(Collection<?> c)
void add(int index, E element)	在固定位置添加元素
int indexOf(Object o)	定位元素
ListIterator listIterator()	遍历列表

上述的方法都是List的常用方法，相信大家都非常的熟悉。

ArrayList

ArrayList是实现List接口的可扩容数组（动态数组），它的内部是基于数组实现的，数组这个结构具有的特点

随机存取：随机存取就是可以通过索引直接访问列表的元素

可以实现动态扩容，下面我们来看一下它的源码实现

属性	描述
size	列表的元素个数
DEFAULT_CAPACITY	创建一个空对象时的默认大小

我们来看一下ArrayList是怎么实现动态扩容的。

 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);
    }

如果当容量比初始容量大时，新的容量相当于是原来的1.5倍这里

add

ArrayList重载了List的add方法，这里面重写的方法有直接添加，和在某一个位置添加一个元素，这里就可以看出ArrayList的底层是由数组实现的了

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++;
    }

这里采用的是System.arraycopy来进行数组的拷贝，属于深度拷贝，效率很高。

remove

这里的移除也是有直接移除某个索引下的数据，但是这里面有两个不同的方式移除数据，一个是remove，一个是fastRemove两种方式移除元素，remove和fastRemove不同的是一个是需要返回删除的元素，一个是不返回的。

LinkedList

LinkedList是基于双向链表来实现的，是属于链式存储，只能顺序存取元素，不能随机存取。

LinkedList的结点结构，包括指向下一个结点的指针next和指向上一个结点的指针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;
        }
    }

属性包括

名称	描述
size	元素个数
first	头节点
last	尾节点

remove

移除头节点，需要更新size大小和把删除的节点为NULL，里面还有removeRange方法，可以把从fromIndex到toIndex的全部节点释放掉

 public E remove() {
        return removeFirst();
 }
 private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

get和peek

下面可以来看看LinkedList的访问元素的形式，前面说了这个结构是只能顺序遍历的，不能随机进行访问，需要遍历整个列表，但是我们使用的是双向链表，由于我们维护了头节点和尾节点，当需要访问元素时，如果根据的是下标（这里的下标不是数组的下标），先判断和头节点近还是和尾节点近，然后再进行顺序遍历。

peek方法是访问头节点。

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;
        }
    }