ArrayList和LinkedList的簡單實現(xiàn)

  • ArrayList提供了一宗可增長數(shù)組的實現(xiàn)。有點事對get和set調用花費常數(shù)時間弛饭。缺點是插入和刪除代價昂貴徘公,除非插入和刪除是在ArrayList的末端進行。
  • LinkedList提供了雙鏈表實現(xiàn)军洼。優(yōu)點是,插入和刪除開銷很小演怎,花費常數(shù)時間匕争。缺點是不容易做索引,get和set調用昂貴爷耀,除非調用接近表的斷點的項(離哪端近就從哪端開始)甘桑。

原文地址:http://blog.csdn.net/qq_25806863/article/details/76423425

這兩個集合主要是內部對數(shù)據(jù)的存儲方式不一樣,一個用的數(shù)組,一個用的鏈表跑杭。

數(shù)組和鏈表

關于數(shù)組合鏈表在之前有個簡單的比較

簡單數(shù)組

array list

  • 數(shù)組可以使遍歷以線性時間執(zhí)行O(N)铆帽。
  • 查找是常數(shù)時間O(1)
  • 不過插入和刪除開銷昂貴德谅,如果發(fā)生在第一個元素上爹橱,時間是O(N),如果發(fā)生在最后一個元素上也就是高端,時間是O(1)

當插入和刪除都只對高端操作窄做,數(shù)組也比較合適愧驱,否則就應用 鏈表 linked list

簡單鏈表

使用鏈表是因為鏈表在內存中是不連續(xù)的,不用因為一個元素的插入或刪除而引起其他元素的變動椭盏。

一般鏈表

鏈表由一系列節(jié)點組成组砚,節(jié)點不需要在內存中相連,因此每一個節(jié)點除了自身元素外還要包含自己的后繼元的節(jié)點的鏈(link),稱之為next鏈掏颊。最后一個節(jié)點的next鏈引用null糟红。

  • 遍歷的時間是O(N),跟數(shù)組一樣。
  • 查找的時間乌叶,因為需要從第一個節(jié)點開始查找盆偿,所以時間也是線性的,O(N) 枉昏。要查找第x個元素陈肛,花費的時間是O(x), 效率不如數(shù)組。
  • 刪除可以通過修改next鏈的引用來實現(xiàn)
  • 插入也一樣兄裂,獲取一個新節(jié)點,修改兩個next鏈的引用阳藻,

刪除A2:

刪除一個元素

在A1后插入Ax:

插入

雙鏈表

讓每一個節(jié)點擁有其前驅節(jié)點的引用就成了雙鏈表晰奖。

雙鏈表

ArrayList和LinkedList

  • ArrayList提供了一宗可增長數(shù)組的實現(xiàn)。有點事對get和set調用花費常數(shù)時間腥泥。缺點是插入和刪除代價昂貴匾南,除非插入和刪除是在ArrayList的末端進行。
  • LinkedList提供了雙鏈表實現(xiàn)蛔外。優(yōu)點是蛆楞,插入和刪除開銷很小,花費常數(shù)時間夹厌。缺點是不容易做索引豹爹,get和set調用昂貴,除非調用接近表的斷點的項(離哪端近就從哪端開始)矛纹。

ArrayList的實現(xiàn)

  • 內部使用數(shù)組來保存數(shù)據(jù)臂聋,有一個默認的數(shù)組容量
  • 當容量不夠的時候,擴容一個新數(shù)組,將老數(shù)據(jù)復制到新數(shù)組孩等,釋放舊數(shù)組艾君。
  • 內部類實現(xiàn) MyIterator
  • 增強for循環(huán)的實現(xiàn) implements Iterable<T>
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Consumer;

/**
 * @author sll on 2017/6/30.
 */
public class MyArrayList<Element> implements Iterable<Element> {
    private static final int DEFAULT_CAPACITY = 5;
    private int size;
    private Element[] elements;
    private int modCount = 0;

    public MyArrayList() {
        elements = (Element[]) new Object[DEFAULT_CAPACITY];
        clear();
    }

