List

有序集合泊愧，可以精確控制列表中每個(gè)元素的插入位置伊磺。通過整數(shù)索引獲取列表中的元素。List允許出現(xiàn)重復(fù)的值 删咱， 并可以精確控制列表中每個(gè)元素的插入位置屑埋，通過整數(shù)索引獲取列表中的元素。

ArrayList

ArrayList 是List 接口的大小可變數(shù)組的實(shí)現(xiàn)痰滋。實(shí)現(xiàn)了所有可選列表操作摘能， 并允許包括null 在內(nèi)的所有元素续崖。除了實(shí)現(xiàn)List 接口外， 此類還提供一些方法來操作內(nèi)部用來存儲(chǔ)列表的數(shù)組的大型鸥恪（ 此類大致上等同于 vector 類严望， 但 vector 是同步的） 。

ArrayList 的底層是使用數(shù)組實(shí)現(xiàn)的逻恐，看下面的圖

image-20200212171434134.png

可以看到像吻，數(shù)組中的每一個(gè)元素，都存儲(chǔ)在內(nèi)存單元中复隆，并且元素之間緊密排列萧豆，既不能打亂元素的存儲(chǔ)順序，也不能跳過某個(gè)存儲(chǔ)單元進(jìn)行存儲(chǔ)昏名。

ArrayList 底層既然是使用數(shù)組實(shí)現(xiàn)涮雷，那么特點(diǎn)就和數(shù)組一致：查詢速度快，增刪速度慢轻局。

每個(gè)ArrayList 實(shí)例都有一個(gè)容量洪鸭。該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小， 它總是至少等于列表的大小仑扑。隨著向Array L ist 中小斷添加元素览爵， 其容量也自動(dòng)增長。并未指定增長策略的細(xì)節(jié)镇饮，因?yàn)檫@不只是添加元素會(huì)帶來分?jǐn)偣潭〞r(shí)間開銷那樣簡單蜓竹。我們可以使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建容量為 10 的列表， 也可以初始化指定容量大小储藐。

ArrayList 指定初始容量大小的構(gòu)造器方法

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}

常用的操作

public static void main(String[] args) {

    ArrayList<Integer> list = new ArrayList<>();

    //  添加數(shù)據(jù)
    list.add(123);
    list.add(346);

    //  替換數(shù)據(jù)
    list.set(1, 777);

    //  將list中的所有數(shù)據(jù)放到 list2 中
    List<Integer> list2 = new ArrayList<>();
    list2.addAll( list );

    //  循環(huán)list2中所有的數(shù)據(jù)
    for (Integer integer : list2) {

        System.out.println( integer );

        //  刪除循環(huán)出的對(duì)象
        list2.remove(integer);
    }

    //  list 集合是否有數(shù)據(jù)
    if( !list.isEmpty() ) {

        System.out.println("list.size = "+ list.size());

        //  清空 list
        list.clear();
    }

    //  在清空list后俱济，再看list現(xiàn)在有多少數(shù)據(jù)
    System.out.println("list.size = "+ list.size());
}

LinkedList

LinkedList 是一個(gè)鏈表結(jié)構(gòu)，可當(dāng)作堆棧钙勃、隊(duì)列蛛碌、雙端隊(duì)列 。鏈表是一種在物理上非連續(xù)辖源、非順序的數(shù)據(jù)結(jié)構(gòu)蔚携，由若干節(jié)點(diǎn)（node）所組成。

單鏈表

image-20200212173413313.png

單向鏈表的每一個(gè)節(jié)點(diǎn)包含兩部分克饶，一部分是存放數(shù)據(jù)的變量data酝蜒，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針next。正如地下黨的聯(lián)絡(luò)方式矾湃，一級(jí)一級(jí)亡脑，單線傳遞：

private static class Node {
    int data;
    Node next;
}

雙鏈表

雙向鏈表比單向鏈表稍微復(fù)雜一些，它的每一個(gè)節(jié)點(diǎn)除了擁有data和next指針，還擁有指向前置節(jié)點(diǎn)的prev指針

image-20200212173517719.png

和數(shù)組不同远豺，鏈表存儲(chǔ)數(shù)據(jù)的時(shí)候奈偏，則采用了見縫插針的方式，鏈表的每一個(gè)節(jié)點(diǎn)分布在內(nèi)存的不同位置躯护，依靠next指針關(guān)聯(lián)起來惊来。這樣可以靈活有效地利用零散的碎片空間。

image-20200212173548104.png

LinkedList 做數(shù)據(jù)的添加和刪除操作時(shí)速度很快棺滞，但是做查詢的時(shí)候速度就很慢裁蚁，這和 ArrayList 剛好相反。

適用 LinkedList 獨(dú)有的方法继准，在集合前后做數(shù)據(jù)插入

public static void main(String[] args) {

    LinkedList<Integer> list = new LinkedList<>();

    list.add(123);
    //  添加相同的數(shù)據(jù)
    list.add(123);
    list.add(456);
    list.add(789);
    list.add(101);

    //  將數(shù)據(jù) 111 添加到 list 的末尾
    list.addLast(111);
    //  將數(shù)據(jù) 999 添加到 list的最前面
    list.addFirst(999);

    for (int i = 0; i < list.size(); i++) {
        System.out.println( list.get(i) );
    }

}

注意代碼中聲明和實(shí)現(xiàn)都是 LinkedList 枉证， 如果聲明的是 List 接口 ， addFirst 和 addLast 方法是不可見的