一、双向链表

1. 基本实现

package com.douma.line;
public class DoubleLinkedlist<E> {
    private class Node {
        E e;
        Node prev;
        Node next;

        // 补全构造方法：
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this(e, null);
        }
        public Node() {
            this(null, null);
        }
        // 打印Node可调用 toString方法
        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node first; // 头节点
    private Node last; // 尾节点
    private int size;
    public DoubleLinkedList() {
        first = last = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

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

2. 双向链表的优劣

优：1 空间换时间

// 时间复杂度是 O(n)
private Node node(int index) {
    if (index < 0 || index >= size) return null;
    
    Node curr = null;
    // 如果 index 小于链表长度的一半，则从 first 开始遍历查找
    if (index < size / 2) {
        curr = first;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
    } else { 
        // 如果 index 大于等于链表长度的一半，则从 last 开始遍历查找
        curr = last;
        for (int i = 0; i < size - index - 1; i++) {
            curr = curr.prev;
        }
    }
    return curr;
}

3. 基本操作

修改：

public void set(int index, E e) {
    // 先找到需要修改的节点
    Node node = node(index);
    if (node == null) {
        throw new IllegalArgumentException("index failed, index must >= 0 and <size");
    }
    node.e = e;
}

插入：

/**
     * 往链表的表头插入节点
     * @param e
     */
public void addFirst(E e) {
    Node newNode = new Node(e);
    if (first == null) {
        // 如果头节点为空，说明链表中没有一个节点
        // 那么新插入的节点既是头节点，又是尾节点
        last = newNode;
    } else {
        // 将新节点作为头节点
        newNode.next = first;
        first.prev = newNode;
    }
    first = newNode;
    size++;
}
/**
     * 往链表尾巴插入新节点
     * @param e
     */
public void addLast(E e) {
    Node newNode = new Node(e);
    if (last == null) {
        // 如果尾节点为空，说明链表中没有一个节点
        // 那么新插入的节点既是头节点，又是尾节点
        first = newNode;
    } else {
        // 将新节点作为尾节点
        newNode.prev = last;
        last.next = newNode;
    }
    last = newNode;
    size++;
}
/**
     * 往指定索引位置插入节点
     * @param index
     * @param e
     */
// 时间复杂度是 O(n)
public void add(int index, E e) {
    if (index < 0 || index > size)
        throw new IllegalArgumentException("add failed, index must >= 0 and <= size");

    if (index == size) {
        addLast(e);
    } else if (index == 0) {
        addFirst(e);
    } else {
        // 1. 找到要插入的位置，并记住这个位置的节点
        // 如 往 index=2 的地方插入节点77，找得oldNode 的index就为2
        Node oldNode = node(index);
        // 还要记录其前一个节点
        Node prev = oldNode.prev;

        // 2. 新建节点，将它的 next 指向 oldNode，将它的 prev 指向 oldNode.prev
        Node newNode = new Node(prev, e, oldNode);

        // 3. 将新建节点设置为 oldNode 的 prev
        oldNode.prev = newNode;

        // 4. 将新建节点设置 oldNode 之前的 prev 的 next
        prev.next = newNode;
        size++;
    }
}

删除：

• 删头结点：记下要删除节点的next节点。
• 删尾节点：记下要删除节点的prev节点。
• 删除中间节点：
  先找到该节点： Node delNode = node(index);

public E removeFirst() {
    if (first == null) {
        throw new NoSuchElementException();
    }
    E e = first.e;
    // 拿到头节点的下一个节点
    Node next = first.next;
    // 如果 next 为空，说明整个链表只有一个节点
    if (next == null) {
        first = null;
        last = null;
    } else {
        // 将头节点从链表中断开
        first.next = null;
        next.prev = null;
        // 将 next 设置为头节点
        first = next;
    }
    size--;
    return e;
}

public E removeLast() {
    if (last == null) {
        throw new NoSuchElementException();
    }
    E e = last.e;
    // 拿到尾节点的前一个节点
    Node prev = last.prev;
    // 如果 prev 为空，说明整个链表只有一个节点
    if (prev == null) {
        last = null;
        first = null;
    } else {
        // 将尾节点从链表中断开
        last.prev = null;
        prev.next = null;
        // 将 prev 设置为尾节点
        last = prev;
    }
    size--;
    return e;
}

// 时间复杂度是 O(n)
public E remove(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("index failed, index must >= 0 and < size");

    if (index == 0) {
        return removeFirst();
    } else if (index == size - 1) {
        return removeLast();
    }

    // 1. 找到要删除的节点
    Node delNode = node(index);
    E e = delNode.e;

    // 2. 记住要删除节点的 prev 和 next 节点
    Node prev = delNode.prev;
    Node next = delNode.next;

    // 3. 将删除节点的前后节点联系起来
    prev.next = next;
    next.prev = prev;

    // 4. 将删除节点从链表中断开
    delNode.next = null;
    delNode.prev = null;

    size--;
    return e;
}

java中内置的LinkedList是一个双向链表。