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

單向連結清單是一種十分基礎的資料結構，是線性表的一種，為了更清楚一點，今天使用java将其實作，實作過程如下

定義節點

/*
 * 節點類
 * 
 */
public class Node {
    Object data;//存儲節點資料
    Node next;//指向下一節點
}
           

定義操作

public interface LinKed {

    public Node get(int p);

    public void Insert(int p, Object data);

    public void delete(int p);

    public void clean();

    public int size();

}
           

實作單向連結清單

public class SingleLinked implements LinKed {
    private Node head;// 頭節點
    private int length;// 連結清單長度
    /*
     * 初始化連結清單
     */

    public SingleLinked() {
        head = null;
        length = ;
    }

    /*
     * 清空連結清單
     */
    public void clean() {
        head = null;
        length = ;
    }

    /*
     * 擷取連結清單第p個節點
     */
    public Node get(int p) {
        Node current = head;
        if (p >  && p <= length) {
            for (int i = ; i < p - ; i++) {
                current = current.next;
            }
            return current;
        }
        return null;

    }

    /*
     * 插入節點頭插法
     */
    public void headInsert(Object data) {
        Node n = new Node();
        n.data = data;
        n.next = head;
        head = n;
        length++;

    }

    /*
     * 插入節點在p節點
     */
    public void Insert(int p, Object data) {
        Node current = head;
        Node n = new Node();
        n.data = data;
        if (p >  && p <= length + ) {

            for (int i = ; i < p - ; i++) {

                current = current.next;
            }

            n.next = current.next;
            current.next = n;
            length++;

        }

    }

    /*
     * 删除第p個節點
     */
    public void delete(int p) {
        Node current = head;

        // 周遊連結清單直到p節點的前一節點
        if (p >  && p <= length) {
            if (p == ) {// 若删除的是頭節點
                head = current.next;
                length--;
                return;
            } else {
                for (int i = ; i <= p; i++) {

                    if (i == p - ) {
                        current.next = current.next.next;
                        length--;
                    } else {
                        current = current.next;
                    }

                }
            }

        }
    }

    /*
     * 列印連結清單
     */
    public void print() {
        Node current = head;
        for (int i = ; i < length; i++) {
            System.out.print(current.data + "-->");
            current = current.next;
        }
        System.out.println();
    }

    @Override
    public int size() {

        return this.length;
    }

}
           

測試

public class Test {

    public static void main(String[] args) {
        SingleLinked sl = new SingleLinked();
        sl.headInsert("a1");
        sl.headInsert("a2");
        sl.headInsert("a3");
        sl.headInsert("a4");
        sl.print();
        sl.delete();
        sl.print();
        System.out.println(sl.get().data);
        sl.Insert(, "a5");
        sl.print();
        sl.Insert(, "a6");
        sl.print();

    }

}