本節(jié)我們討論常見(jiàn)常用的數(shù)據(jù)結(jié)構(gòu)——表。

如果要通俗簡(jiǎn)單的說(shuō)什么是表，那我們可以這樣說(shuō)： 按順序排好的元素集合就是表。

表的概述

抽象數(shù)據(jù)類型是帶有一組操作的一些對(duì)象的結(jié)合

1、定義：

線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有n≥0個(gè)結(jié)點(diǎn)的有限序列，對(duì)于其中的結(jié)點(diǎn)，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)沒(méi)有前驅(qū)但有一個(gè)后繼結(jié)點(diǎn)，有且僅有一個(gè)終端結(jié)點(diǎn)沒(méi)有后繼但有一個(gè)前驅(qū)結(jié)點(diǎn)，其它的結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。

2、特征/性質(zhì)

• 1)集合中必存在唯一的一個(gè)***個(gè)元素
• 2)集合中必存在唯一的一個(gè)***元素
• 3)除***一個(gè)元素之外，均有唯一的后繼
• 4)除***個(gè)元素之外，均有唯一的前驅(qū)

在上圖中，a1是a2的前驅(qū)，ai+1 是ai的后繼，a1沒(méi)有前驅(qū)，an沒(méi)有后繼 ，n為線性表的長(zhǎng)度 ，若n==0時(shí)，線性表為空表 ，下圖就是一個(gè)標(biāo)準(zhǔn)的線性表

線性表分為如下幾種：

順序存儲(chǔ)方式線性表

順序存儲(chǔ)方式線性表中，存儲(chǔ)位置連續(xù)，可以很方便計(jì)算各個(gè)元素的地址

如每個(gè)元素占C個(gè)存儲(chǔ)單元，那么有： Loc(An) = Loc(An-1) + C,于是有： Loc(An) = Loc(A1)+(i-1)*C;

優(yōu)點(diǎn)：查詢很快

缺點(diǎn)：插入和刪除效率慢

下圖很形象的表現(xiàn)了，插入和刪除慢的特點(diǎn)

表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)順序存儲(chǔ)方式線性的典型就是數(shù)組，對(duì)于表的所有操作都可以通過(guò)使用數(shù)組來(lái)實(shí)現(xiàn)。雖然數(shù)組創(chuàng)建時(shí)就已經(jīng)是固定大小，但在需要的使用可以用雙倍的容量創(chuàng)建一個(gè)不同的數(shù)組。下面是擴(kuò)容的偽代碼：

int[] aar = new int[10]; 
      //擴(kuò)大aar 
      int[] newArr = new int[aar.length * 2]; 
      for (int i = 0; i < aar.length; i++) { 
          newArr[i] = aar[i]; 
      } 
      aar = newArr; 

數(shù)組的實(shí)現(xiàn)使得printList以線性時(shí)間被執(zhí)行，而findKth(返回特定位置上的元素)則花費(fèi)常數(shù)的時(shí)間。

最壞的情形是，在位置0插入一個(gè)元素，需要將數(shù)組中所有元素向后移動(dòng)一個(gè)位置，而刪除一個(gè)元素，則需要將所有元素向前移動(dòng)一個(gè)位置，兩種情況復(fù)雜度都是O(n)。平均來(lái)看，兩種操作都需要移動(dòng)表一半的元素，因此需要線性時(shí)間，但是如果插入和刪除都發(fā)生在數(shù)組的最尾，則插入和刪除都只需要花費(fèi)O(1)的時(shí)間。

如果頻繁的插入和刪除發(fā)生在表的最前端，則使用鏈表會(huì)更好。

鏈?zhǔn)酱鎯?chǔ)方式線性表

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

優(yōu)點(diǎn)：相對(duì)于數(shù)組，刪除還插入效率高

缺點(diǎn)：相對(duì)于數(shù)組，查詢效率低

要執(zhí)行插入操作，只需要如下的代碼：

s->next = p->next 
p-next = s ; 

執(zhí)行刪除操作，只需要如下的代碼：

p->next = p->next->next 

循環(huán)鏈表將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相連的單鏈表稱為單循環(huán)鏈表，簡(jiǎn)稱循環(huán)鏈表

雙向循環(huán)鏈表

