线性表的链式存储--双向链表

双向链表：

单链表的每个结点中，再设置一个指向其前驱结点的指针域。
存在两个指针域，一个指向直接后继，另一个人指向直接前驱。

结点数据结构：

    private static class LinkedNode<E> {

        //前驱结点
        private LinkedNode<E> pre;

        //后继结点
        private LinkedNode<E> next;

        //数据
        private E item;

        public LinkedNode(LinkedNode<E> pre, LinkedNode<E> next, E item) {
            this.pre = pre;
            this.next = next;
            this.item = item;
        }
    }

参数定义：

    //第一结点
    LinkedNode<E> first;

    //最后一个结点
    LinkedNode<E> last;

    //链表数据量
    private int size;

元素个数：

    public int size() {
        return size;
    }

判断是否为空：

    public Boolean isEmpty() {
        return size == 0;
    }

获取元素下标：

    public int indexOf(Object o) {
        int index = 0;

        //循环判断
        if (o == null) {
            for (LinkedNode<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (LinkedNode<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    return index;
                }
                index++;
            }

        }
        return -1;
    }

判断是否包含某个元素：

    public Boolean contains(Object o) {
        return indexOf(o) != -1;
    }

获取指定下标数据：

    public E get(int index) {

        //判断下标是否越界
        if (index < 0 || index > size) {
            throw new RuntimeException("下标不正确");
        }

        //减少循环次数，从头向后，或者从后向前判断
        if (index < (size >> 1)) {
            LinkedNode<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }

            return x.item;

        } else {

            LinkedNode<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.pre;
            }

            return x.item;

        }

    }

插入--头插法：

    public void addFirst(E e) {

        LinkedNode<E> linkedNode = first;
        LinkedNode<E> newNode = new LinkedNode<>(null, first, e);

        first = newNode;
        if (linkedNode == null) {
            last = newNode;
        } else {
            linkedNode.pre = newNode;
        }

        size++;

    }

插入--尾插法：

 private void addLast(E e) {
        LinkedNode<E> linkedNode = last;
        LinkedNode<E> newNode = new LinkedNode<>(last, null, e);
        last = newNode;
        if (linkedNode == null) {
            first = newNode;
        } else {
            linkedNode.next = newNode;
        }

        size++;
    }

删除：

    public Boolean remove(Object o) {

        if (o == null) {
            for (LinkedNode<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (LinkedNode<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }

        }

        return false;
    }

    private void unlink(LinkedNode<E> linkedNode) {

        //前驱是空，说明为第一个元素
        LinkedNode<E> pre = linkedNode.pre;
        LinkedNode<E> next = linkedNode.next;
        if (pre == null) {
            first = next;
        } else {
            pre.next = next;
            linkedNode.pre = null;
        }

        //猴急为空，说明为最后一个结点
        if (next == null) {
            last = pre;
        } else {
            next.pre = pre;
            linkedNode.next = null;

        }

        linkedNode.item = null;
        size--;
    }

清空：

    public void clear() {

        for (LinkedNode<E> x = first; x != null; ) {

            LinkedNode<E> next = x.next;
            x.item = null;
            x.pre = null;
            x.next = null;

            x = next;
        }
        first = last = null;
        size = 0;

    }