手写双向链表

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

根据自己需求写对应的链表存储 可以节约内存空间，不必使用一些用不到算法。

/**
 * Created by zqb on 2019/5/21
 */
public class LinkedList<E> {
    /**
     * 节点
     *
     * @param <E>
     */
    private static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    public LinkedList() {

    }

    //头节点 尾节点
    private Node<E> first;
    private Node<E> last;
    //大小
    int size;

    /**
     * 添加数据到最后
     */
    public void add(E e) {
        linkLast(e);
    }

    /**
     * 添加数据在index 位置
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == size) {//如果添加到最后
            linkLast(e);
        } else {
            //查找当前位置所在的节点
            Node<E> target = node(index);
            //原节点的上一节点
            Node<E> pre = target.prev;
            //更新新节点的上一节点
            Node<E> newNode = new Node<>(pre, e, target);
            if (pre == null) { //如何添加的位置 为0  前位置为null
                first = newNode;
                //更新原位置节点的上一个节点
                target.prev = newNode;
            } else {
                //更新原前节点的下一个节点
                pre.next = newNode;
                //更新原位置节点的上一个节点
                target.prev = newNode;
            }
            size++;
        }
    }

    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        Node<E> l = last;
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 查找位置
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        return node(index).item;

    }

    /**
     * 获取index位置上的节点
     *
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        //如果index 在整个链表的前半部分
        if (index < (size / 2)) {//size >>1
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }

    }

    /**
     * 获取数据e位置上的节点
     *
     * @param e
     * @return
     */
    private Node<E> node(E e) {
        Node<E> node = first;
        boolean isHaveNode = false;
        for (int i = 0; i < size; i++) {
            if (node.item == e) {
                isHaveNode = true;
                break;
            }
            node = node.next;
        }
        if (isHaveNode) {
            return node;
        } else {
            return null;
        }
    }

    /**
     * 删除元素 根据index
     */
    public void remove(int index) {
        Node<E> target = node(index);
        unLinkNode(target);
    }

    /**
     * 删除元素
     */
    public void remove(E e) {
        Node<E> target = node(e);
        unLinkNode(target);
    }

    /**
     * 删除节点
     *
     * @param target
     */
    private void unLinkNode(Node<E> target) {
        if (target == null) {
            System.out.println("没有该数据");
            return;
        }
        Node<E> pre = target.prev;
        Node<E> next = target.next;
        if (pre != null) {
            if (next != null) {
                pre.next = next;
                next.prev = pre;
            } else { //下一节点为空  则把要删除的节点的上一节点 设置为结束节点
                pre.next = null;
                last = pre;
            }
        } else { //前一节点为空  则把要删除的节点的下一节点 设置为开始节点
            if (next != null) {
                next.prev = null;
                first = next;
            }
        }
        size--;
    }
}