總覽數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

• 線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有序序列
• 隊(duì)列：只允許在一端插入，而在另一端進(jìn)行刪除操作的線性表
• 堆棧：棧是限定僅在表尾進(jìn)行插入刪除操作的線性表
• 樹：樹是n個(gè)節(jié)點(diǎn)的有序集。節(jié)點(diǎn)可以像樹一樣越向葉子節(jié)點(diǎn)就沒有交集
• 圖論：由頂點(diǎn)的有窮空集合和頂點(diǎn)之間邊的集合組成
• 排序和查找算法：排序是對(duì)數(shù)據(jù)進(jìn)行順序排列，查找是在大量數(shù)據(jù)中尋找我們需要的數(shù)據(jù)的過(guò)程

什么是數(shù)據(jù)結(jié)構(gòu)？

• 數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)組成
• 數(shù)據(jù)對(duì)象：有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集
• 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合

邏輯結(jié)構(gòu)與物理結(jié)構(gòu)##

邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的相互關(guān)系

1. 集合結(jié)構(gòu)
2. 線性結(jié)構(gòu)
3. 樹形結(jié)構(gòu)
4. 圖形結(jié)構(gòu)

image

image

image

image

物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)

1. 順序存儲(chǔ)結(jié)構(gòu)

image

1. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

image

數(shù)組

1. 簡(jiǎn)單：數(shù)組是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)
2. 占據(jù)連續(xù)內(nèi)存：數(shù)據(jù)空間連續(xù)，按照申請(qǐng)的順序存儲(chǔ)，但是必須指定數(shù)組大小
3. 數(shù)組空間效率低：數(shù)組中經(jīng)常有空閑的區(qū)域沒有得到充分的應(yīng)用
4. 操作麻煩：數(shù)組的增加和刪除操作很麻煩

線性表

物理結(jié)構(gòu)劃分（一個(gè)蘿卜一個(gè)坑，美女）

image

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（天龍三兄弟）

image

• 順序表

image

image

a1是a2的前驅(qū)，ai+1是ai的后繼，a1沒有前驅(qū)，an沒有后繼
n為線性表長(zhǎng)度，若n==0,線性表為空
數(shù)據(jù)節(jié)點(diǎn)：

class students{
    Student[40];
    int size;
    ...
}

下面從ArrayList的添加刪除來(lái)看看順序表：（從android studio中分離出來(lái)的方法）

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

 public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;

add方法中有一個(gè)參數(shù)和二個(gè)參數(shù)的方法，首先我們看一個(gè)參數(shù)的方法：
首先看看ensureCapacityInternal（size+1）從他的參數(shù)我們可以看到是整個(gè)ArrayList大小+1,如果ArrayList（elementData）數(shù)組等于初始的數(shù)組，就對(duì)比傳入?yún)?shù)與默認(rèn)的參數(shù)大小，兩者取其大

 private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

如果較大的參數(shù)減去當(dāng)前ArrayList的真實(shí)長(zhǎng)度是大于0的，我們就走grow方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow方法中有一個(gè)新的容積大?。╪ewCapacity），他擴(kuò)充的大小相當(dāng)于當(dāng)前ArrayList的size+size*2,這個(gè)值與minCapacity對(duì)比取其大值，并且限制不能小于int的MAX。做完判斷就會(huì)走copeyOf方法

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

System.arraycopy(a,4,a1,5,6)：把a(bǔ)數(shù)組的數(shù)據(jù)從下標(biāo) 4 開始，移動(dòng)到 a1數(shù)組下標(biāo)是 5 ，移動(dòng)6的長(zhǎng)度

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

現(xiàn)在來(lái)看二個(gè)參數(shù)的add方法：
先走一個(gè)OutOfBoundsException的判斷，如果當(dāng)前要添加的位置index大于ArrayList的長(zhǎng)度，或者小于0，根據(jù)前面的分析ensureCapacityInternal(size + 1)就是對(duì)ArrayList進(jìn)行擴(kuò)容，擴(kuò)容完就繼續(xù)復(fù)制，System.arraycopy(elementData, index, elementData, index + 1, size - index);
將elementData的下標(biāo)為index復(fù)制到index+1處，復(fù)制的大小就是size-index，然后將要添加的值element插入到數(shù)組的index處，同時(shí)增加Arraylist的size，+1。
remove方法也有兩種參數(shù)，一個(gè)是int下標(biāo)，一個(gè)是object值：
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

先看傳入int下標(biāo)的方法，如果下標(biāo)大于ArrayList長(zhǎng)度，就出OutOfBoundsException。獲取在該index上的元素，判斷需要發(fā)生移動(dòng)的數(shù)據(jù)量大小，然后將index+1的numMoved的數(shù)據(jù)移動(dòng)到從index開始，同時(shí)將最后一位置為空。
如果傳入了Object，就循環(huán)遍歷出這個(gè)數(shù)據(jù)，并進(jìn)行移除。
ArrayList類的關(guān)系如下：

image

ArrayList面試常見問(wèn)題

ArrayList的大小是如何自動(dòng)增加的？
ArrayList在add方法中會(huì)做出判斷，如果當(dāng)前長(zhǎng)度過(guò)短，會(huì)增加size+size*2的長(zhǎng)度

什么情況下你會(huì)使用ArrayList？
ArrayList在插入刪除時(shí)候有明顯的復(fù)雜度增加，因?yàn)樗麆h除的時(shí)候是順序表，插入刪除都要移動(dòng)size-index-1長(zhǎng)度的數(shù)據(jù)。明白他的特性下，我會(huì)在保存數(shù)據(jù)同時(shí)對(duì)這段數(shù)據(jù)不進(jìn)行排序刪除等操作時(shí)候，我會(huì)優(yōu)先使用ArrayList，如果要進(jìn)行排序等操作我會(huì)選擇LinkList。

