Java數據結構-線性表之靜態鏈表

靜態鏈表的定義：
節點由一個一維數組和一個指針域組成，數組用來存放數據元素，而指針域裡面的指針（又稱游標）用來指向下一個節點的數組下標。這樣的鏈表稱之為靜態鏈表。
鏈表中的數組第一個和最後一個位置需要特殊處理，不存數據。第一個位置（即數組0下標）的節點的指針用來存放備用鏈表的第一個節點的數組下標。最後一個位置（即數組長度MaxSize-1下標）的節點的指針用來存放指向有數值的第一個數據元素的數組下標，類似於單鏈表的頭結點。

靜態鏈表的示例圖：

下面舉一個摘抄自《大話數據結構》的例子，來解釋一下靜態數據鏈表。

下面介紹靜態鏈表的插入和刪除操作：
這裡我畫了一張圖，簡單的描述了一下，相信應該容易理解，如下：

同樣刪除的示例圖如下：

下面貼一下我用Java實現的代碼，主要功能只實現了插入和刪除操作：

package com.phn.datestructure;
/**
 * @author 潘海南
 * @Email [email protected]
 * @TODO 靜態鏈表 
 * @date 2015年7月19日
 */
public class FOStaticList<E> {
    //靜態鏈表的長度
    private int size;
    //靜態鏈表的容量,實際容量為capacity-2：capacity-頭結點-備用頭結點=capacity-2
    private int capacity;
    //備用鏈表的頭結點
    private FOStaticNode<E> backNode= null;
    //備用鏈表在數組中的位置，默認為第一個，即為0
    private int backNodeIndex = 0;
    //靜態鏈表的頭結點，即靜態鏈表數據元素鏈的頭結點
    private FOStaticNode<E> headerNode = null;
    //靜態鏈表的存儲數據元素的數組
    private FOStaticNode<E>[] fosn = null;
    //默認容量
    private static final int DEFUALT_CAPACITY = 100;

    public FOStaticList(){
        this(DEFUALT_CAPACITY);
    }
    /**
     * @TODO 帶參構造函數，用來初始化賦值靜態鏈表，並進行相關容量和大小的設置
     * @param initialCapacity 靜態鏈表的初始化容量 
     */
    public FOStaticList(int initialCapacity) {
        this.init(initialCapacity);
        this.setCapacity(initialCapacity);
        this.setSize();
    }
    /**
     * @TODO 初始化賦值靜態鏈表，並設置靜態鏈表的頭結點和備用鏈表的頭結點
     * @param initialCapacity
     */
    private void init(int initialCapacity) {
        //判斷給定的初始化參數是否合法
        if (initialCapacity < 0) {
            throw new RuntimeException("數組大小錯誤:" + initialCapacity);
        }
        fosn = new FOStaticNode[initialCapacity];
        //給靜態鏈表賦值，內部的e=null，而游標設置為i+1
        for(int i = 0;i<initialCapacity-1;i++){
            fosn[i]  = new FOStaticNode<E>();
            fosn[i].setCursor(i+1);
        }
        fosn[initialCapacity-1] = new FOStaticNode<E>();
        //設置靜態鏈表的頭結點指向備用鏈表的數組下標，即initialCapacity-1的節點的游標為0
        fosn[initialCapacity-1].setCursor(backNodeIndex);
        //設置靜態鏈表的頭結點為headerNode
        this.setHeaderNode(fosn[initialCapacity-1]);
        //設置備用鏈表的頭結點為backNode
        this.setBackNode(fosn[backNodeIndex]);
    }
    /**
     * @TODO 靜態鏈表尾插法添加數據元素
     * @param e 要添加的數據元素
     * @return true
     */
    public boolean add(E e){
        //檢查鏈表的容量，並進行相應的擴容
        this.ensureCapacity(size);
        //將備用鏈表頭結點指向的游標（即備用鏈表的第一個位置）賦值給oldBackNodeCursor保存
        int oldBackNodeCursor = this.backNode.getCursor();
        if(size==0){
            /*若目前（即添加元素之前）靜態鏈表沒有數據元素，則將靜態鏈表的頭結點的游標指向
         *   “備用鏈表頭結點指向的游標對應的位置”，即備用鏈表的第一個元素位置*/
            this.headerNode.setCursor(oldBackNodeCursor);
        }else{
            //將靜態鏈表的頭結點指向的游標賦值給tempNodeCursor
            int tempNodeCursor = this.headerNode.getCursor();
            //下面的循環用來找到靜態鏈表（數據元素鏈）的最後一個元素節點lastNode
            FOStaticNode<E> lastNode = new FOStaticNode<E>();
            while(tempNodeCursor!=0){
                lastNode= this.fosn[tempNodeCursor];
                tempNodeCursor= this.fosn[tempNodeCursor].getCursor();
            }
            //將lastNode節點的指向游標設置值為備用鏈表的第一個位置
            lastNode.setCursor(oldBackNodeCursor);
        }
        //將備用鏈表的第一個位置設置數據元素為e
        this.fosn[oldBackNodeCursor].setE(e);
        //獲取備用鏈表的第一個位置指向的游標，並將其賦值給newBackNodeCursor（作為新的備用鏈表頭結點指向的游標）保存，
        int newBackNodeCursor = this.fosn[oldBackNodeCursor].getCursor();
        //設置備用鏈表的第一個位置（即目前作為靜態鏈表數據元素鏈的最後一個元素）指向的游標為備用鏈表的頭結點位置（默認0位置）
        this.fosn[oldBackNodeCursor].setCursor(backNodeIndex);
        //設置備用鏈表頭結點指向的游標為新的備用鏈表頭結點指向的游標newBackNodeCursor
        this.backNode.setCursor(newBackNodeCursor);
        //鏈表長度加1
        this.size++;
        return true;
    }
    /**
     * @TODO 根據提供的index來刪除靜態鏈表中的第index個元素
     * @param index 靜態鏈表中的第index個元素
     * @return true or false
     */
    public boolean remove(int index){
        //判斷給出的元素位置是否合法；this.capacity-2表示靜態鏈表能夠達到的最大長度：capacity-頭結點-備用頭結點=capacity-2
        if(index<1 || index>this.capacity-2){
            System.out.println("不存在此位置的元素");
            return false;
        }
        //聲明變量preRemoveCursor用來作為將要刪除的數據元素數組的下標，或者稱為將要刪除的數據元素的前一個節點指向的游標。
        int preRemoveCursor = this.headerNode.getCursor();
        //下面的循環用來找出刪除的數據元素的前一個節點preRemoveNode和將要刪除的數據元素的前一個節點指向的游標preRemoveCursor
        FOStaticNode<E> preRemoveNode = new FOStaticNode<E>();
        int tempCount = 0;
        while(tempCount!=index-1){
            preRemoveNode = this.fosn[preRemoveCursor];
            preRemoveCursor = preRemoveNode.getCursor();
            tempCount++;
        }
        //聲明變量oldBackNodeCursor作為備用鏈表的頭結指向的游標並賦值保存。
        int oldBackNodeCursor = this.backNode.getCursor();
        //設置備用鏈表的頭結點指向的游標為 將要刪除的數據元素數組的下標 preRemoveCursor
        this.backNode.setCursor(preRemoveCursor);
        //將將要刪除的數據元素指向的游標賦值給removeCursor並保存
        int removeCursor = this.fosn[preRemoveCursor].getCursor();
        //將將要刪除的數據元素指向的游標設置為備用鏈表的頭結指向的游標oldBackNodeCursor
        this.fosn[preRemoveCursor].setCursor(oldBackNodeCursor);
        //將將要刪除的數據元素設置為null，即刪除
        this.fosn[preRemoveCursor].setE(null);
        //將將要刪除的數據元素的前一個節點指向的游標設置為將要刪除的數據元素指向的游標removeCursor
        preRemoveNode.setCursor(removeCursor);
        //長度減1
        this.size--;
        return true;
    }


    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("[ ");
        int currentCursor = this.headerNode.getCursor();
        if(currentCursor!=backNodeIndex){
            sb.append(currentCursor+""+this.fosn[currentCursor]);
            currentCursor = this.fosn[currentCursor].getCursor();
            while(currentCursor!=backNodeIndex){
                sb.append(", "+currentCursor+""+this.fosn[currentCursor]);
                currentCursor = this.fosn[currentCursor].getCursor();
            }
        }
        return sb.append(" ]").toString();
    }
    /**
     * @TODO 判斷靜態鏈表的容量是否超過，並進行相應的擴容操作。
     * 注意：這裡最主要的是將當前靜態鏈表數組下標最後一個位置的游標保存起來，即將頭結點指向的游標保存起來；
     * 然後賦值給新的靜態鏈表的頭結點指向的游標。
     * @param currentSize 當前長度
     */
    private void ensureCapacity(int currentSize) {
        if(currentSize == this.capacity-2){
            int oldCapacity = this.capacity;
            //這裡我是按照ArrayList的擴容來進行的，擴大約1.5倍左右。
            this.capacity = (this.capacity * 3) / 2 + 1;
            FOStaticNode<E>[] newData = new FOStaticNode[this.capacity];
            for (int i = 0; i < oldCapacity-1; i++) {
                newData[i] = this.fosn[i];
            }
            newData[capacity-1]  = new FOStaticNode<E>();
            newData[capacity-1].setCursor(this.fosn[oldCapacity-1].getCursor());
            for(int i = oldCapacity-1;i<this.capacity-1;i++){
                newData[i]  = new FOStaticNode<E>();
                newData[i].setCursor(i+1);
            }
            this.fosn = newData;
        }
    }
    /**
     * @return the size
     */
    public int size() {
        return size;
    }
    private void setSize() {
        this.size=0;
    }
    /**
     * @param backNode the backNode to set
     */
    private void setBackNode(FOStaticNode<E> backNode) {
        this.backNode = backNode;
    }
    /**
     * @param headerNode the headerNode to set
     */
    private void setHeaderNode(FOStaticNode<E> headerNode) {
        this.headerNode = headerNode;
    }
    /**
     * @param capacity the capacity to set
     */
    private void setCapacity(int capacity) {
        this.capacity = capacity;
    }

}

在舉一個刪除的示例圖，請聯系我的代碼進行操作，
首先寫個測試的方法

public static void main(String[] args) {
    FOStaticList<String> fosl = new FOStaticList<String>(6);
    fosl.add("元素1");
    System.out.println(fosl);
    fosl.add("元素2");
    fosl.add("元素3");
    System.out.println(fosl);
    fosl.add("元素4");
    System.out.println(fosl);
    System.out.println(fosl.size());
    fosl.remove(2);
    System.out.println(fosl);
}

運行測試方法，結合下圖應該可以比較好的理解。

最��說說靜態鏈表的優缺點。