手寫 LinkedList（雙向連結清單）

文章目錄

• • • 1、MyList 接口
    • 2、MyLinkedList 實作類
    • 3、Student 測試實體類
    • 4、測試類

1、MyList 接口

/**
 * 用于 LinkedList 繼承
 *
 * @param <E>
 */
public interface MyList<E> {

    /**
     * 将指定節點追加到此清單的末尾
     *
     * @param element : 節點中存儲的資料
     * @return : 傳回是否插入成功 boolean
     */
    public boolean add(E element);

    /**
     * 在此清單中的指定位置插入指定節點。
     * 目前處于移動中的節點（如果有）和右方的任何後續節點（向其索引添加節點）移動。
     *
     * @param index   : 要添加的節點位置
     * @param element : 節點中存儲的資料
     */
    public void add(int index, E element);

    /**
     * 擷取指定索引位置的節點
     *
     * @param index : 要擷取的節點位置
     * @return : 傳回擷取的節點資料 element
     */
    public E get(int index);

    /**
     * 替換指定索引位置的節點
     *
     * @param index   : 要替換的節點位置
     * @param element : 要替換的節點資料 element
     * @return : 傳回舊的節點資料 element
     */
    public E set(int index, E element);

    /**
     * 移除指定索引位置的節點
     *
     * @param index : 要移除的節點位置
     * @return : 傳回被移除的節點資料 element
     */
    public E remove(int index);

    /**
     * 擷取 LinkedList 大小, 即 index + 1
     *
     * @return
     */
    public int size();

    /**
     * 清空連結清單
     */
    public void clear();

}
           

2、MyLinkedList 實作類

public class MyLinkedList<E> implements MyList<E> {

    /**
     * 0.01 連結清單頭節點
     */
    private Node head;

    /**
     * 0.02 連結清單尾節點
     */
    private Node tail;

    /**
     * 0.03 MyLinkedList 的大小（它包含的Node數）
     */
    private int size;

    /**
     * 0.04 初始化雙向連結清單結構
     */
    public MyLinkedList() {

    }

    /**
     * 1.00 将 element 作為最後一個節點進行連接配接
     *
     * @param element
     */
    void linkLast(E element) {
        //① 擷取連結清單尾節點
        Node<E> t = tail;

        //② 建立一個 Node 節點, 并将 element 資料放入其中,
        // 該 Node 節點的上一個連結指向舊的 “tail 連結清單尾節點”,
        // 該 Node 節點的下一個連結指向 null 節點
        Node<E> newNode = new Node<>(t, element, null);

        //③ 将 ”新的 Node 節點“ 作為 “tail 連結清單尾節點”
        tail = newNode;

        //④ 判斷 舊的 “tail 連結清單尾節點” 是否存在
        if (t == null) {
            //⑤ 不存在, 将 ”新的 Node 節點“ 作為 “head 連結清單頭節點”
            head = newNode;
        } else {
            //⑥ 存在, 将 ”① 擷取連結清單尾節點 t“ 的下一個連結指向 ”新的 Node 節點“
            t.next = newNode;
        }
        //⑦ MyLinkedList 的大小（它包含的Node數）+ 1
        size++;
    }

