第二章線形表-順序表

質問を発する
シーケンス表は、配列に基づく線形表の一実施形態である。
抽象データタイプ
多くの時間配列は私達の需要を満たすことができません。たとえば、配列に基づいてパッケージ化します。つまり、私達の順序表です。
get Size()
 
 
コードの実装

public class ArrayList {
    /**          */
    private int[] data;
    /** size      data        */
    private int size;

    public ArrayList(int capacity) {
        this.data =  new int[capacity];
        this.size = 0;
    }
    public ArrayList() {
        this(10);
    }

    /**
     *           
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     *        
     * @return
     */
    public int getCapacity(){
        return this.data.length;
    }

    /**
     *          
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    /**
     *      index       
     * @param index
     * @param e
     */
    public void add(int index, int e){
        if (index < 0 || index > this.size){
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size");
        }
        if (this.size == this.data.length){
            throw new IllegalArgumentException("Add failed. Array is full.");
        }
        for (int i = size - 1; i >= index; i--){
            this.data[i + 1] = data[i];
        }
        this.data[index] = e;
        this.size ++;
    }

    /**
     *              
     * @param e
     */
    public void addLast(int e){
        /*
        if (this.size == this.data.length){
            throw new IllegalArgumentException("Add failed. Array is full.");
        }
        this.data[size] = e;
        this.size ++;
        */
        this.add(size, e);
    }

    /**
     *              
     * @param e
     */
    public void addFirst(int e){
        this.add(0, e);
    }

    /**
     *             e
     * @param index
     * @return
     */
    public int get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        return this.data[index];
    }

    /**
     *             e
     * @param e
     * @param index
     */
    public void set(int e, int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        this.data[index] = e;
    }

    /**
     *                e
     * @param e
     * @return
     */
    public boolean contains(int e){
        for (int i = 0; i < size; i++){
            if (data[i] == e){
                return true;
            }
        }
        return false;
    }

    /**
     *         e     ，    e     -1
     * @param e
     * @return
     */
    public int find(int e){
        for (int i = 0; i < size; i++){
            if (data[i] == e){
                return i;
            }
        }
        return -1;
    }

    /**
     *       index      ，       
     * @param index
     * @return
     */
    public int remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        int ret  = this.data[index];
        for (int i = index + 1; i < this.size; i++){
            this.data[i - 1] = this.data[i];
        }
        this.size --;
        return ret;
    }

    /**
     *            ，       
     * @return
     */
    public int removeFirst(){
        return this.remove(0);
    }

    /**
     *             ，       
     * @return
     */
    public int removeLast(){
        return this.remove(this.size -1);
    }

    /**
     *        
     * @param e
     */
    public boolean removeElement(int e){
        int index = this.find(e);
        if (index != -1){
            this.remove(index);

        }
        return false;
    }

    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        rs.append(String.format("Array List: size = %d, capacity = %d
", this.size, this.data.length));
        rs.append("[");
        for (int i = 0; i < this.size; i ++){
            rs.append(this.data[i]);
            if (i != size -1){
                rs.append(", ");
            }
        }
        rs.append("]");
        return rs.toString();
    }
}

 
コードの最適化:
ファンサポートを追加
以上で実現した順序表は、intタイプのデータしか記憶できません。以上で実現した順序表が、より多くのデータタイプを記憶することをサポートするために、モデルを追加します。

public class ArrayList {
    /**          */
    private T[] data;
    /** size      data        */
    private int size;

    public ArrayList(int capacity) {
        this.data = (T[]) new Object[capacity];
        this.size = 0;
    }
    public ArrayList() {
        this(10);
    }

    /**
     *           
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     *        
     * @return
     */
    public int getCapacity(){
        return this.data.length;
    }

    /**
     *          
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    /**
     *      index       
     * @param index
     * @param e
     */
    public void add(int index, T e){
        if (index < 0 || index > this.size){
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size");
        }
        //     data              ，    
        if (this.size == this.data.length){
            resize(2 * this.data.length);
        }
        for (int i = size - 1; i >= index; i--){
            this.data[i + 1] = data[i];
        }
        this.data[index] = e;
        this.size ++;
    }


    /**
     *              
     * @param e
     */
    public void addLast(T e){
        this.add(size, e);
    }

    /**
     *              
     * @param e
     */
    public void addFirst(T e){
        this.add(0, e);
    }

