Java資料結構——單向連結清單實作

/**
 * 單向連結清單實作類
 * @Description
 * 類描述：
 * @author GaoAnQiu
 * @Date 
 * @modify
 * 修改記錄：
 *
 */
public class Link {

    private int size = 0;
    private Node first;
    private Node last;

    public Node getFirst() {
        return first;
    }

    public void setFirst(Node first) {
        this.first = first;
    }

    public Node getLast() {
        return last;
    }

    public void setLast(Node last) {
        this.last = last;
    }

    public Link() {

    }

    /**
     * 傳回連結清單長度
     * @Description
     * 方法描述:
     * @return 傳回類型： int
     * @return
     */
    public int getLength() {
        return size;
    }

    public void printLink(Link link) {
        Node temp = first;
        while (temp != null) {
            System.out.print(temp.getData() + "-->");
            temp = temp.getNext();
        }
        System.out.println();
    }

    /**
     * 傳回指定位置的節點
     * @Description
     * 方法描述:
     * @return 傳回類型： Node
     * @param index
     * @return
     */
    public Node get(int index) {
        Node temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 插入第一個元素，頭和尾都指向同一個元素
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     */
    private void onetNode(int element) {
        first = new Node();
        first.setData(element);
        last = first;
    }

    public void addHead(int element) {
        if (size == 0) {
            onetNode(element);
        } else {
            Node node = new Node();
            node.setData(element);
            node.setNext(first);
            first = node;
        }
        size++;
    }

    /**
     * 插入尾結點
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     * @param element
     */
    public void addTail(int element) {
        if (size == 0) {
            onetNode(element);
        } else {
            Node node = new Node();
            node.setData(element);
            last.setNext(node);
            last = node; //将插入的結點設定為尾結點
            size++;
        }
    }

    /**
     * 插入中間元素
     * 頭尾兩處需要特殊處理
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (index > size) {
            throw new IndexOutOfBoundsException("待插入的位置超過連結清單的最大長度。");
        } else {
            if (index == 0) {
                //下标為0時，插入頭元素
                addHead(element);
            } else if (size == index) {
                //下标與連結清單長度一緻時，插入尾元素
                addTail(element);
            } else {
                Node preNode = get(index - 1); //
                Node nextNode = get(index);
                Node newNode = new Node();
                newNode.setData(element);
                preNode.setNext(newNode);
                newNode.setNext(nextNode);
                size++;
            }
        }
    }

    /**
     * 删除頭節點
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     */
    public void delHead() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("空連結清單，無元素可删除");
        } else {
            if (size == 1) {
                //隻有一個節點時，清空連結清單
                clear();
            } else {
                Node nextNode = first.getNext();
                first = nextNode;
            }
            size--;
        }
    }

    /**
     * 清空連結清單
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     */
    public void clear() {
        first = last = null;
        size = 0;
    }

    public void delTail() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("空連結清單，無可删除的元素。");
        } else if (size == 1) {
            clear();
        } else {
            //取出尾節點的前一個節點，next指派為null
            Node preTail = get(size - 2);
            preTail.setNext(null);
            last = preTail;
            size--;
        }
    }

    /**
     * 删除節點
     * @Description
     * 方法描述:
     * @return 傳回類型： void
     * @param index
     */
    public void del(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("删除位置越界");
        } else {
            if (index == 0) {
                delHead();
            } else if (index == size - 1) {
                delTail();
            } else {
                Node preNode = get(index - 1);
                Node nextNode = get(index + 1);
                preNode.setNext(nextNode);
                size--;
            }
        }
    }

}
           

public class Node {

    private int data;//資料
    private Node next;//指針

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}