    /**
     * 2.01 判斷 add() 方法的 index 是否合法
     *
     * @param index : 要處理的索引值
     */
    private void rangCheckForAdd(int index) {
        // 判斷 index 是否合法
        if (index < 0 || index > size) {
            // 抛出 數組下标越界異常.
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 2.02 判斷 index 是否合法
     *
     * @param index : 要處理的索引值
     */
    private void rangCheck(int index) {
        // 判斷 index 是否合法
        if (index < 0 || index >= size) {
            // 抛出 數組下标越界異常.
            throw new IndexOutOfBoundsException();
        }
    }


    /**
     * 2.03 在指定節點索引處傳回（非空）節點, 如 : Node<E> succ.
     *
     * @param index : 要添加的節點位置
     * @return : 傳回位置為 index 的 Node 節點
     */
    private Node<E> node(int index) {
        // assert isElementIndex(index);

        //① 要傳回的 Node 節點
        Node<E> x;

        //② 假定傳入的 index 小于 size/2
        if (index < (size >> 1)) {

            //③ 要傳回的 Node 節點 = ”連結清單頭“ 節點
            x = head;

            //④ 循環周遊, 直到找到位置為 index 的 Node 節點
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        } else {

            //⑤ 要傳回的 Node 節點 = ”連結清單尾“ 節點
            x = tail;
            //⑥ 循環周遊, 直到找到位置為 index 的 Node 節點
            for (int i = size - 1; i > index; i--) {
                x = x.previous;
            }
        }
        //傳回位置為 index 的 Node 節點
        return x;
    }

    /**
     * 2.03 在非空節點 succ 之前插入節點資料 element
     *
     * @param element : 要插入的節點資料  element
     * @param succ    : 在 Node<E> succ 前插入節點
     */
    private void linkBefore(E element, Node<E> succ) {
        //① 擷取 ”非空節點 succ“ 連結指向的上一個節點
        // assert succ != null;
        Node<E> prev = succ.previous;

        //② 建立一個 Node 節點, 并将 element 資料放入其中,
        // 該 Node 節點的上一個連結指向 ”非空節點 succ “ 連結指向的上一個節點,
        // 該 Node 節點的下一個連結指向 succ 節點
        Node<E> newNode = new Node<>(prev, element, succ);

        //③ ”非空節點 succ“ 的上一個連結指向 ”新的 Node 節點“
        succ.previous = newNode;

        //④ 判斷 ”①非空節點 succ “ 連結指向的上一個節點 是否存在
        if (prev == null) {
            //⑤ 不存在, 将 ”新的 Node 節點“ 作為 “head 連結清單頭” 節點
            head = newNode;
        } else {
            //⑥ 存在, 将 “ ”①非空節點 succ“ 連接配接的上一個節點的下一個節點連結” 指向 ”新的 Node 節點“
            prev.next = newNode;
        }
        //⑦ MyLinkedList 的大小（它包含的Node數）+ 1
        size++;
    }

    /**
     * 2.04 取消連結非空節點 x
     *
     * @param x : 要移除的 Node<E> x 節點
     * @return : 被移除的 Node<E> x 節點的 element 資料
     */
    private E unlink(Node<E> x) {
        // assert x != null;
        //① 擷取要移除的 Node<E> x 節點的 element 資料
        E element = x.element;
        //② 擷取要移除的 Node<E> x 節點連結指向的 下一個節點
        Node<E> next = x.next;
        //③ 擷取要移除的 Node<E> x 節點連結指向的 上一個節點
        Node<E> prev = x.previous;

        //④ 如果 Node<E> x 節點連結指向的上一個節點為空節點, 即: 為頭節點
        if (prev == null) {
            //⑤ 将頭節點設為 Node<E> x 節點連結指向 的下一個節點, 即: 目前節點的下一個節點
            head = next;
        } else { //⑥ 否則 Node<E> x 節點連結指向的上一個節點不是空節點
            //⑦ 将要移除的 Node<E> x 節點連結指向的 “上一個節點” 的下一個節點
            // 指向要移除的 Node<E> x 節點連結指向的 ”下一個節點“
            prev.next = next;
            //⑧ 将要移除的 Node<E> x 節點連結指向指向的 上一個節點連結 置為 null
            x.previous = null;
        }
        //④ 如果 Node<E> x 節點指向的下一個節點為空節點, 即: 為尾節點
        if (next == null) {
            //⑤ 将尾節點設為 Node<E> x 節點連結指向 的上一個節點, 即: 目前節點的上一個節點
            tail = prev;
        } else {  //⑥ 否則 Node<E> x 節點連結指向的下一個節點不是空節點
            //⑦ 将要移除的 Node<E> x 節點連結指向的 “下一個節點” 的上一個節點
            // 指向要移除的 Node<E> x 節點連結指向的 ”上一個節點“
            next.previous = prev;
            //⑧ 将要移除的 Node<E> x 節點連結指向的 下一個節點連結 置為 null
            x.next = null;
        }

        //⑨ 将将要移除的 Node<E> x 節點的 element 置為 null
        x.element = null;

        //⑩ MyLinkedList 的大小（它包含的Node數）-1
        size--;

        // 傳回被移除的 Node<E> x 節點的 element
        return element;
    }

    /**
     * 1.10 将指定節點追加到此清單的末尾
     *
     * @param element : 資料
     * @return
     */
    @Override
    public boolean add(E element) {
        //将 element 作為最後一個節點進行連接配接
        linkLast(element);
        return true;
    }

    /**
     * 2.10 在此清單中的指定位置插入指定節點。
     * 将目前位于該位置的節點（如果有）和右下的任何後續節點（向其索引添加一個節點）移位。
     *
     * @param index   : 要添加的節點位置
     * @param element : 節點存儲的 element 資料
     */
    @Override
    public void add(int index, E element) {

        //① 判斷 index 是否合法
        rangCheckForAdd(index);

        //② 如果 index 等于連結清單長度
        if (index == size) {

            //③ 直接追加到此清單的末尾
            linkLast(element);
        } else {

            //⑤ 在此清單中的指定位置插入
            linkBefore(element, node(index));
        }
    }

    /**
     * 2.11 擷取指定索引位置的節點存儲的 element 資料
     *
     * @param index : 要擷取的節點位置
     * @return : 傳回 Node 節點中存儲的 element 資料
     */
    @Override
    public E get(int index) {
        //① 判斷 index 是否合法
        rangCheck(index);

        //② 傳回 Node 節點中存儲的 element 資料
        return node(index).element;
    }

    /**
     * 2.12 替換指定索引位置的節點
     *
     * @param index   : 要替換的節點位置
     * @param element : 要替換的 節點資料
     * @return : 傳回 被替換的 Node 節點中的 element 資料
     */
    @Override
    public E set(int index, E element) {
        //① 判斷 index 是否合法
        rangCheck(index);

        Node<E> x = node(index);

        //② 擷取指定索引位置的 Node 節點中的 element 資料
        E oldValue = x.element;

        //③ 用 ”傳入的 element“ 替換對應索引中的 Node 節點中的 element 資料
        x.element = element;

        //⑤ 傳回被替換的 Node 節點中的 element 資料
        return oldValue;
    }

    /**
     * 2.13 移除指定索引位置的節點
     *
     * @param index : 要移除的節點位置
     * @return : 傳回 被移除的 Node 節點中的 element 資料
     */
    @Override
    public E remove(int index) {
        //① 判斷 index 是否合法
        rangCheck(index);

        //② 移除指定節點, 并傳回被移除節點的 element 資料
        return unlink(node(index));
    }

    /**
     * 2.14 MyLinkedList 的大小（它包含的 Node 數）
     *
     * @return : 傳回包含的 Node 數
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 2.15 清空 連結清單
     */
    @Override
    public void clear() {
        // 清除節點之間的所有連結是"不必要的"，但：
        // 如果丢棄的節點居住在多代，則幫助生成 GC
        // 一定要釋放記憶體，即使有一個可通路的疊代器
        //① 讓 x = head 連結清單頭, 隻要 x 不為 null 就一直周遊
        for (Node<E> x = head; x != null; ) {
            //② 取出目前節點連結指向的 下一個節點
            Node<E> next = x.next;
            //③ 将目前節點的 element 資料置為空
            x.element = null;
            //④ 将 目前節點與下一節點的連結 置為空
            x.next = null;
            //⑤ 将 目前節點與上一節點的連結 置為空
            x.previous = null;
            //⑤ 将目前節點替換為 下一節點
            x = next;
        }
        //⑥ 将 頭節點和尾節點 都置為 null
        head = tail = null;
        //⑦ 将 MyLinkedList 長度置為 0
        size = 0;
    }

    /**
     * 0.00 連結清單就是一系列存儲資料元素的單元通過指針串接起來形成的.
     * <p>
     * 雙向連結清單中的每個節點除了要儲存它的下一個節點對象的引用以外,
     * 還會儲存一個它前一個節點對象的引用，這樣就可以實作雙向查找資料.
     *
     * @param <E>
     */
    private static class Node<E> {

        /**
         * 0.00 用于資料元素的存儲
         */
        private E element;

        /**
         * 0.00 上一個節點對象的連結
         */
        private Node<E> previous;

        /**
         * 0.0 下一個節點對象的連結
         */
        private Node<E> next;

        Node(Node<E> previous, E element, Node<E> next) {
            this.previous = previous;
            this.element = element;
            this.next = next;
        }

    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("Size = " + size + ", Data = ").append("[");
        // 拼接第一個元素
        sb.append(this.head.element);

        Node node = this.head.next;
        // 擷取目前節點連結指向的下一個節點
        for (int i = 0; i < size - 1; i++) {
            sb.append(", " + node.element);
            node = node.next;
        }
        sb.append("]");

        return sb.toString();
    }
}
           

3、Student 測試實體類

public class Student {

    private int id;

    private String name;

    private String address;

    public Student(int id, String name, String address) {
        this.id = id;
        this.name = name;
        this.address = address;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public String getAddress() {
        return address;
    }

    @Override
    protected void finalize() {
        System.out.println("This desctory!");
    }

    @Override
    public String toString() {
        return "Student{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", Address='" + address + '\'' +
                '}';
    }
}
           

4、測試類

public class Test {

    public static void main(String[] args) {

        MyLinkedList<Student> list = new MyLinkedList<>();
        list.add(new Student(1, "梨花1", "龍門客棧1"));
        list.add(new Student(2, "梨花2", "龍門客棧2"));
        list.add(new Student(3, "梨花3", "龍門客棧3"));
        list.add(new Student(4, "梨花4", "龍門客棧4"));
        System.out.println("添加元素" + list);

        list.add(2, new Student(10, "梨花10", "龍門客棧10"));
        System.out.println("插入元素" + list);

        System.out.println("擷取指定索引位置的元素" + list.get(2));

        System.out.println("被替換的元素" + list.set(2, new Student(1000, "梨花1000", "龍門客棧1000")));
        System.out.println("替換完成的LinkedList" + list);

        System.out.println("被移除的元素" + list.remove(2));
        System.out.println("移除元素完成的LinkedList" + list);

        list.clear();
    }
}