Java數據結構-線性表之單鏈表LinkedList

線性表的鏈式存儲結構，也稱之為鏈式表，鏈表；鏈表的存儲單元可以連續也可以不連續。
鏈表中的節點包含數據域和指針域，數據域為存儲數據元素信息的域，指針域為存儲直接後繼位置（一般稱為指針）的域。

注意一個頭結點和頭指針的區別：
頭指針：

• 指向鏈表的第一個節點的指針，若鏈表有頭結點，則是指向頭結點的指針；
• 頭指針具有標識作用，所以常用頭指針作為鏈表的名字；
• 不論鏈表是否為空，頭指針都不為空；
• 是鏈表的必要元素。

頭結點：

• 頭結點是為了操作的統一和方便而設立的，放在第一個元素節點的前面，其數據域一般無意義，也可以存放鏈表的長度；
• 頭結點不是鏈表的必要元素。

這裡先講講單鏈表吧，其他的後面再講。
無頭結點的鏈表

有頭結點的鏈表

空鏈表

我試著用Java寫了一個LinkedList的代碼，如下：

  package com.phn.datestructure;

/**
 * @author 潘海南
 * @Email [email protected]
 * @TODO 鏈式表
 * @date 2015年7月18日
 */
public class FOLinkedList<E> {
    //  單鏈表的頭結點
    private FOLinkedNode<E> header = null;
    //  單鏈表的長度
    private int size;

    /**
     * @TODO 默認的無參構造函數
     */
    public FOLinkedList() {
        super();
        this.header = new FOLinkedNode<E>();
        this.setSize();
    }
    /**
     * @TODO 單鏈表添加元素
     * @param e 數據元素類型
     * @return true
     */
    public boolean add(E e) {
        FOLinkedNode<E> node = new FOLinkedNode<E>(e);
        if (header.getE() == null) {
            header.setE(e);
        } else {
            FOLinkedNode<E> lastNode = this.last(this.header);
            lastNode.addNext(node);
        }

        this.size++;
        return true;
    }
    /**
     * @TODO 單鏈表插入元素
     * @param index 插入位置
     * @param e 數據元素類型
     * @return true
     */
    public boolean insert(int index,E e) {
        FOLinkedNode<E> node = new FOLinkedNode<E>(e);
        FOLinkedNode<E> preNode = this.get(index - 1);
        node.addNext(preNode.next);
        preNode.addNext(node);
        this.size++;
        return true;
    }
    /**
     * @TODO 單鏈表刪除元素
     * @param index 將要刪除的元素的索引位置
     * @return E 刪除的元素
     */
    public FOLinkedNode<E> remove(int index){
        FOLinkedNode<E> preNode = this.get(index-1);
        FOLinkedNode<E> node = preNode.next;
        preNode.addNext(preNode.next.next);
        node.addNext(null);
        this.size--;
        return node;
    }
    /**
     * @TODO 根據元素索引位置獲取元素
     * @param index 元素的索引位置
     * @return E 元素e
     */
    public FOLinkedNode<E> get(int index) {
        validateIndex(index);
        FOLinkedNode<E> temp = this.header;
        int i = 0;
        while (i < index - 1) {
            if (temp != null) {
                temp = temp.next;
                i++;
            } else {
                throw new RuntimeException("節點空值錯誤");
            }
        }
        return temp;
    }
    /**
     * @TODO 將單鏈表中索引位置為i的元素修改為元素e
     * @param index 元素的索引位置
     * @param e 需要修改成的元素
     * @return true 修改成功標志
     */
    public boolean set(int index, E e){
        validateIndex(index);
        FOLinkedNode<E> oldNode = this.get(index);
        oldNode.setE(e);
        return true;
    }
    /**
     * @TODO 驗證所給索引位置是否合法
     * @param index 給出的索引位置
     */
    private void validateIndex(int index) {
        if (index > this.size || index < 0) {
            throw new RuntimeException("索引錯誤：" + index);
        }
    }
    /**
     * @TODO 獲取單鏈表的最後一個節點
     * @param header 單鏈表的頭結點
     * @return node 單鏈表的最後一個節點
     */
    private FOLinkedNode<E> last(FOLinkedNode<E> header) {
        FOLinkedNode<E> temp = header;
        while (true) {
            if (temp.next == null) {
                return temp;
            }
            temp = temp.next;
        }
    }

    @Override
    public String toString() {
        return "[" + this.NodesToString(this.header) + "]";
    }
    /**
     * @TODO 設置單鏈表的長度
     * @param header 單鏈表的頭結點
     * @return 單鏈表的節點字符串序列
     */
    private String NodesToString(FOLinkedNode<E> header) {
        StringBuffer sb = new StringBuffer();
        if (header != null) {
            sb.append(header.getE());
            FOLinkedNode<E> temp = new FOLinkedNode<E>();
            temp = header.next;
            while (temp != null) {
                sb.append(", " + temp.getE());
                temp = temp.next;
            }
        }

        return sb.toString();
    }
    /**
     * @TODO 設置單鏈表的長度
     */
    private void setSize() {
        this.size = 0;
    }
    /**
     * @TODO 獲取單鏈表的長度
     * @return size 單鏈表的長度
     */
    public int size() {
        return this.size;
    }
}

節點類：

package com.phn.datestructure;
public class FOLinkedNode<E> {
        private E e;// 結點中存放的數據

        FOLinkedNode() {
        }

        FOLinkedNode(E e) {
            this.e = e;
        }

        FOLinkedNode<E> next;// 用來指向該結點的下一個結點

        // 設置下一節點的值
        void addNext(FOLinkedNode<E> node) {
            next = node;
        }

        public E getE() {
            return e;
        }

        public void setE(E e) {
            this.e = e;
        }

        @Override
        public String toString() {
            return "Node [e=" + e + ", next=" + next + "]";
        }

    }

這裡也講講數據元素的插入和刪除操作；
插入操作演示如下：



代碼：

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

這裡摘了《大話數據結構》的一段文字解釋：

刪除操作如下圖：

一句代碼：

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

結合上述代碼和圖例，可以看出單鏈表的刪除和插入操作都是由兩部分組成：

1. 遍歷查找到需要操作的位置的那個元素；
2. 然後進行插入和刪除操作。

下面是摘自《大話數據結構》的分析：

單鏈表的整表創建
方法有頭插法和尾插法；
頭插法：相當於插隊的方法。如下圖

相對於頭插法，尾插法更加合理一些。

單鏈表的整表刪除
下面是摘自《大話數據結構》的分析：

下面比較一下單鏈表和順序表：