雙向循環(huán)鏈表是單向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域

對(duì)于空的雙向循環(huán)鏈表

雙向循環(huán)鏈表插入

Java Collection Api中的表

1.IteratorIterator接口的思路，通過(guò)Iterator方法，每個(gè)集合均創(chuàng)建并返回給客戶一個(gè)實(shí)現(xiàn)Iterator接口的對(duì)象，并將當(dāng)前位置的概念在對(duì)象內(nèi)部存儲(chǔ)下來(lái)。

public interface Iterator<E> {  
    boolean hasNext();  
    E next();  
    default void remove() { 
        throw new UnsupportedOperationException("remove"); 
    }  
} 

Iterator中的方法有限，因此，很難使用Iterator做遍歷Collection意外的任何工作。Iterator還包含一個(gè)remove()方法。該方法的作用是刪除next()***返回的項(xiàng)(此后不能再調(diào)用remove()，直到你下一次調(diào)用next())。

如果對(duì)正在被迭代的集合進(jìn)行結(jié)構(gòu)上的改變(即對(duì)該集合使用add,remove或clear),那么迭代器將不再合法(并且在其后使用該迭代器將出現(xiàn)ConcurrentModificationException異常被拋出)，為了避免迭代器準(zhǔn)備給出某一項(xiàng)作為下一項(xiàng)而該項(xiàng)此后或者被刪除，所以只有在需要立即使用一個(gè)迭代器的時(shí)候，我們才應(yīng)該獲取迭代器。然而，如果迭代器調(diào)用了它自己的remove方法，那么這個(gè)迭代器就仍然合法的。

2.List接口

public interface List<E> extends Collection<E> {  
    int size();  
    boolean isEmpty();  
    Iterator<E> iterator(); 
     Object[] toArray();  
    <T> T[] toArray(T[] a);  
    boolean add(E e);  
    boolean remove(Object o);  
    boolean containsAll(Collection<?> c);  
    boolean addAll(Collection<? extends E> c);  
    boolean addAll(int index, Collection<? extends E> c);  
    boolean removeAll(Collection<?> c);  
    boolean retainAll(Collection<?> c);  
    void clear();  
    boolean equals(Object o);  
    int hashCode();  
    E get(int index);  
    E set(int index, E element);  
    void add(int index, E element);  
    E remove(int index);  
    int indexOf(Object o);  
    int lastIndexOf(Object o);  
    ListIterator<E> listIterator();  
} 

List ATD有兩種流行的實(shí)現(xiàn)方式，ArrayList和LinkedList。

ArrayList的優(yōu)點(diǎn)是，get和set調(diào)用花費(fèi)常數(shù)時(shí)間。缺點(diǎn)是新項(xiàng)的插入和現(xiàn)有項(xiàng)的刪除代價(jià)昂貴，除非變動(dòng)的是ArrayList的末端。

LinkedList優(yōu)點(diǎn)是在表的前端添加和刪除都是常數(shù)時(shí)間，缺點(diǎn)是不容易作索引，get的調(diào)用是昂貴的，除非是接近表的端點(diǎn)

public static void makeList1(List<Integer> lst,int n){ 
        lst.clear(); 
        for (int i = 0; i < n; i++) { 
            lst.add(i); 
        } 
    } 

不管ArrayList還是LinkedList作為參數(shù)被傳遞，makeList1的運(yùn)行時(shí)間都是O(N)，因?yàn)閷?duì)add的每次調(diào)用都是在表的末端進(jìn)行從而花費(fèi)常數(shù)時(shí)間(可以忽略對(duì)ArrayList偶爾擴(kuò)展)。另一方面，如果我們通過(guò)在表的前端添加一些項(xiàng)來(lái)構(gòu)造一個(gè)List:

public static void makeList2(List<Integer> lst,int n){ 
        lst.clear(); 
        for (int i = 0; i < n; i++) { 
            lst.add(i); 
        } 
    } 

對(duì)于LinkedList它的運(yùn)行時(shí)間是O(N)，但是對(duì)于ArrayList其運(yùn)行時(shí)間則是O(n^2)，因?yàn)樵贏rrayList中，在前端進(jìn)行添加是一個(gè)O(N)操作。

