快捷導(dǎo)航

Java ArrayList與LinkedList使用方法詳解

更新時(shí)間：2022年11月08日 16:33:42 作者：宏遠(yuǎn)十一冠王

Java中容器對(duì)象主要用來(lái)存儲(chǔ)其他對(duì)象，根據(jù)實(shí)現(xiàn)原理不同，主要有3類常用的容器對(duì)象：ArrayList使用數(shù)組結(jié)構(gòu)存儲(chǔ)容器中的元素、LinkedList使用鏈表結(jié)構(gòu)存儲(chǔ)容器中的元素

前言

最近參加了21天打卡活動(dòng)，希望可以讓自己養(yǎng)成寫博客的習(xí)慣…

ArrayList和LinkedList

ArrayList和LinkedList都是常用的List類型，兩者都繼承了AbstratctList，并實(shí)現(xiàn)List接口。

List的方法

列舉一些常見(jiàn)的方法，ArrayList和LinkedList會(huì)實(shí)現(xiàn)List里面的方法

方法	描述
boolean isEmpty()	判斷當(dāng)前列表是否為空
boolean contains(Object o)	是否包含這個(gè)元素
T[] toArray(T[] a)
boolean add(E e)	添加一個(gè)元素
boolean remove(Object o)	移除
boolean containsAll(Collection<?> c)
void add(int index, E element)	在固定位置添加元素
int indexOf(Object o)	定位元素
ListIterator listIterator()	遍歷列表

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

ArrayList

ArrayList是實(shí)現(xiàn)List接口的可擴(kuò)容數(shù)組（動(dòng)態(tài)數(shù)組），它的內(nèi)部是基于數(shù)組實(shí)現(xiàn)的，數(shù)組這個(gè)結(jié)構(gòu)具有的特點(diǎn)

隨機(jī)存?。弘S機(jī)存取就是可以通過(guò)索引直接訪問(wèn)列表的元素

可以實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容，下面我們來(lái)看一下它的源碼實(shí)現(xiàn)

屬性	描述
size	列表的元素個(gè)數(shù)
DEFAULT_CAPACITY	創(chuàng)建一個(gè)空對(duì)象時(shí)的默認(rèn)大小

我們來(lái)看一下ArrayList是怎么實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的。

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

如果當(dāng)容量比初始容量大時(shí)，新的容量相當(dāng)于是原來(lái)的1.5倍這里

add

ArrayList重載了List的add方法，這里面重寫的方法有直接添加，和在某一個(gè)位置添加一個(gè)元素，這里就可以看出ArrayList的底層是由數(shù)組實(shí)現(xiàn)的了

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來(lái)進(jìn)行數(shù)組的拷貝，屬于深度拷貝，效率很高。

remove

這里的移除也是有直接移除某個(gè)索引下的數(shù)據(jù)，但是這里面有兩個(gè)不同的方式移除數(shù)據(jù)，一個(gè)是remove，一個(gè)是fastRemove兩種方式移除元素，remove和fastRemove不同的是一個(gè)是需要返回刪除的元素，一個(gè)是不返回的。

LinkedList

LinkedList是基于雙向鏈表來(lái)實(shí)現(xiàn)的，是屬于鏈?zhǔn)酱鎯?chǔ)，只能順序存取元素，不能隨機(jī)存取。

LinkedList的結(jié)點(diǎn)結(jié)構(gòu)，包括指向下一個(gè)結(jié)點(diǎn)的指針next和指向上一個(gè)結(jié)點(diǎn)的指針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	元素個(gè)數(shù)
first	頭節(jié)點(diǎn)
last	尾節(jié)點(diǎn)

remove

移除頭節(jié)點(diǎn)，需要更新size大小和把刪除的節(jié)點(diǎn)為NULL，里面還有removeRange方法，可以把從fromIndex到toIndex的全部節(jié)點(diǎn)釋放掉

 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

下面可以來(lái)看看LinkedList的訪問(wèn)元素的形式，前面說(shuō)了這個(gè)結(jié)構(gòu)是只能順序遍歷的，不能隨機(jī)進(jìn)行訪問(wèn)，需要遍歷整個(gè)列表，但是我們使用的是雙向鏈表，由于我們維護(hù)了頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，當(dāng)需要訪問(wèn)元素時(shí)，如果根據(jù)的是下標(biāo)（這里的下標(biāo)不是數(shù)組的下標(biāo)），先判斷和頭節(jié)點(diǎn)近還是和尾節(jié)點(diǎn)近，然后再進(jìn)行順序遍歷。

peek方法是訪問(wèn)頭節(jié)點(diǎn)。

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

push

向列表中添加元素，我們可以采用offerFirst和offerLast往列表頭部添加元素或者往尾部添加元素，push方法調(diào)用的是addFrist方法，采用的是頭插法，刪除也是才有刪除頭部元素；

ArrayList和LinkedList的使用場(chǎng)景和區(qū)別

前面也提到兩者的存取結(jié)構(gòu)是不同的，一個(gè)是用數(shù)組來(lái)操作，一個(gè)采用的是雙向鏈表，一般ArrayList用在訪問(wèn)更加多的情況下，由于插入會(huì)相對(duì)較慢，但是LinkedList采用的是順序訪問(wèn)，在插入和刪除較多的場(chǎng)景會(huì)更加適用。

到此這篇關(guān)于Java ArrayList與LinkedList使用方法詳解的文章就介紹到這了,更多相關(guān)Java ArrayList與LinkedList內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: