數(shù)組
什么是數(shù)組？
數(shù)組簡(jiǎn)單來(lái)說(shuō)就是將所有的數(shù)據(jù)排成一排存放在系統(tǒng)分配的一個(gè)內(nèi)存塊上，通過(guò)使用特定元素的索引作為數(shù)組的下標(biāo)，可以在常數(shù)時(shí)間內(nèi)訪問(wèn)數(shù)組元素的這么一個(gè)結(jié)構(gòu)；

image.png

為什么能在常數(shù)時(shí)間內(nèi)訪問(wèn)數(shù)組元素？
為了訪問(wèn)一個(gè)數(shù)組元素，該元素的內(nèi)存地址需要計(jì)算其距離數(shù)組基地址的偏移量。需要用一個(gè)乘法計(jì)算偏移量，再加上基地址，就可以獲得某個(gè)元素的內(nèi)存地址。首先計(jì)算元素?cái)?shù)據(jù)類型的存儲(chǔ)大小，然后將它乘以元素在數(shù)組中的索引，最后加上基地址，就可以計(jì)算出該索引位置元素的地址了；整個(gè)過(guò)程可以看到需要一次乘法和一次加法就完成了，而這兩個(gè)運(yùn)算的執(zhí)行時(shí)間都是常數(shù)時(shí)間，所以可以認(rèn)為數(shù)組訪問(wèn)操作能在常數(shù)時(shí)間內(nèi)完成；

數(shù)組的優(yōu)點(diǎn)
簡(jiǎn)單且易用；
訪問(wèn)元素快（常數(shù)時(shí)間）；

數(shù)組的缺點(diǎn)
大小固定：數(shù)組的大小是靜態(tài)的（在使用前必須制定數(shù)組的大?。?br> 分配一個(gè)連續(xù)空間塊：數(shù)組初始分配空間時(shí)，有時(shí)候無(wú)法分配能存儲(chǔ)整個(gè)數(shù)組的內(nèi)存空間（當(dāng)數(shù)組規(guī)模太大時(shí)）；
基于位置的插入操作實(shí)現(xiàn)復(fù)雜：如果要在數(shù)組中的給定位置插入元素，那么可能就會(huì)需要移動(dòng)存儲(chǔ)在數(shù)組中的其他元素，這樣才能騰出指定的位置來(lái)放插入的新元素；而如果在數(shù)組的開(kāi)始位置插入元素，那么這樣的移動(dòng)操作開(kāi)銷就會(huì)很大。

關(guān)于數(shù)組的一些問(wèn)題思考
1）在索引沒(méi)有語(yǔ)義的情況下如何表示沒(méi)有的元素？

我們創(chuàng)建的數(shù)組的索引可以有語(yǔ)義也可以沒(méi)有語(yǔ)義，比如我現(xiàn)在只是單純的想存放100，98，96這三個(gè)數(shù)字，那么它們保存在索引為0，1，2的這幾個(gè)地方或者其他地方都可以，無(wú)論它們之間的順序怎樣我都不關(guān)心，因?yàn)樗鼈兊乃饕菦](méi)有語(yǔ)義的我只是想把它們存起來(lái)而已；但是如果它們變成了學(xué)號(hào)為1，2，3這幾個(gè)同學(xué)對(duì)應(yīng)的成績(jī)，那么它們的索引就有了語(yǔ)義，索引0對(duì)應(yīng)了學(xué)號(hào)為1的同學(xué)的成績(jī)，索引1對(duì)應(yīng)了學(xué)號(hào)2的同學(xué)，索引2對(duì)應(yīng)了學(xué)號(hào)3的同學(xué)，因?yàn)閿?shù)組的最大的優(yōu)點(diǎn)是訪問(wèn)元素是在常數(shù)時(shí)間，所以我們使用數(shù)組最好就是在索引有語(yǔ)義的情況下；

image.png

好了，那么如果在索引沒(méi)有語(yǔ)義的情況下，我們?nèi)绾伪硎緵](méi)有的元素呢？例如上圖中，對(duì)于用戶而言，訪問(wèn)索引為3和4的數(shù)組元素是違法的，因?yàn)樗鼈兏揪筒淮嬖冢覀內(nèi)绾伪硎緵](méi)有的元素呢？

表示為0或者-1？

2）如何添加元素和刪除元素呢？
我們知道，數(shù)組的明顯缺點(diǎn)是在創(chuàng)建之前需要提前聲明好要使用的空間，那么當(dāng)我們空間滿了該如何處理呢？又該如何刪除元素呢？在Java中提供給我們的默認(rèn)數(shù)組是不支持這些功能的，我們需要開(kāi)發(fā)屬于自己的數(shù)組類才行；

使用泛型封裝自己的數(shù)組類

我們需要自己創(chuàng)建一個(gè)Array類，并實(shí)現(xiàn)一些增刪改查的功能，大體的結(jié)構(gòu)如下：
private E[] data;
/**
* 有效元素的個(gè)數(shù)
*/
private int size;

我們需要一個(gè)成員變量來(lái)保存我們的數(shù)據(jù)，這里是data，然后需要一個(gè)int類型來(lái)存放我們的有效元素的個(gè)數(shù)，在這里我們沒(méi)有必要再多定義一個(gè)表示數(shù)組空間的變量，因?yàn)檫@里的空間大小就是data.length；

默認(rèn)的構(gòu)造函數(shù)

我們需要?jiǎng)?chuàng)建一些方法來(lái)初始化我們的數(shù)組，那肯定是需要傳一個(gè)capacity來(lái)表示數(shù)組的容量嘛：
/**
* 構(gòu)造函數(shù)，傳入數(shù)組的容量capacity構(gòu)造Array
* @param capacity 初始化的大小
*/
public ZyhArray(int capacity){
data = (E[]) new Object[capacity];
}

當(dāng)然我們也需要?jiǎng)?chuàng)建一個(gè)默認(rèn)的構(gòu)造函數(shù)來(lái)為不知道初始該定義多少的用戶一個(gè)默認(rèn)大小的數(shù)組：
public ZyhArray(){
this(10);
}

這里演示的話給個(gè)10差不多了，實(shí)際可能會(huì)更復(fù)雜一些...

成員方法

就是增刪改查嘛，不過(guò)這里需要注意的是，為了實(shí)現(xiàn)我們自己的動(dòng)態(tài)數(shù)組，在增加和刪除中，我們對(duì)臨界值進(jìn)行了判斷，動(dòng)態(tài)的增加或者縮小數(shù)組的大小，而且提供了一些常用友好的方法給用戶；

/**
* 獲取數(shù)組的容量
*/

public int getCapacity() {
    return data.length;
}



/**
 * 獲取數(shù)組中的元素個(gè)數(shù)
 * @return
 */
public int getSize() {
    return size;
}


/**
 * 返回?cái)?shù)組是否為空
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}


/**
 * 在index索引的位置插入一個(gè)新元素e
 * @param index
 * @param e
 */
public void add(int index, E e) {

    if (index < 0 || index > size){
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
    }

    if (size == data.length){
        resize(2 * data.length);
    }

    for (int i = size - 1; i >= index; i--){
        data[i + 1] = data[i];
    }
    data[index] = e;
    size++;


}


/**
 * 向所有元素后添加一個(gè)新元素
 * @param e
 */
public void addLast(E e) {
    add(size, e);
}


/**
 * 在所有元素前添加一個(gè)新元素
 * @param e
 */
public void addFirst(E e) {
    add(0, e);
}


/**
 * 獲取index索引位置的元素
 * @param index
 * @return
 */
public E get(int index) {
    if (index < 0 || index >= size){
        throw new IllegalArgumentException("Get failed. Index is illegal.");
    }
    return data[index];
}


/**
 * 修改index索引位置的元素為e
 * @param index
 * @param e
 */
public void set(int index, E e) {
    if (index < 0 || index >= size){
        throw new IllegalArgumentException("Set failed. Index is illegal.");
    }
    data[index] = e;
}


/**
 * 查找數(shù)組中是否有元素e
 * @param e
 * @return
 */
public boolean contains(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e)){
            return true;
        }
    }
    return false;
}


/**
 * 查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1
 * @param e
 * @return
 */
public int find(E e) {
    for (int i = 0; i < size; i++) {
        if (data[i].equals(e)){
            return i;
        }
    }
    return -1;
}


/**
 * 從數(shù)組中刪除index位置的元素, 返回刪除的元素
 *  這是為了防止復(fù)雜度抖動(dòng)和安全性
 * @param index
 * @return
 */
public E remove(int index) {
    if (index < 0 || index >= size){
        throw new IllegalArgumentException("Remove failed. Index is illegal.");
    }

    E ret = data[index];
    for (int i = index + 1; i < size; i++){
        data[i - 1] = data[i];
    }
    size--;
    data[size] = null; // loitering objects != memory leak

    if (size == data.length / 4 && data.length / 2 != 0){
        resize(data.length / 2);
    }
    return ret;
}


/**
 * 從數(shù)組中刪除第一個(gè)元素, 返回刪除的元素
 * @return
 */
public E removeFirst() {
    return remove(0);
}


/**
 * 從數(shù)組中刪除最后一個(gè)元素, 返回刪除的元素
 * @return
 */
public E removeLast() {
    return remove(size - 1);
}


/**
 * 從數(shù)組中刪除元素e
 * @param e
 */
public void removeElement(E e) {
    int index = find(e);
    if (index != -1){
        remove(index);
    }
}

@Override
public String toString() {

    StringBuilder res = new StringBuilder();
    res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
    res.append('[');
    for (int i = 0; i < size; i++) {
        res.append(data[i]);
        if (i != size - 1){
            res.append(", ");
        }
    }
    res.append(']');
    return res.toString();
}


/**
 * 將數(shù)組空間的容量變成newCapacity大小
 * @param newCapacity
 */
private void resize(int newCapacity) {

    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++){
        newData[i] = data[i];
    }
    data = newData;
}

注意：為了更好的展示代碼而不太浪費(fèi)空間，所以這里使用//的風(fēng)格來(lái)注釋代碼；
特別注意：在remove方法中，縮小數(shù)組的判斷條件為size == data.length / 4 && data.length / 2 != 0，這是為了防止復(fù)雜度抖動(dòng)和安全性；

注意：這里需要注意復(fù)雜度抖動(dòng)

簡(jiǎn)單時(shí)間復(fù)雜度分析

添加操作

在添加操作中，我們可以明顯看到，addLast()方法是與n無(wú)關(guān)的，所以為O(1)復(fù)雜度；而addFirst()和add()方法都涉及到挪動(dòng)數(shù)組元素，所以都是O(n)復(fù)雜度，包括resize()方法；綜合起來(lái)添加操作的復(fù)雜度就是O(n)；

image.png

刪除操作
在刪除操作中，與添加操作同理，綜合來(lái)看刪除操作的復(fù)雜度就是O(n)；

image.png

image.png

查詢操作
在查詢操作中，如果我們已知索引，那么復(fù)雜度為O(1)；如果未知索引，我們需要遍歷整個(gè)數(shù)組，那么復(fù)雜度為O(n)級(jí)別；

image.png

總結(jié)

以上我們簡(jiǎn)單分析了我們自己創(chuàng)建的數(shù)組類的復(fù)雜度：

增加：O(n)；
刪除：O(n)；
修改：已知索引 O(1)；未知索引 O(n)；
查詢：已知索引 O(1)；未知索引 O(n)；

均攤復(fù)雜度
如果細(xì)心的同學(xué)應(yīng)該可以注意到，在增加和刪除的復(fù)雜度分析中，如果我們都只是對(duì)最后一個(gè)元素進(jìn)行相應(yīng)的操作的話，那么對(duì)應(yīng)的O(n)的復(fù)雜度顯然是不合理的，我們之所以將他們的復(fù)雜度定義為O(n)，就是因?yàn)樵谖覀兺ǔ５膹?fù)雜度分析中我們需要考慮最壞的情況，也就是對(duì)應(yīng)的需要使用resize()方法擴(kuò)容的情況，但是這樣的情況并不是每一次都出現(xiàn)，所以我們需要更加合理的來(lái)分析我們的復(fù)雜度，這里提出的概念就是：均攤復(fù)雜度；

image.png

假設(shè)我們現(xiàn)在的capacity為5，并且每一次的添加操作都使用addLast()方法，那么我們?cè)谑褂昧宋宕蝍ddLast()方法之后就會(huì)觸發(fā)一次resize()方法，在前五次的addLast()方法中我們總共進(jìn)行了五次基本操作，也就是給數(shù)組的末尾添加上一個(gè)元素，在進(jìn)行第六次addLast()方法的時(shí)候，觸發(fā)resize()方法，就需要進(jìn)行一次元素的轉(zhuǎn)移，共5次操作（轉(zhuǎn)移五個(gè)元素嘛），然后再在末尾加上一個(gè)元素，也就是總共進(jìn)行了11次操作；

也就是說(shuō)：6次addLast()操作，觸發(fā)resize()方法，總共進(jìn)行了11次操作，平均下來(lái)，每次addLast()操作，進(jìn)行了2次基本操作（約等于）；那么依照上面的假設(shè)我們可以進(jìn)一步推廣為：假設(shè)capacity為n，n+1次addLast()操作，觸發(fā)resize()方法，總共進(jìn)行了2n+1次基本操作，平均來(lái)講，每次addLast()操作，進(jìn)行了2次基本操作，這樣也就意味著，均攤下來(lái)的addLast()方法的復(fù)雜度為O(1)，而不是之前分析的O(n)，這樣的均攤復(fù)雜度顯然比最壞復(fù)雜度來(lái)得更有意義，因?yàn)椴皇敲恳淮蔚牟僮鞫际亲顗牡那闆r！

同理，我們看removeLast()對(duì)應(yīng)的均攤復(fù)雜度也為O(1)；

復(fù)雜度震蕩
在我們的remove方法中，我們判斷縮小容量的條件為size == data.length / 4 && data.length / 2 != 0，這樣是為了防止復(fù)雜度震蕩和安全性（因?yàn)榭s小到一定的時(shí)候容量可能為1），這又是怎么一回事呢？我們考慮一下將條件改為size == data.length / 2的時(shí)候，出現(xiàn)的如下圖這樣的情況：

image.png

當(dāng)我們數(shù)組已經(jīng)滿元素的情況下，使用一次addLast方法，因?yàn)橛|發(fā)resize，數(shù)組容量擴(kuò)容為當(dāng)前的兩倍，所以此時(shí)復(fù)雜度為O(n)；這時(shí)候我們立即使用removeLast，因?yàn)榇藭r(shí)的容量等于n/2，所以會(huì)馬上產(chǎn)生縮小容量的操作，此時(shí)復(fù)雜度為O(n)；我們之前明明通過(guò)均攤復(fù)雜度分析出我們的兩個(gè)操作都為O(1)，而此時(shí)卻產(chǎn)生了震蕩，為了避免這樣的操作，我們需要懶操作一下，也就是在remove的時(shí)候不要立即縮容，而是等到size == capacity / 4的時(shí)候再縮小一半，這樣就有效的解決了復(fù)雜度震蕩的問(wèn)題；

Java中的ArrayList的擴(kuò)容

上面我們已經(jīng)實(shí)現(xiàn)了自己的數(shù)組類，我們也順便看看Java中的ArrayList是怎么寫的，其他的方法可以自己去看看，這里提出來(lái)一個(gè)grow()的方法，來(lái)看看ArrayList是怎么實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的：

image.png

鏈表
什么是鏈表
鏈表是一種用于存儲(chǔ)數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)，它是最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們?cè)谏厦骐m然實(shí)現(xiàn)了動(dòng)態(tài)數(shù)組，但這僅僅是對(duì)于用戶而言，其實(shí)底層還是維護(hù)的一個(gè)靜態(tài)的數(shù)組，它之所以是動(dòng)態(tài)的是因?yàn)槲覀冊(cè)赼dd和remove的時(shí)候進(jìn)行了相應(yīng)判斷動(dòng)態(tài)擴(kuò)容或縮容而已，而鏈表則是真正意義上動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)；

image.png

鏈表的優(yōu)點(diǎn)
真正的動(dòng)態(tài)，不需要處理固定容量的問(wèn)題；
能夠在常數(shù)時(shí)間內(nèi)擴(kuò)展容量；
對(duì)比我們的數(shù)組，當(dāng)創(chuàng)建數(shù)組時(shí)，我們必須分配能存儲(chǔ)一定數(shù)量元素的內(nèi)存，如果向數(shù)組中添加更多的元素，那么必須創(chuàng)建一個(gè)新的數(shù)組，然后把原數(shù)組中的元素復(fù)制到新數(shù)組中去，這將花費(fèi)大量的時(shí)間；當(dāng)然也可以通過(guò)給數(shù)組預(yù)先設(shè)定一個(gè)足夠大的空間來(lái)防止上述時(shí)間的發(fā)生，但是這個(gè)方法可能會(huì)因?yàn)榉峙涑^(guò)用戶需要的空間而造成很大的內(nèi)存浪費(fèi)；而對(duì)于鏈表，初始時(shí)僅需要分配一個(gè)元素的存儲(chǔ)空間，并且添加新的元素也很容易，不需要做任何內(nèi)存復(fù)制和重新分配的操作；

鏈表的缺點(diǎn)
喪失了隨機(jī)訪問(wèn)的能力；
鏈表中的額外指針引用需要浪費(fèi)內(nèi)存；
鏈表有許多不足。鏈表的主要缺點(diǎn)在于訪問(wèn)單個(gè)元素的時(shí)間開(kāi)銷問(wèn)題；數(shù)組是隨時(shí)存取的，即存取數(shù)組中任一元素的時(shí)間開(kāi)銷為O(1)，而鏈表在最差情況下訪問(wèn)一個(gè)元素的開(kāi)銷為O(n)；數(shù)組在存取時(shí)間方面的另一個(gè)優(yōu)點(diǎn)是內(nèi)存的空間局部性，由于數(shù)組定義為連續(xù)的內(nèi)存塊，所以任何數(shù)組元素與其鄰居是物理相鄰的，這極大得益于現(xiàn)代CPU的緩存模式；

鏈表和數(shù)組的簡(jiǎn)單對(duì)比
數(shù)組最好用于索引有語(yǔ)意的情況，最大的優(yōu)點(diǎn)：支持快速查詢；
鏈表不適用于索引有語(yǔ)意的情況，最大的優(yōu)點(diǎn)：動(dòng)態(tài)；

實(shí)現(xiàn)自己的鏈表類

public class ZyhLinkedList<E> {
private class Node {
public E e;
public Node next;

    public Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }

    public Node(E e) {
        this(e, null);
    }

    public Node() {
        this(null, null);
    }

    @Override
    public String toString() {
        return e.toString();
    }
}

private Node dummyHead;
private int size;

public ZyhLinkedList() {
    dummyHead = new Node();
    size = 0;
}

// 獲取鏈表中的元素個(gè)數(shù)
public int getSize() {
    return size;
}

// 返回鏈表是否為空
public boolean isEmpty() {
    return size == 0;
}

// 在鏈表的index(0-based)位置添加新的元素e
// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）
public void add(int index, E e) {

    if (index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Illegal index.");

    Node prev = dummyHead;
    for (int i = 0; i < index; i++)
        prev = prev.next;

    prev.next = new Node(e, prev.next);
    size++;
}

// 在鏈表頭添加新的元素e
public void addFirst(E e) {
    add(0, e);
}

// 在鏈表末尾添加新的元素e
public void addLast(E e) {
    add(size, e);
}

// 獲得鏈表的第index(0-based)個(gè)位置的元素
// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）
public E get(int index) {

    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get failed. Illegal index.");

    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++)
        cur = cur.next;
    return cur.e;
}

// 獲得鏈表的第一個(gè)元素
public E getFirst() {
    return get(0);
}

// 獲得鏈表的最后一個(gè)元素
public E getLast() {
    return get(size - 1);
}

// 修改鏈表的第index(0-based)個(gè)位置的元素為e
// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）
public void set(int index, E e) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Update failed. Illegal index.");

    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++)
        cur = cur.next;
    cur.e = e;
}

// 查找鏈表中是否有元素e
public boolean contains(E e) {
    Node cur = dummyHead.next;
    while (cur != null) {
        if (cur.e.equals(e))
            return true;
        cur = cur.next;
    }
    return false;
}

// 從鏈表中刪除index(0-based)位置的元素, 返回刪除的元素
// 在鏈表中不是一個(gè)常用的操作，練習(xí)用：）
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    // E ret = findNode(index).e; // 兩次遍歷

    Node prev = dummyHead;
    for (int i = 0; i < index; i++)
        prev = prev.next;

    Node retNode = prev.next;
    prev.next = retNode.next;
    retNode.next = null;
    size--;

    return retNode.e;
}

// 從鏈表中刪除第一個(gè)元素, 返回刪除的元素
public E removeFirst() {
    return remove(0);
}

// 從鏈表中刪除最后一個(gè)元素, 返回刪除的元素
public E removeLast() {
    return remove(size - 1);
}

// 從鏈表中刪除元素e
public void removeElement(E e) {

    Node prev = dummyHead;
    while (prev.next != null) {
        if (prev.next.e.equals(e))
            break;
        prev = prev.next;
    }

    if (prev.next != null) {
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
    }
}

@Override
public String toString() {
    StringBuilder res = new StringBuilder();

    Node cur = dummyHead.next;
    while (cur != null) {
        res.append(cur + "->");
        cur = cur.next;
    }
    res.append("NULL");

    return res.toString();
}

}

鏈表虛擬頭結(jié)點(diǎn)的作用
為了屏蔽掉鏈表頭結(jié)點(diǎn)的特殊性；
因?yàn)轭^結(jié)點(diǎn)是沒(méi)有前序結(jié)點(diǎn)的，所以我們不管是刪除還是增加操作都要對(duì)頭結(jié)點(diǎn)進(jìn)行單獨(dú)的判斷，為了我們編寫邏輯的方便，引入了一個(gè)虛擬頭結(jié)點(diǎn)的概念；
簡(jiǎn)單復(fù)雜度分析
我們從鏈表的操作中可以很容易的看出，對(duì)于增刪改查這幾個(gè)操作的復(fù)雜度都是O(n)的，但是如果我們只是對(duì)鏈表頭進(jìn)行增/刪/查的操作的話，那么它的復(fù)雜度就是O(1)的，這里也可以看出來(lái)我們的鏈表適合干的事情了..

轉(zhuǎn)自
作者：我沒(méi)有三顆心臟
鏈接：http://www.itdecent.cn/p/7b93b3570875
來(lái)源：簡(jiǎn)書