    /**
     *             e
     * @param index
     * @return
     */
    public T get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        return this.data[index];
    }

    /**
     *             e
     * @param e
     * @param index
     */
    public void set(T e, int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        this.data[index] = e;
    }

    /**
     *                e
     * @param e
     * @return
     */
    public boolean contains(T e){
        for (int i = 0; i < size; i++){
            if (data[i] == e){
                return true;
            }
        }
        return false;
    }

    /**
     *         e     ，    e     -1
     * @param e
     * @return
     */
    public int find(T e){
        for (int i = 0; i < size; i++){
            if (data[i].equals(e) ){
                return i;
            }
        }
        return -1;
    }

    /**
     *       index      ，       
     * @param index
     * @return
     */
    public T remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        T ret  =  this.data[index];
        for (int i = index + 1; i < this.size; i++){
            this.data[i - 1] = this.data[i];
        }
        this.size --;
        this.data[size] = null;
        //     data              1/2 ，    
        if (this.size == this.data.length / 2){
            resize(this.data.length / 2);
        }
        return ret;
    }

    /**
     *            ，       
     * @return
     */
    public T removeFirst(){
        return this.remove(0);
    }

    /**
     *             ，       
     * @return
     */
    public T removeLast(){
        return this.remove(this.size -1);
    }

    /**
     *        
     * @param e
     */
    public boolean removeElement(T e){
        int index = this.find(e);
        if (index != -1){
            this.remove(index);

        }
        return false;
    }

    /**
     *         
     * @return
     */
    public T getLast(){
        return this.get(this.size -1);
    }

    /**
     *        
     * @return
     */
    public T getFirst(){
        return this.get(0);
    }


    private void resize(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity];
        for (int i = 0; i < this.size; i++){
            newData[i] = this.data[i];
        }
        this.data = newData;
    }

    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        rs.append(String.format("Array List: size = %d, capacity = %d
", this.size, this.data.length));
        rs.append("[");
        for (int i = 0; i < this.size; i ++){
            rs.append(this.data[i]);
            if (i != size -1){
                rs.append(", ");
            }
        }
        rs.append("]");
        return rs.toString();
    }
}

 
ダイナミック拡大:
以上の順序表を実現しましたが、データは静的な配列を使用しています。容量が限られています。多くの場合、配列にいくつの要素を入れるかを予見できません。この場合、容量が大きすぎると、スペースがもったいないです。容量が小さすぎると、足りないです。このような状況では、私たちは解決策が必要です。配列容量が伸縮可能です。

public class ArrayList {
    /**          */
    private T[] data;
    /** size      data        */
    private int size;

    public ArrayList(int capacity) {
        this.data = (T[]) new Object[capacity];
        this.size = 0;
    }
    public ArrayList() {
        this(10);
    }

    /**
     *           
     * @return
     */
    public int getSize(){
        return this.size;
    }

    /**
     *        
     * @return
     */
    public int getCapacity(){
        return this.data.length;
    }

    /**
     *          
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    /**
     *      index       
     * @param index
     * @param e
     */
    public void add(int index, T e){
        if (index < 0 || index > this.size){
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size");
        }
        //     data              ，    
        if (this.size == this.data.length){
            resize(2 * this.data.length);
        }
        for (int i = size - 1; i >= index; i--){
            this.data[i + 1] = data[i];
        }
        this.data[index] = e;
        this.size ++;
    }


    /**
     *              
     * @param e
     */
    public void addLast(T e){
        this.add(size, e);
    }

    /**
     *              
     * @param e
     */
    public void addFirst(T e){
        this.add(0, e);
    }

    /**
     *             e
     * @param index
     * @return
     */
    public T get(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        return this.data[index];
    }

    /**
     *             e
     * @param e
     * @param index
     */
    public void set(T e, int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        this.data[index] = e;
    }

    /**
     *                e
     * @param e
     * @return
     */
    public boolean contains(T e){
        for (int i = 0; i < size; i++){
            if (data[i] == e){
                return true;
            }
        }
        return false;
    }

    /**
     *         e     ，    e     -1
     * @param e
     * @return
     */
    public int find(T e){
        for (int i = 0; i < size; i++){
            if (data[i].equals(e) ){
                return i;
            }
        }
        return -1;
    }

    /**
     *       index      ，       
     * @param index
     * @return
     */
    public T remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        T ret  =  this.data[index];
        for (int i = index + 1; i < this.size; i++){
            this.data[i - 1] = this.data[i];
        }
        this.size --;
        this.data[size] = null;
        //     data              1/2 ，    
        if (this.size == this.data.length / 2){
            resize(this.data.length / 2);
        }
        return ret;
    }

    /**
     *            ，       
     * @return
     */
    public T removeFirst(){
        return this.remove(0);
    }

    /**
     *             ，       
     * @return
     */
    public T removeLast(){
        return this.remove(this.size -1);
    }

    /**
     *        
     * @param e
     */
    public boolean removeElement(T e){
        int index = this.find(e);
        if (index != -1){
            this.remove(index);

        }
        return false;
    }

    private void resize(int newCapacity) {
        T[] newData = (T[]) new Object[newCapacity];
        for (int i = 0; i < this.size; i++){
            newData[i] = this.data[i];
        }
        this.data = newData;
    }

    @Override
    public String toString() {
        StringBuffer rs = new StringBuffer();
        rs.append(String.format("Array List: size = %d, capacity = %d
", this.size, this.data.length));
        rs.append("[");
        for (int i = 0; i < this.size; i ++){
            rs.append(this.data[i]);
            if (i != size -1){
                rs.append(", ");
            }
        }
        rs.append("]");
        return rs.toString();
    }
}

 
手順表の各種操作時間複雑度分析

追加操作

 addLast(e):O(1)

addFirst(e):O(n)

add（index，e）：O（n）

resize:O(n)

変更操作

set:O(1)

削除操作

removeLast:O(1)

RemoveFirst:O(1)

Remove:O(n)

検索操作

get(index):O(1)

contains(e):O(n)

find(e):O(n)