單鏈表(可以用來實現(xiàn)棧和隊列)

    private class Node {
        /**
         * 鏈表存儲的數(shù)據(jù)(泛型)
         */
        Item item;
        /**
         * 指向下一個節(jié)點的指針
         */
        Node next;
    }

刪除鏈表的元素

image.png

添加元素

image.png

雙向鏈表(實現(xiàn)LinkedList)

  /**
     * 鏈表節(jié)點
     * @param <AnyType> 
     */
    private static class Node<AnyType> {
        /**
         * @param d 數(shù)據(jù)
         * @param p 上一個節(jié)點
         * @param n 下一個節(jié)點
         */
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
            data = d;
            prev = p;
            next = n;
        }

        /**
         * 數(shù)據(jù)
         */
        public AnyType data;
        /**
         * 上一個節(jié)點
         */
        public Node<AnyType> prev;
        /**
         * 下一個節(jié)點
         */
        public Node<AnyType> next;
    }

image.png

添加元素

image.png

    /**
     * 向目標(biāo)元素p之前插入x
     *
     * @param p 目標(biāo)p
     * @param x 插入的元素
     */
    private void addBefore(Node<AnyType> p, AnyType x) {
        /*構(gòu)建一個新node,prev是p.prev,next是p  1,3*/
        Node<AnyType> newNode = new Node<>(x, p.prev, p);
        /*新node的上一個節(jié)點的next 指向自己 2*/
        newNode.prev.next = newNode;
        /*p的prev 指向自己 4*/
        p.prev = newNode;
        theSize++;
        modCount++;

    }

刪除元素

image.png

    /**
     * 刪除目標(biāo)節(jié)點
     *
     * @param p 目標(biāo)節(jié)點
     * @return 刪除的數(shù)據(jù)
     */
    private AnyType remove(Node<AnyType> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        return p.data;
    }