public static int sum(List<Integer> lst){ 
        int total = 0; 
        for (int i = 0; i < n; i++) { 
            total+=lst.get(i); 
 
        } 
        return total; 
    } 

這里，ArrayList的運(yùn)行時(shí)間是O(N)，但對(duì)于LinkedList來(lái)說(shuō)，其運(yùn)行時(shí)間則是O(n^2)，因?yàn)長(zhǎng)inkedList中，對(duì)get的調(diào)用為O(N)操作。可是，要是使用一個(gè)增強(qiáng)的for循環(huán)，那么它對(duì)任意List的運(yùn)行時(shí)間都是O(N)，因?yàn)榈鲗⒂行У貜囊豁?xiàng)到下一項(xiàng)推進(jìn)。

對(duì)搜索而言，ArrayList和LinkedList都是低效，對(duì)Collection的contains和remove方法調(diào)用均花費(fèi)線性時(shí)間。

例子：remove方法對(duì)LinkedList類的使用例子1：假設(shè)現(xiàn)在有6，5，1，4，2五個(gè)數(shù)，需要在方法調(diào)用之后去除所有的偶數(shù)。

思路：

1. 創(chuàng)建一張包含所有奇數(shù)的新表，清除原表，再將奇數(shù)拷貝回去。
2. 直接在原表中進(jìn)行遍歷，遇到偶數(shù)時(shí)直接進(jìn)行移除。

ArrayList和LinkedList針對(duì)于remove都是低效的，在LinkedList中，到達(dá)i位置的代價(jià)是昂貴的。

public static void removEventVer1(List<Integer> lst) { 
        int i = 0; 
        while (i < lst.size()) { 
            if (lst.get(i) % 2 == 0) { 
                lst.remove(i); 
            } else { 
                i++; 
            } 
        } 
    } 

對(duì)于LinkedList來(lái)說(shuō)，上面的解法運(yùn)行時(shí)間則是O(n^2)，使用迭代器的效率會(huì)更好，當(dāng)然在使用迭代器時(shí)，我們不能直接使用List的

remove,否則會(huì)拋出異常，就像下面的寫法(增強(qiáng)for循環(huán)底層還是用的迭代器)

public static void removEventVer2(List<Integer> lst) { 
        for (Integer x : lst) { 
            if (x % 2 == 0) { 
                lst.remove(x); 
            } 
 
        } 
    } 

為了解決上面的問(wèn)題，我們可以直接使用迭代器的remove方法，這樣做是合法的

public static void removEventVer3(List<Integer> lst) { 
        Iterator<Integer> itr = lst.iterator(); 
        while (itr.hasNext()){ 
            if (itr.next()%2==0){ 
                itr.remove(); 
            } 
        } 
 
    } 

使用了Iterator以后，LinkedList的remove操作消耗的就是O(n)時(shí)間，因?yàn)镮terator已經(jīng)位于需要被刪除的節(jié)點(diǎn)上。

而即使使用Iterator，ArrayList的remove方法還是O(n^2)，因?yàn)閯h除，數(shù)組的數(shù)還是需要進(jìn)行移動(dòng)。

ListIterator接口ListIterator接口擴(kuò)展了Iterator，hasNext和hasPrevious方法，使得既可以從前遍歷也可以從尾巴進(jìn)行遍歷，add在當(dāng)前位置插入一個(gè)新的項(xiàng)，set方法改變Iterator調(diào)用hasNext或hasPrevious返回的當(dāng)前值。

public interface ListIterator<E> extends Iterator<E> { 
    boolean hasNext(); 
    boolean hasPrevious(); 
    void remove(); 
    void set(E e); 
    void add(E e); 

實(shí)現(xiàn)一個(gè)ArrayList

下面，我們自己手寫一個(gè)ArrayList，且支持泛型，代碼如下：

public class MyArrayList<T> implements Iterable<T> { 
 
    private static final int DEFAULT_CAPACITY = 10; 
    private T[] mArray; 
    private int mArraySize; 
 
    @Override 
    public Iterator<T> iterator() { 
        return new ArrayIterator(); 
    }  
 
    private class ArrayIterator implements Iterator<T> { 
        private int currentPositon;  
        @Override 
        public boolean hasNext() { 
            return currentPositon < mArraySize; 
        } 
 
