本節我們討論常見常用的數據結構——表。

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

表的概述

抽象數據類型是帶有一組操作的一些對象的結合

1、定義：

線性表是一個線性結構，它是一個含有n≥0個結點的有限序列，對于其中的結點，有且僅有一個開始結點沒有前驅但有一個后繼結點，有且僅有一個終端結點沒有后繼但有一個前驅結點，其它的結點都有且僅有一個前驅和一個后繼結點。

2、特征/性質

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

在上圖中，a1是a2的前驅，ai+1 是ai的后繼，a1沒有前驅，an沒有后繼 ，n為線性表的長度 ，若n==0時，線性表為空表 ，下圖就是一個標準的線性表

線性表分為如下幾種：

順序存儲方式線性表

順序存儲方式線性表中，存儲位置連續，可以很方便計算各個元素的地址

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

優點：查詢很快

缺點：插入和刪除效率慢

下圖很形象的表現了，插入和刪除慢的特點

表的簡單數組實現順序存儲方式線性的典型就是數組，對于表的所有操作都可以通過使用數組來實現。雖然數組創建時就已經是固定大小，但在需要的使用可以用雙倍的容量創建一個不同的數組。下面是擴容的偽代碼：

 

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

數組的實現使得printList以線性時間被執行，而findKth(返回特定位置上的元素)則花費常數的時間。

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

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

鏈式存儲方式線性表

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續的，也可以是不連續的

優點：相對于數組，刪除還插入效率高

缺點：相對于數組，查詢效率低

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

 

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

 

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

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

循環鏈表將單鏈表中終端結點的指針端由空指針改為指向頭結點，就使整個單鏈表形成一個環，這種頭尾相連的單鏈表稱為單循環鏈表，簡稱循環鏈表

雙向循環鏈表

雙向循環鏈表是單向循環鏈表的每個結點中，再設置一個指向其前驅結點的指針域

對于空的雙向循環鏈表

雙向循環鏈表插入

Java Collection Api中的表

1.IteratorIterator接口的思路，通過Iterator方法，每個集合均創建并返回給客戶一個實現Iterator接口的對象，并將當前位置的概念在對象內部存儲下來。

 

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

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

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

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有兩種流行的實現方式，ArrayList和LinkedList。

ArrayList的優點是，get和set調用花費常數時間。缺點是新項的插入和現有項的刪除代價昂貴，除非變動的是ArrayList的末端。

LinkedList優點是在表的前端添加和刪除都是常數時間，缺點是不容易作索引，get的調用是昂貴的，除非是接近表的端點

 

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

不管ArrayList還是LinkedList作為參數被傳遞，makeList1的運行時間都是O(N)，因為對add的每次調用都是在表的末端進行從而花費常數時間(可以忽略對ArrayList偶爾擴展)。另一方面，如果我們通過在表的前端添加一些項來構造一個List:

 

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

對于LinkedList它的運行時間是O(N)，但是對于ArrayList其運行時間則是O(n^2)，因為在ArrayList中，在前端進行添加是一個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的運行時間是O(N)，但對于LinkedList來說，其運行時間則是O(n^2)，因為LinkedList中，對get的調用為O(N)操作。可是，要是使用一個增強的for循環，那么它對任意List的運行時間都是O(N)，因為迭代器將有效地從一項到下一項推進。

對搜索而言，ArrayList和LinkedList都是低效，對Collection的contains和remove方法調用均花費線性時間。

例子：remove方法對LinkedList類的使用例子1：假設現在有6，5，1，4，2五個數，需要在方法調用之后去除所有的偶數。

思路：

1. 創建一張包含所有奇數的新表，清除原表，再將奇數拷貝回去。
2. 直接在原表中進行遍歷，遇到偶數時直接進行移除。

ArrayList和LinkedList針對于remove都是低效的，在LinkedList中，到達i位置的代價是昂貴的。

 

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

對于LinkedList來說，上面的解法運行時間則是O(n^2)，使用迭代器的效率會更好，當然在使用迭代器時，我們不能直接使用List的

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

 

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

為了解決上面的問題，我們可以直接使用迭代器的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)時間，因為Iterator已經位于需要被刪除的節點上。

而即使使用Iterator，ArrayList的remove方法還是O(n^2)，因為刪除，數組的數還是需要進行移動。

ListIterator接口ListIterator接口擴展了Iterator，hasNext和hasPrevious方法，使得既可以從前遍歷也可以從尾巴進行遍歷，add在當前位置插入一個新的項，set方法改變Iterator調用hasNext或hasPrevious返回的當前值。

 

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

實現一個ArrayList

下面，我們自己手寫一個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[]，而是需要通過下面的代碼創建一個泛型的數組

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

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

 

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

實現LinkedList

在LinkedList中，最前端的節點叫做頭節點，最末端的節點叫做尾節點。這兩個額外的節點的存在，排除許多特殊情況，極大簡化了編碼。例如：如果不使用頭節點，那么刪除***個節點就是特殊情況，因為在刪除時需要重新調整鏈表到***個節點的鏈，還因為刪除算法一般還要訪問被刪除節點前面的那個節點(如果沒有頭節點的話，***個節點就會出現前面沒有節點的特殊情況)。

 

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代表自從構造以來對鏈表所做改變的次數。每次對add或remove的調用都將更新modCount。想法在于,當一個迭代器被建立時，他將存儲集合的modCount。每次個迭代器方法(next或remove)的調用都將該鏈表內的當前modCount檢測在迭代器內存儲的modCount，并且當兩個計數不匹配時，拋出一個ConcurrentModificationException異常。

2.在LinkedListIterator中，currentNode表示包含由調用next所返回的項的節點。注意，當currentNode被定位在endNote，對next調用是非法的。

在LinkedListIterator的remove方法中，currentNode是保持不變的，因為currentNode節點不受前面節點被刪除的影響，與ArrayIterator不同，(在ArrayIterator中，項被移動，要求更新current)