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

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

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

• 數(shù)據(jù)項：一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成
• 數(shù)據(jù)對象：有相同性質(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ù)對象中數(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ī)中的存儲

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

image

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

image

數(shù)組

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

線性表

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

image

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

image

• 順序表

image

image

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

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

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

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方法中有一個參數(shù)和二個參數(shù)的方法叶撒，首先我們看一個參數(shù)的方法：
首先看看ensureCapacityInternal（size+1）從他的參數(shù)我們可以看到是整個ArrayList大小+1,如果ArrayList（elementData）數(shù)組等于初始的數(shù)組，就對比傳入?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的真實長度是大于0的祠够，我們就走grow方法

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

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

grow方法中有一個新的容積大小（newCapacity）粪牲，他擴(kuò)充的大小相當(dāng)于當(dāng)前ArrayList的size+size*2,這個值與minCapacity對比取其大值古瓤，并且限制不能小于int的MAX。做完判斷就會走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 開始腺阳，移動到 a1數(shù)組下標(biāo)是 5 落君，移動6的長度

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)在來看二個參數(shù)的add方法：
先走一個OutOfBoundsException的判斷，如果當(dāng)前要添加的位置index大于ArrayList的長度亭引，或者小于0绎速，根據(jù)前面的分析ensureCapacityInternal(size + 1)就是對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處主届，同時增加Arraylist的size赵哲，+1。
remove方法也有兩種參數(shù)君丁，一個是int下標(biāo)枫夺，一個是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長度绘闷，就出OutOfBoundsException橡庞。獲取在該index上的元素较坛，判斷需要發(fā)生移動的數(shù)據(jù)量大小，然后將index+1的numMoved的數(shù)據(jù)移動到從index開始扒最，同時將最后一位置為空丑勤。
如果傳入了Object，就循環(huán)遍歷出這個數(shù)據(jù)吧趣，并進(jìn)行移除法竞。
ArrayList類的關(guān)系如下：

image

ArrayList面試常見問題

ArrayList的大小是如何自動增加的？
ArrayList在add方法中會做出判斷强挫，如果當(dāng)前長度過短岔霸，會增加size+size*2的長度

什么情況下你會使用ArrayList？
ArrayList在插入刪除時候有明顯的復(fù)雜度增加俯渤，因為他刪除的時候是順序表呆细，插入刪除都要移動size-index-1長度的數(shù)據(jù)。明白他的特性下八匠，我會在保存數(shù)據(jù)同時對這段數(shù)據(jù)不進(jìn)行排序刪除等操作時候絮爷，我會優(yōu)先使用ArrayList，如果要進(jìn)行排序等操作我會選擇LinkList臀叙。

在索引中ArrayList的增加或者刪除某個對象的運行過程略水？效率很低嗎？解釋一下為什么劝萤？
從ArrayList的remove方法我們可以看到渊涝，如果要刪除某個對象，根據(jù)對象刪除需要遍歷整個數(shù)組床嫌，然后刪除后進(jìn)行位移跨释，根據(jù)下標(biāo)刪除也需要進(jìn)行位移，效率很低厌处。但是在尾部刪除或者添加鳖谈，根據(jù)順序表的規(guī)則，效率不低阔涉。

ArrayList如何順序刪除節(jié)點 缆娃？
他是可以順序刪除節(jié)點的。通過迭代器順序刪除瑰排，each和for循環(huán)也可以刪除贯要，但是需要從后往前刪除。如果從前往后刪椭住，根據(jù)順序表的特點崇渗，0節(jié)點永遠(yuǎn)存在，刪除了也會從1節(jié)點上面前移所以會報錯。

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

線性表之鏈表

定義：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素葫掉，這組存儲單元可以是連續(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)點跟狱，存儲空間連續(xù)允許隨機(jī)訪問尾插俭厚，尾刪方便，缺點插入效率低驶臊，刪除效率低套腹，長度固定
單鏈表 優(yōu)點，隨意進(jìn)行增刪改资铡，插入效率高，刪除效率高O0幢码，長度可以隨意修改笤休，缺點內(nèi)存不連續(xù)，不能隨機(jī)查找

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

image

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

image

雙鏈表的知識樹

1. 增

image

1：s.next=p.next;
2: p.next.prev=s;
3: s.prev=p;
4: p.next=s;
//步驟不能亂症副，否則就會出現(xiàn)跳躍式的循環(huán)店雅，比如2,4調(diào)換，這樣s=p.next,而p.next.prev=s,這樣s這里就出現(xiàn)了一個死循環(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贞铣，方法很簡單闹啦，只有一個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;
    }
}

這是一個簡單的尾插，我們可以從名稱上看出來辕坝。首先獲取最后一個節(jié)點l窍奋，同時new出來一個Node<>,從Node的構(gòu)造方法，我們可以看出酱畅，第一個是新參數(shù)的prev指向的節(jié)點琳袄，而next為空。同時把尾值替換為新節(jié)點纺酸。然后是一個判斷窖逗，當(dāng)首節(jié)點為空，就把新參數(shù)作為首節(jié)點餐蔬，否則就將首節(jié)點的next指向尾節(jié)點碎紊。
再看兩個參數(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),同時新建一個Node（s），將新節(jié)點的prev指向該prev(s.prev=pred)啄骇，同時將新節(jié)點的next痴鳄，指向原位置的節(jié)點(s.next=p)。判斷如果新節(jié)點的prev為空缸夹，那就將新節(jié)點命名為首節(jié)點痪寻，否決就將老節(jié)點的next指向新節(jié)點（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)的方法相對簡單
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é)點prev螺句，若prev為空，這時候就在首節(jié)點位置橡类，就把首節(jié)點復(fù)制為下標(biāo)節(jié)點的next蛇尚，否則就將下表節(jié)點的值賦為她的next（prev.next=next）,同時把下標(biāo)節(jié)點的prev指空。如果next位置為空顾画，那么此時處于尾節(jié)點位置取劫，將節(jié)點的next的prev指向prev，并將下標(biāo)節(jié)點指向null研侣。最后將節(jié)點賦空谱邪。
如果是傳入Object，分兩種情況進(jìn)行遍歷庶诡。

List總結(jié)

image

1. List是一個接口惦银，它繼承于Collection的接口。它代表這有序的隊列
2. AbstractList是一個抽象類末誓，它繼承于AbstractCollection扯俱。AbstractList實現(xiàn)了List接口中除size（）、get（int location）之外的函數(shù)
3. AbstractSequentialList是一個抽象類喇澡，它繼承于AbstractList迅栅。AbstractSequentialList實現(xiàn)了鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)
4. ArrayList晴玖，LinkList读存，Vector，Stack是List的4個實現(xiàn)類