    public void clear() {
        size = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void trimToSize() {
        ensureCapacity(size);
    }

    //這里是查找,使用數(shù)組直接就查出來了肄方,所以一次查詢的時間是 O(1)
    public Element get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return elements[index];
    }

    public Element set(int index, Element newElement) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        Element old = elements[index];
        elements[index] = newElement;
        return old;
    }

    public boolean add(Element e) {
        return add(size, e);
    }


    //這里的增加和刪除就要移動很多項冰垄,所以一次插入或刪除的速度是 O(N)
    public boolean add(int index, Element e) {
        if (elements.length == size) {
            ensureCapacity(size * 2 + 1);
        }
        System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = e;
        size++;
        modCount++;
        return true;
    }

    public Element remove(int index) {
        Element removeElement = elements[index];
        int moveNum = size - index - 1;
        if (moveNum > 0) {
            System.arraycopy(elements, index + 1, elements, index, moveNum);
        }
        size--;
        elements[size] = null;
        modCount++;
        return removeElement;
    }

    public void ensureCapacity(int newCapacity) {
        if (newCapacity < size)
            return;
        elements = Arrays.copyOf(elements, newCapacity);
    }


    public Itr iterator() {
        return new Itr();
    }


    private class Itr implements Iterator<Element> {
        private int exceptMocCount = modCount;
        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < size();
        }

        @Override
        public Element next() {
            if (exceptMocCount != modCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return elements[current++];
        }

        @Override
        public void remove() {
            if (exceptMocCount != modCount) {
                throw new ConcurrentModificationException();
            }
            MyArrayList.this.remove(--current);
        }

        @Override
        public void forEachRemaining(Consumer<? super Element> action) {

        }
    }
}

LinkedList的實現(xiàn)

  • 使用雙鏈表來實現(xiàn)
  • 節(jié)點類Node,為私有靜態(tài)內部類(嵌套類),包含數(shù)據(jù)和前后節(jié)點的鏈
  • 有兩個額外的節(jié)點权她,頭節(jié)點和尾節(jié)點虹茶,中間才是數(shù)據(jù)
  • 內部實現(xiàn)MyIterator
  • 增強for循環(huán)的實現(xiàn) implements Iterable<E>
  • 對add和remove增加一個計數(shù)modCount,在迭代器的hasNext和next中比較這個計數(shù)伴奥,不同就說明這個集合被修改了写烤,就拋出異常ConcurrentModificationException。
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author sll on 2017/6/30.
 */
public class MyLinkedList<E> implements Iterable<E> {

    private int theSize = 0;
    private int modCount = 0;
    private Node<E> startNode, endNode;//額外的頭節(jié)點和尾節(jié)點

    public MyLinkedList() {
        clear();
    }

    private void clear() {
        startNode = new Node(null, null, null);
        endNode = new Node(null, startNode, null);
        startNode.next = endNode;
        theSize = 0;
        modCount++;
    }

    public int size() {
        return theSize;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean add(E x) {
        return add(size(), x);
    }

    public boolean add(int index, E x) {
        addBefore(getNode(index), x);
        return true;
    }

    public E get(int index) {
        return getNode(index).data;
    }

    public E set(int index, E x) {
        Node<E> p = getNode(index);
        E old = p.data;
        p.data = x;
        return old;
    }

    public E remove(int index) {
        return remove(getNode(index));
    }


    private void addBefore(Node<E> p, E x) {
        Node<E> newNode = new Node<>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;
    }

    private Node<E> getNode(int index) {
        Node<E> p;
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException();
        if (index < size() / 2) {
            p = startNode.next;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        } else {
            p = endNode;
            for (int i = size(); i > index; i--) {
                p = p.prev;
            }
        }

        return p;
    }

    private E remove(Node<E> x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        theSize--;
        modCount++;
        return x.data;
    }

    @Override
    public Iterator<E> iterator() {
        return new MyIterator();
    }

    private static class Node<E> {
        public E data;
        public Node<E> prev;
        public Node<E> next;

        public Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    private class MyIterator implements Iterator<E> {
        private Node<E> current = startNode.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        @Override
        public boolean hasNext() {
            return current!= endNode;
        }

        @Override
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (!okToRemove) {
                throw new NoSuchElementException();
            }
            MyLinkedList.this.remove(current.prev);
            okToRemove = false;
            expectedModCount++;
        }

    }


}

時間對比

以分別用ArrayList和LinkedList用下面三個方法做一個時間對比:

//從末端添加拾徙,創(chuàng)建一個由N個項的List洲炊。
public static void makeList1(List<Integer> list, int N) {
    list.clear();
    for (int i = 0; i < N; i++) {
        list.add(i);
    }
}

//從首端添加,創(chuàng)建一個由N個項的List尼啡。
public static void makeList2(List<Integer> list, int N) {
    list.clear();
    for (int i = 0; i < N; i++) {
        list.add(0, i);
    }
}

//獲取長度為N的List的每一個值求和暂衡。
public static void makeList3(List<Integer> list) {
    long total = 0;
    for (int i = 0; i < list.size(); i++) {
        total += list.get(i);
    }
}

首先創(chuàng)建兩個集合,N=100000崖瞭,打印耗費時間(ms):

List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<Integer>();
  • makeList1

