记录：用Java语言实现双向链表（增删查）

节点对象

public class Node<T> {
    public T value;
    public Node pre = null;
    public Node next = null;

    public Node(T value, Node pre, Node next) {
        this.value = value;
        this.pre = pre;
        this.next = next;
    }
}

双向链表

public class TwoSideLinkedList<T> {
    // 头节点
    public Node<T> firstNode = null;

    // 尾节点
    public Node<T> lastNode = null;

    // 链表长度
    public int size = 0;

    /**
     * 初始化
     * 1. 空的双向链表
     * 2. 带节点的双向链表
     */
    public TwoSideLinkedList() {
    }

    public TwoSideLinkedList(T... nodeList) {
        // 将多个节点添加进链表中
        addAll(nodeList);
    }

    /**
     * 增
     * 1. 往尾部添加节点 -> add
     * 2. 往头部添加节点 -> addFirst
     * 3. 往任意位置添加节点 -> addByIndex
     * 4. 批量添加节点到尾部 -> addAll
     */
    public void add(T data) {
        // 如果链表为空，则设置当前节点为头节点和尾节点
        if (size == 0) {
            Node<T> newHeadNode = new Node(data, null, null);
            firstNode = newHeadNode;
            lastNode = newHeadNode;
        } else {
            // 往尾节点添加节点
            Node<T> newTailNode = new Node(data, lastNode, null);
            lastNode.next = newTailNode;
            lastNode = newTailNode;
        }
        size++;
    }

    public void addFirst(T data) {
        if (size == 0) {
            Node<T> newHeadNode = new Node(data, null, null);
            firstNode = newHeadNode;
            lastNode = newHeadNode;
        } else {
            Node<T> newHeadNode = new Node(data, null, firstNode);
            firstNode.pre = newHeadNode;
            firstNode = newHeadNode;
        }
        size++;
    }

    public void addByIndex(int index, T data) throws Exception {
        // 1. 判断index是否在链表范围内
        if (index > size) {
            throw new Exception("Out of index");
        }
        // 2. 找到目标节点和其前节点
        Node<T> oldIndexNode = firstNode;
        for (int i = 0; i < index; i++) {
            // 2.1 得到目标位置的节点
            oldIndexNode = oldIndexNode.next;
        }
        // 3. 得到前节点
        Node<T> preIndexNode = oldIndexNode.pre;
        // 4. 根据传入的值，创建新的节点
        Node<T> newIndexNode = new Node(data, preIndexNode, oldIndexNode);
        // 5. 修改链表之间的关系
        preIndexNode.next = newIndexNode;
        oldIndexNode.pre = newIndexNode;
        size++;
    }

    public void addAll(T... data) {
        // 循环调用add的方法进行添加
        for (T value : data) {
            add(value);
        }
    }

    /**
     * 查
     * 1. 拿到头部节点 -> getFirst
     * 2. 拿到尾部节点 -> getTail
     * 3. 拿到任意位置节点 -> getByIndex
     * 4. 链表长度 -> getSize
     */
    public T getFirst() {
        return firstNode.value;
    }

    public T getTail() {
        return lastNode.value;
    }

    public T getByIndex(int index) throws Exception {
        if (index >= size) {
            throw new Exception("Out of index");
        }
        Node<T> targetNode = firstNode;
        for (int i = 0; i < index; i++) {
            targetNode = targetNode.next;
        }
        return targetNode.value;
    }

    public int getSize() {
        return size;
    }

    /**
     * 刪
     * 1. 删除尾节点 -> delete
     * 2. 删除头节点 -> deleteFirst
     * 3. 删除任意节点 -> deleteByIndex
     */
    public void delete() throws Exception {
        if (size == 0) {
            throw new Exception("LinkedList is empty");
        }
        lastNode = lastNode.pre;
        lastNode.next = null;
        size--;
    }

    public void deleteFirst() throws Exception {
        if (size == 0) {
            throw new Exception("LinkedList is empty");
        }
        firstNode = firstNode.next;
        firstNode.pre = null;
        size--;
    }

    public void deleteByIndex(int index) throws Exception {
        if (size == 0) {
            throw new Exception("LinkedList is empty");
        }
        if (index >= size) {
            throw new Exception("Out of index");
        }
        if (index == 0) {
            deleteFirst();
        }
        if (index == size - 1) {
            delete();
        }

        Node<T> waitForDeleteNode = firstNode;
        for (int i = 0; i < index; i++) {
            waitForDeleteNode = waitForDeleteNode.next;
        }
        Node<T> preNode = waitForDeleteNode.pre;
        Node<T> nextNode = waitForDeleteNode.next;
        preNode.next = nextNode;
        nextNode.pre = preNode;
        size--;
    }
}

测试方法

public class DemoApplication {

    public static void main(String[] args) throws Exception {
        // 空链表
        TwoSideLinkedList<String> emptyLinkedList = new TwoSideLinkedList<>();
        emptyLinkedList.add("b");
        emptyLinkedList.add("d");
        emptyLinkedList.addFirst("a");
        emptyLinkedList.addByIndex(2, "c");
        emptyLinkedList.addAll("e", "f", "g");

        System.out.println(emptyLinkedList.getSize()); // 7
        System.out.println(emptyLinkedList.getFirst()); // a
        System.out.println(emptyLinkedList.getTail()); // g
        System.out.println(emptyLinkedList.getByIndex(2)); // c

        emptyLinkedList.delete();
        emptyLinkedList.deleteFirst();
        emptyLinkedList.deleteByIndex(1);

        // 非空链表
        TwoSideLinkedList<String> nonEmptyLinkedList = new TwoSideLinkedList<>("a", "b");
        nonEmptyLinkedList.add("c");
        System.out.println();
    }
}