        @Override 
        public T next() { 
            if (!hasNext()) { 
                throw new NoSuchElementException(); 
            } 
 
            return mArray[currentPositon++]; 
        } 
 
        @Override 
        public void remove() { 
            MyArrayList.this.remove(--currentPositon); 
        } 
    }   
    public void trimTosize() { 
        ensureCapacity(size()); 
    } 
 
    public int size() { 
        return mArraySize; 
    } 
 
    public boolean isEmpty() { 
        return mArraySize == 0; 
    }  
    public MyArrayList(int size) { 
        if (size < DEFAULT_CAPACITY) { 
            mArraySize = size; 
        } else { 
            ensureCapacity(DEFAULT_CAPACITY); 
        } 
    } 
 
    private void ensureCapacity(int newCapacity) { 
        T[] newArray = (T[]) new Object[newCapacity]; 
        for (int i = 0; i < mArray.length; i++) { 
            newArray[i] = mArray[i]; 
        } 
        mArray = newArray; 
    }  
    public boolean add(T t) { 
        add(t, mArraySize); 
        return true; 
    } 
 
    public void add(T t, int position) { 
        if (mArraySize == mArray.length) { 
            ensureCapacity(mArraySize * 2 + 1); 
        } 
        for (int i = position; i < mArraySize - 1; i++) { 
            mArray[i + 1] = mArray[i]; 
        } 
        mArray[position] = t; 
        ++mArraySize; 
    } 
 
    public T reomve() { 
        return remove(mArraySize); 
    } 
 
    private T remove(int position) { 
        T t = mArray[position]; 
        for (int i = position; i < mArraySize - 1; i++) { 
            mArray[i] = mArray[i + 1]; 
        } 
        --mArraySize; 
        return t; 
    } 
 
    public T get(int position) { 
        if (position < 0 || position > mArraySize) { 
            throw new ArrayIndexOutOfBoundsException(); 
        } 
        return mArray[position]; 
    } 
 
    public T set(T t) { 
        return set(t, mArraySize - 1); 
    } 
 
    public T set(T t, int position) { 
        if (position < 0 || position > mArraySize) { 
            throw new ArrayIndexOutOfBoundsException(); 
        } 
        T old = mArray[position]; 
        mArray[position] = t; 
        return old; 
    } 
} 

值得一提的是，我們不能直接new T[]，而是需要通過(guò)下面的代碼創(chuàng)建一個(gè)泛型的數(shù)組

T[] newArray = (T[]) new Object[newCapacity]; 

還有一點(diǎn)值得說(shuō)明的是，在ArrayIterator中使用MyArrayList.this.remove是為了避免和迭代器自身的remove沖突

@Override 
        public void remove() { 
            MyArrayList.this.remove(--currentPositon); 
        } 

實(shí)現(xiàn)LinkedList

在LinkedList中，最前端的節(jié)點(diǎn)叫做頭節(jié)點(diǎn)，最末端的節(jié)點(diǎn)叫做尾節(jié)點(diǎn)。這兩個(gè)額外的節(jié)點(diǎn)的存在，排除許多特殊情況，極大簡(jiǎn)化了編碼。例如：如果不使用頭節(jié)點(diǎn)，那么刪除***個(gè)節(jié)點(diǎn)就是特殊情況，因?yàn)樵趧h除時(shí)需要重新調(diào)整鏈表到***個(gè)節(jié)點(diǎn)的鏈，還因?yàn)閯h除算法一般還要訪問(wèn)被刪除節(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)(如果沒(méi)有頭節(jié)點(diǎn)的話，***個(gè)節(jié)點(diǎn)就會(huì)出現(xiàn)前面沒(méi)有節(jié)點(diǎn)的特殊情況)。

public class MyLinkedList<T> implements Iterable<T> { 
 
    private Node<T> headNote; 
    private Node<T> endNote; 
 
    private int mSize; 
    private int modCount; 
 
    public MyLinkedList() { 
        init(); 
    } 
 
    private void init() { 
        headNote = new Node<>(null, null, null); 
        endNote = new Node<>(null, headNote, null); 
        headNote.mNext = endNote; 
 
        mSize = 0; 
        modCount++; 
    } 
 