在索引中ArrayList的增加或者刪除某個(gè)對(duì)象的運(yùn)行過(guò)程？效率很低嗎？解釋一下為什么？
從ArrayList的remove方法我們可以看到，如果要?jiǎng)h除某個(gè)對(duì)象，根據(jù)對(duì)象刪除需要遍歷整個(gè)數(shù)組，然后刪除后進(jìn)行位移，根據(jù)下標(biāo)刪除也需要進(jìn)行位移，效率很低。但是在尾部刪除或者添加，根據(jù)順序表的規(guī)則，效率不低。

ArrayList如何順序刪除節(jié)點(diǎn) ？
他是可以順序刪除節(jié)點(diǎn)的。通過(guò)迭代器順序刪除，each和for循環(huán)也可以刪除，但是需要從后往前刪除。如果從前往后刪，根據(jù)順序表的特點(diǎn)，0節(jié)點(diǎn)永遠(yuǎn)存在，刪除了也會(huì)從1節(jié)點(diǎn)上面前移所以會(huì)報(bào)錯(cuò)。

arrayList的遍歷方法
each和for循環(huán)，迭代器

線性表之鏈表

定義：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的

class Node{
    Object data;     
    Node next;
}

image

單循環(huán)鏈表

image

雙循環(huán)鏈表

image

鏈表的增刪改查

image

//增
s.next=p.next
p.next=s
//刪
p.next=p.next.next
//改
p.data=new data();
//查
while(p.next!=l){
    p=p.next;
}

順序表 優(yōu)點(diǎn)，存儲(chǔ)空間連續(xù)允許隨機(jī)訪問(wèn)尾插，尾刪方便，缺點(diǎn)插入效率低，刪除效率低，長(zhǎng)度固定
單鏈表 優(yōu)點(diǎn)，隨意進(jìn)行增刪改，插入效率高，刪除效率高O0，長(zhǎng)度可以隨意修改，缺點(diǎn)內(nèi)存不連續(xù)，不能隨機(jī)查找

雙鏈表的存儲(chǔ)結(jié)構(gòu)單元
private static class Node<E>{
E item;
Node<E> next;
Node<E> prev;
}

image

雙鏈表的表現(xiàn)形式

image

雙鏈表的知識(shí)樹

1. 增

image

1：s.next=p.next;
2: p.next.prev=s;
3: s.prev=p;
4: p.next=s;
//步驟不能亂，否則就會(huì)出現(xiàn)跳躍式的循環(huán)，比如2,4調(diào)換，這樣s=p.next,而p.next.prev=s,這樣s這里就出現(xiàn)了一個(gè)死循環(huán)

2. 刪

image

p.next.prev=p.prev;
p.pre.next=p.next;

image

image

現(xiàn)在分析一下LinkedList的添加刪除方法：首先是add()
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

單參數(shù)的add，方法很簡(jiǎn)單，只有一個(gè)likLast(e)
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
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;
    }
}

這是一個(gè)簡(jiǎn)單的尾插，我們可以從名稱上看出來(lái)。首先獲取最后一個(gè)節(jié)點(diǎn)l，同時(shí)new出來(lái)一個(gè)Node<>,從Node的構(gòu)造方法，我們可以看出，第一個(gè)是新參數(shù)的prev指向的節(jié)點(diǎn)，而next為空。同時(shí)把尾值替換為新節(jié)點(diǎn)。然后是一個(gè)判斷，當(dāng)首節(jié)點(diǎn)為空，就把新參數(shù)作為首節(jié)點(diǎn)，否則就將首節(jié)點(diǎn)的next指向尾節(jié)點(diǎn)。
再看兩個(gè)參數(shù)的add方法。當(dāng)插入的位置為尾部，就使用尾插，否則就走linkBefore

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

拿出該插入位置的pred(p.prev),同時(shí)新建一個(gè)Node（s），將新節(jié)點(diǎn)的prev指向該prev(s.prev=pred)，同時(shí)將新節(jié)點(diǎn)的next，指向原位置的節(jié)點(diǎn)(s.next=p)。判斷如果新節(jié)點(diǎn)的prev為空，那就將新節(jié)點(diǎn)命名為首節(jié)點(diǎn)，否決就將老節(jié)點(diǎn)的next指向新節(jié)點(diǎn)（pred.next=s）

刪除方法如下：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

傳入下標(biāo)的方法相對(duì)簡(jiǎn)單
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

判斷下標(biāo)節(jié)點(diǎn)prev，若prev為空，這時(shí)候就在首節(jié)點(diǎn)位置，就把首節(jié)點(diǎn)復(fù)制為下標(biāo)節(jié)點(diǎn)的next，否則就將下表節(jié)點(diǎn)的值賦為她的next（prev.next=next）,同時(shí)把下標(biāo)節(jié)點(diǎn)的prev指空。如果next位置為空，那么此時(shí)處于尾節(jié)點(diǎn)位置，將節(jié)點(diǎn)的next的prev指向prev，并將下標(biāo)節(jié)點(diǎn)指向null。最后將節(jié)點(diǎn)賦空。
如果是傳入Object，分兩種情況進(jìn)行遍歷。

List總結(jié)

image

1. List是一個(gè)接口，它繼承于Collection的接口。它代表這有序的隊(duì)列
2. AbstractList是一個(gè)抽象類，它繼承于AbstractCollection。AbstractList實(shí)現(xiàn)了List接口中除size（）、get（int location）之外的函數(shù)
3. AbstractSequentialList是一個(gè)抽象類，它繼承于AbstractList。AbstractSequentialList實(shí)現(xiàn)了鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)
4. ArrayList，LinkList，Vector，Stack是List的4個(gè)實(shí)現(xiàn)類