单链表和双链表

单链表(可以用来实现栈和队列)

    private class Node {
        /**
         * 链表存储的数据(泛型)
         */
        Item item;
        /**
         * 指向下一个节点的指针
         */
        Node next;
    }

删除链表的元素

image.png

添加元素

image.png

双向链表(实现LinkedList)

  /**
     * 链表节点
     * @param <AnyType> 
     */
    private static class Node<AnyType> {
        /**
         * @param d 数据
         * @param p 上一个节点
         * @param n 下一个节点
         */
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) {
            data = d;
            prev = p;
            next = n;
        }

        /**
         * 数据
         */
        public AnyType data;
        /**
         * 上一个节点
         */
        public Node<AnyType> prev;
        /**
         * 下一个节点
         */
        public Node<AnyType> next;
    }

image.png

添加元素

image.png

    /**
     * 向目标元素p之前插入x
     *
     * @param p 目标p
     * @param x 插入的元素
     */
    private void addBefore(Node<AnyType> p, AnyType x) {
        /*构建一个新node,prev是p.prev,next是p  1,3*/
        Node<AnyType> newNode = new Node<>(x, p.prev, p);
        /*新node的上一个节点的next 指向自己 2*/
        newNode.prev.next = newNode;
        /*p的prev 指向自己 4*/
        p.prev = newNode;
        theSize++;
        modCount++;

    }

删除元素

image.png

    /**
     * 删除目标节点
     *
     * @param p 目标节点
     * @return 删除的数据
     */
    private AnyType remove(Node<AnyType> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        return p.data;
    }