    makeList1(arrayList, 100000);
    makeList1(linkedList, 100000);
    

    結果可能會不一樣狂巢,但也是相近的。

    運行時間都是O(N)

  • makeList2

    makeList2(arrayList, 100000);
    makeList2(linkedList, 100000);
    

    linkedList花費的時間少得多书聚,執(zhí)行時間是O(N)

    而ArrayList因為每次在頭部插入都需要將之前所有項向后移動一位唧领,所以執(zhí)行時間是O(N^2)

  • makeList3

    makeList2(arrayList, 100000);
    makeList2(linkedList, 100000);
    
    makeList3(arrayList);
    makeList3(linkedList);
    

? 這個每次都要查找,所以ArrayList比較快雌续,執(zhí)行時間是O(N)

? 而inkedList的執(zhí)行時間是O(N^2)

  • 用迭代器實現(xiàn)makeList3

    將makeList3改成:

    public static void makeList3(List<Integer> list) {
            long total = 0;
            for (Integer i : list) {
                total+=i;
            }
        }
    

? 兩個都很相近了斩个,都是O(N)。

參考《數(shù)據(jù)結構與算法分析java版》

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末驯杜,一起剝皮案震驚了整個濱河市受啥,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌鸽心,老刑警劉巖滚局,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異顽频,居然都是意外死亡藤肢,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門冲九,熙熙樓的掌柜王于貴愁眉苦臉地迎上來谤草,“玉大人跟束,你說我怎么就攤上這事〕蠛ⅲ” “怎么了冀宴?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長温学。 經(jīng)常有香客問我略贮,道長,這世上最難降的妖魔是什么仗岖? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任逃延,我火速辦了婚禮,結果婚禮上轧拄,老公的妹妹穿的比我還像新娘揽祥。我一直安慰自己,他們只是感情好檩电,可當我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布拄丰。 她就那樣靜靜地躺著,像睡著了一般俐末。 火紅的嫁衣襯著肌膚如雪料按。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天卓箫,我揣著相機與錄音载矿,去河邊找鬼。 笑死烹卒,一個胖子當著我的面吹牛闷盔,可吹牛的內容都是我干的。 我是一名探鬼主播旅急,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼馁筐,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了坠非?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤果正,失蹤者是張志新(化名)和其女友劉穎炎码,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體秋泳,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡潦闲,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了迫皱。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片歉闰。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡辖众,死狀恐怖,靈堂內的尸體忽然破棺而出和敬,到底是詐尸還是另有隱情凹炸,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布昼弟,位于F島的核電站啤它,受9級特大地震影響,放射性物質發(fā)生泄漏舱痘。R本人自食惡果不足惜变骡,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望芭逝。 院中可真熱鬧淆两,春花似錦锐峭、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至逼裆,卻和暖如春蓝仲,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背泡态。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工搂漠, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人某弦。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓桐汤,卻偏偏與公主長得像,于是被迫代替她去往敵國和親靶壮。 傳聞我的和親對象是個殘疾皇子怔毛,可洞房花燭夜當晚...
    茶點故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內容