資料結構--雙向連結清單實作（java）

package com.tt.model;
/****
 * 實作一個雙向連結清單
 * @author Gavin
 *
 */
public class LinkList<E> {
    private Node<E> first;
    private Node<E> last;

    private int size;


    public LinkList() {
        this();
    }
    public LinkList(int size) {
        super();
        this.size = size;
    }
    public int size(){
        return this.size;
    }
    /****
     * 在連結清單末尾添加一個節點
     * @param obj
     */
    public void add(E obj){
        if(this.first == null){
            //連結清單還沒産生時
            this.first = new Node<E>(null,obj,null);
            this.last = this.first;
        }else {
            //連結清單已經存在了
            this.last.next = new Node<E>(this.last,obj,null);
            this.last = this.last.next;
        }
        this.size++;
    }
    /****
     * 在指定位置添加一個節點
     * @param index
     * @param obj
     * @throws Exception 
     */
    public void add(int index,E obj) throws Exception{
        Node<E> node = node(index);
        Node<E> newNode = new Node<E>(node.pre,obj,node);
        Node<E> pre = node.pre;
        if(pre == null){//當node是頭結點的情況
            this.first = newNode;
        }else {
            pre.next = newNode;
        }
        node.pre = newNode;
        this.size++;
    }
    /****
     * 擷取指定位置節點
     * @param index
     * @throws Exception 
     */
    public E get(int index) throws Exception{
        Node<E> temp = node(index);
        if(temp == null){
            return null;
        }
        return temp.data;
    }
    /***
     * 移除指定位置節點(傳回被移除的資料)
     * @param index
     * @throws Exception 
     * 
     */
    public void remove(int index) throws Exception{
        remove(node(index));
    }
    /****
     * 移除某個對象的節點
     * @param obj
     * @throws Exception 
     */
    public void removeElement(E obj) throws Exception{
        remove(nodeElement(obj));
    }
    /****
     * 移除某個節點
     * @param obj
     */
    private void remove(Node<E> node){
        Node<E> pre = node.pre;
        Node<E> next = node.next;
        if(pre == null){//需要移除的節點沒有上一個節點（隻能是頭結點的情況）
            this.first = next;//将頭結點的下一節點，向前移動一格

            if(this.first != null){//有可能目前連結清單已經空了

                this.first.pre = null;//将頭節點的pre指派為空
            }
        }else if(next == null){//需要移除的節點沒有下一個節點（隻能是尾結點的情況）

            this.last = pre;//将目前尾結點的前一節點變成尾節點

            this.last.next = null;//将尾節點的next指派為空
        }else {//一般情況
            pre.next = next;
            next.pre = pre;
        }
        this.size--;
    }
    /****
     * 設定指定位置的值
     * @param index
     * @param obj
     * @throws Exception 
     */
    public void set(int index,E obj) throws Exception{
        node(index).data =obj;
    }
    /***
     * 擷取指定位置節點
     * @param index
     * @return
     * @throws Exception 
     */
    private Node<E> node(int index) throws Exception {
        checkIndex(index);
        Node<E> temp = this.first;
        for(int i = ;i<index;i++){
            temp = temp.next;
        }
        return temp;
    }
    /***
     * 根據對象擷取位置節點
     * @param index
     * @return
     * @throws Exception 
     */
    private Node<E> nodeElement(E obj) throws Exception {
        Node<E> temp = this.first;
        for(int i = ;i<this.size;i++){
            if(temp.data.equals(obj)){
                return temp;//找到節點跳出
            }
            temp = temp.next;
        }
        return null;
    }

    /***
     * 檢查傳入的下标是否越界
     * @param index
     * @throws Exception
     */
    private void checkIndex(int index) throws Exception{
        if(index <  || index >= this.size){
            throw new Exception("擷取資料錯誤，數組越界");
        }
    }
    /****
     * 主函數--測試用
     * @param args
     * @throws Exception 
     */
    public static void main(String[] args) throws Exception {
        LinkList list = new LinkList();
        list.add("111");
        list.add("222");
        list.add("333");
        list.add("44444");
        list.add();
        list.add();
        list.remove();
        list.removeElement();
        list.add(,"xxxxxx");
        list.set(, "yyyyyy");
        System.out.println("size === "+list.size());
        for (int i = ;i<list.size();i++) {
            System.out.println("get("+i+") === "+list.get(i));
        }
        //System.out.println("get(99) === "+list.get(99));//越界
    }
}

           

package com.tt.model;

public class Node<E> {
        Node<E> pre;
        Node<E> next;
        E data;

        public Node() {
            super();
        }
        public Node(Node<E> pre, E data ,Node<E> next) {
            super();
            this.pre = pre;
            this.next = next;
            this.data = data;
        }

}