    public int size() { 
        return mSize; 
    } 
 
    public boolean isEmpty() { 
        return mSize == 0; 
    } 
 
    public boolean add(T t) { 
        addBefore(t, size()); 
        return true; 
    } 
 
    public T get(int index) { 
        Node<T> temp = getNode(index, 0, size()); 
        return temp.mData; 
    } 
 
    public T remove(int position) { 
        Node<T> tempNode = getNode(position); 
        return remove(tempNode); 
    } 
 
    private T remove(Node<T> tempNode) { 
        tempNode.mPre.mNext = tempNode.mNext; 
        tempNode.mNext.mPre = tempNode.mPre; 
        mSize--; 
        modCount++; 
        return tempNode.mData; 
    } 
 
    public T set(int index, T t) { 
        Node<T> tempNode = getNode(index); 
        T old = tempNode.mData; 
        tempNode.mData = t; 
        return old; 
    } 
 
    private Node<T> getNode(int index) { 
        return getNode(index, 0, size() - 1); 
    } 
 
 
 
    private Node<T> getNode(int index, int lower, int upper) { 
        Node<T> tempNode; 
 
        if (lower < 0 || upper > mSize) { 
            throw new IndexOutOfBoundsException(); 
        } 
 
        if (index < mSize / 2) { 
            tempNode = headNote.mNext; 
            for (int i = 0; i < index; i++) { 
                tempNode = tempNode.mNext; 
            } 
        } else { 
            tempNode = endNote; 
            for (int i = mSize; i > index; i--) { 
                tempNode = tempNode.mPre; 
            } 
        } 
        return tempNode; 
    } 
 
 
    private static class Node<T> { 
 
        private Node<T> mNext; 
        private T mData; 
        private Node<T> mPre; 
 
        public Node(T data, Node<T> pre, Node<T> next) { 
            mData = data; 
            mPre = pre; 
            mNext = next; 
        } 
    } 
 
 
    private class LinkedListIterator implements Iterator<T> { 
        private Node<T> currentNode = headNote.mNext; 
        private int expectedModCount = modCount; 
        private boolean okToMove; 
 
        @Override 
        public boolean hasNext() { 
            return currentNode != endNote; 
        } 
 
        @Override 
        public T next() { 
            if (modCount != expectedModCount) { 
                throw new ConcurrentModificationException(); 
            } 
            if (!hasNext()) { 
                throw new NoSuchElementException(); 
            } 
            T t = currentNode.mData; 
            currentNode = currentNode.mNext; 
            okToMove = true; 
            return t; 
        } 
 
         @Override 
        public void remove() { 
            if (modCount != expectedModCount) { 
                throw new ConcurrentModificationException(); 
            } 
            if (!okToMove) { 
                throw new IllegalStateException(); 
            } 
            MyLinkedList.this.remove(currentNode.mPre); 
            expectedModCount++; 
            okToMove = false; 
        } 
 
    @Override 
    public Iterator<T> iterator() { 
        return new LinkedListIterator(); 
    } 
} 

1.modCount代表自從構(gòu)造以來(lái)對(duì)鏈表所做改變的次數(shù)。每次對(duì)add或remove的調(diào)用都將更新modCount。想法在于,當(dāng)一個(gè)迭代器被建立時(shí)，他將存儲(chǔ)集合的modCount。每次個(gè)迭代器方法(next或remove)的調(diào)用都將該鏈表內(nèi)的當(dāng)前modCount檢測(cè)在迭代器內(nèi)存儲(chǔ)的modCount，并且當(dāng)兩個(gè)計(jì)數(shù)不匹配時(shí)，拋出一個(gè)ConcurrentModificationException異常。

2.在LinkedListIterator中，currentNode表示包含由調(diào)用next所返回的項(xiàng)的節(jié)點(diǎn)。注意，當(dāng)currentNode被定位在endNote，對(duì)next調(diào)用是非法的。

在LinkedListIterator的remove方法中，currentNode是保持不變的，因?yàn)閏urrentNode節(jié)點(diǎn)不受前面節(jié)點(diǎn)被刪除的影響，與ArrayIterator不同，(在ArrayIterator中，項(xiàng)被移動(dòng)，要求更新current)