数据结构-双向链表

1. 内容大纲

本章节的代码：https://github.com/wicksonZhang/data-structure/tree/main/2-LinkedList/src/main/java/com/wickson/linkedlist/doubles

---

2. 基础知识

2.1. 什么是双向链表

双向链表是单项链表的一个升级版本，由节点中的两个元素升级为了三个元素。第一个元素指向上一个节点的引用，第二个元素存放数据，第三个元素指向下一个节点的引用。

2.2. 双向链表优缺点

优点

1. 双向遍历：因为存在一个前驱节点和后驱节点，所以可以很方便的进行正向和反向的遍历。
2. 删除节点：我们删除节点时，通过指向下一个节点的指针找到后一个节点，还可以通过指向前一个节点的指针快速找到前一个节点，使删除操作更高效。

缺点

1. 占用一定的存储空间：相比于单向链表，多了一个前驱节点寻找上一个节点的地址。

2.3. 生活中的例子

1. 共享单车的传动链条

---

3. 接口设计

我们从动态数组中我们可以再次对 List 集合进行优化，我们将公共部分进行封装为 AbstractList 。

• List<E>.java

public interface List<E> {
    
    int size();	// 元素数量
    
    boolean isEmpty(); // 数组是否为空

    boolean contains(E element); // 是否包含某个元素
    
    void add(E element); // 添加元素

    E get(int index); // 获取指定位置元素

    E set(int index, E element); // 设置指定位置元素

    void add(int index, E element); // 将元素添加到指定位置

    E remove(int index); // 删除指定位置元素

    int indexOf(E element); // 获取元素索引

    void clear(); // 清除所有元素

}

• AbstractList<E>.java

public abstract class AbstractList<E> implements List<E> {

    protected int size = 0;
    
    // 元素数量
    @Override
    public int size() { return size; }

    // 数组是否为空
    @Override
    public boolean isEmpty() { return size == 0; }

    // 数组是否包含某个元素
    @Override
    public boolean contains(E e) { return indexOf(e) >= 0; }

    // 添加元素到首尾部
    @Override
    public void add(E element) { add(size, element);
                                
	// 范围检查
    public void rangeChecked(int index) { if (index >= size || index < 0) { indexOutOfBounds(index); } }

    // 元素新增范围检查
    public void rangeAddChecked(int index) { if (index > size || index < 0) { indexOutOfBounds(index); } }

    // 数组越界异常
    public void indexOutOfBounds(int index) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); }

}

• LinkedList<E>.java

public class LinkedList<E> extends AbstractList<E> {

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) { }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }

    @Override
    public void clear() {}
    
}

---

4. 代码实现

4.1. 初始化

需求：实现双向链表的初始化。

public class LinkedList<E> extends AbstractList<E> {

    /**
     * 指向上一个节点
     */
    private Node<E> first;

    /**
     * 指向下一个节点
     */
    private Node<E> last;

    /**
     * Node 节点
     *
     * @param <E> 元素
     */
    public static class Node<E> {

        Node<E> prev;
        
        E element;

        Node<E> next;

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

4.2. 获取节点

需求：通过 index 获取 node 节点。

实现步骤：

• 由于目前采取的双向链表，所以相对于可以根据具体的 size >> 1 进行查找。
• 首先，我们需要将 size >> 1 。
• 然后，根据 index 跟 size >> 1 进行判断，是从前驱节点还是后驱节点进行查找。

/**
 * 获取 Node 节点
 *
 * @param index 索引
 * @return Node<E>
 */
private Node<E> node(int index) {
    // 检查索引范围
    rangeChecked(index);

    Node<E> node;
    if ((size >> 1) > index) {
        node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
    } else {
        node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
    }
    return node;
}

4.3. 添加元素到指定位置

需求：我们需要将元素添加到指定位置。

注意：分别考虑将元素添加到中间、添加到第一索引位置、最后一个索引位置。

Step-1: 将元素添加到中间

• 首先，获取 index 索引的节点，并将前驱节点指向新节点。
• 然后，获取 index 索引节点的上一个节点，并将后驱节点指向新节点。
• 最后，将新节点的前后指针分别指向上面两个节点

@Override
public void add(int index, E element) {
    rangeAddChecked(index);
    // 获取 index 索引的节点，并将前驱节点指向新节点
    Node<E> nextNode = node(index);
    // 获取 index 索引节点的上一个节点，并将后驱节点指向新节点
    Node<E> prevNode = nextNode.prev;
    // 将新节点的前后指针分别指向上面两个节点
    Node<E> node = new Node<>(prevNode, element, nextNode);
    prevNode.next = node;
    nextNode.prev = node;
    size++;
}

Step-2: 将元素添加到第一位

• 直接判断原节点的 prev 是否为 null

@Override
public void add(int index, E element) {
    rangeAddChecked(index);
    // 获取 index 索引的节点，并将前驱节点指向新节点
    Node<E> nextNode = node(index);
    // 获取 index 索引节点的上一个节点，并将后驱节点指向新节点
    Node<E> prevNode = nextNode.prev;
    // 将新节点的前后指针分别指向上面两个节点
    Node<E> node = new Node<>(prevNode, element, nextNode);
    nextNode.prev = node;
    if (prevNode == null) { // 当 prevNode 为 null 时，表示当前节点为第一个节点
        first = node;
    } else {
        prevNode.next = node;
    }
    size++;
}

Step-3: 将元素添加到最后一位

• 当 index == size 的时候就等于再往最后一个位置在添加元素了。

@Override
public void add(int index, E element) {
    rangeAddChecked(index);
    if (index == size) { // index == size 表示往最后一个位置添加元素
        Node<E> nextNode = last;
        Node<E> node = new Node<>(nextNode, element, null);
        last = node;
        nextNode.next = node;
    } else {
        // 获取 index 索引的节点，并将前驱节点指向新节点
        Node<E> nextNode = node(index);
        // 获取 index 索引节点的上一个节点，并将后驱节点指向新节点
        Node<E> prevNode = nextNode.prev;
        // 将新节点的前后指针分别指向上面两个节点
        Node<E> node = new Node<>(prevNode, element, nextNode);
        nextNode.prev = node;
        if (prevNode == null) { // index == 0
            first = node;
        } else {
            prevNode.next = node;
        }
    }
    size++;
}

注意事项：如果 size 为 0 时，index == size 就会存在问题

@Override
public void add(int index, E element) {
    rangeAddChecked(index);
    if (index == size) { // index == size 表示往最后一个位置添加元素
        Node<E> lastNode = last;
        last = new Node<>(lastNode, element, null);
        if (lastNode == null) { // 如果
            first = last;
        } else {
            lastNode.next = last;
        }
    } else {
        // 获取 index 索引的节点，并将前驱节点指向新节点
        Node<E> nextNode = node(index);
        // 获取 index 索引节点的上一个节点，并将后驱节点指向新节点
        Node<E> prevNode = nextNode.prev;
        // 将新节点的前后指针分别指向上面两个节点
        Node<E> node = new Node<>(prevNode, element, nextNode);
        nextNode.prev = node;
        if (prevNode == null) { // index == 0
            first = node;
        } else {
            prevNode.next = node;
        }
    }
    size++;
}

4.4. 删除指定元素

需求：设置指定元素。

注意事项：需要考虑删除删除中间节点，第一个节点，最后一个节点。

删除中间节点

• 具体操作如下

@Override
public E remove(int index) {
    rangeChecked(index);

    Node<E> node = node(index);
    Node<E> prevNode = node.prev;
    Node<E> nextNode = node.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;

    size--;
    return node.element;
}

Step-1: 删除第一个元素

• 具体操作如下

/**
 * 删除指定元素
 *
 * @param index 索引
 * @return E
 */
@Override
public E remove(int index) {
    rangeChecked(index);
    Node<E> node = node(index);
    Node<E> prevNode = node.prev;
    Node<E> nextNode = node.next;
    nextNode.prev = prevNode;
    if (prevNode == null) { // index == 0
        first = nextNode;
    } else {
        prevNode.next = nextNode;
    }
    size--;
    return node.element;
}

Step-2: 删除最后一个元素

• 具体操作如下

/**
 * 删除指定元素
 *
 * @param index 索引
 * @return E
 */
@Override
public E remove(int index) {
    rangeChecked(index);
    Node<E> node = node(index);
    Node<E> prevNode = node.prev;
    Node<E> nextNode = node.next;
    if (nextNode == null) { // index == size
        last = prevNode;
    } else {
        nextNode.prev = prevNode;
    }

    if (prevNode == null) { // index == 0
        first = nextNode;
    } else {
        prevNode.next = nextNode;
    }

    size--;
    return node.element;
}

4.5. 设置指定位置元素

需求：设置指定位置元素。

/**
 * 设置指定位置元素
 *
 * @param index   索引
 * @param element 元素
 * @return E
 */
@Override
public E set(int index, E element) {
    Node<E> node = node(index);
    E oldElement = node.element;
    node.element = element;
    return oldElement;
}

4.6. 清空元素

需求：清空节点所有元素。

/**
 * 清空元素
 */
@Override
public void clear() {
    size = 0;
    first = null;
    last = null;
}

4.7. 获取指定位置元素

需求：根据所有获取到当前节点，然后在获取节点的 element。

/**
 * 获取指定位置元素
 *
 * @param index 索引
 * @return
 */
@Override
public E get(int index) {
    return node(index).element;
}

4.8. 获取元素索引

需求：获取元素索引。

/**
 * 获取元素索引
 *
 * @param element 元素
 * @return int
 */
@Override
public int indexOf(E element) {
    Node<E> node = first;
    if (element == null) {
        for (int i = 0; i < size; i++) {
            if (node.element == null) {
                return i;
            }
            node = node.next;
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }
    }
    return -1;
}

4.9. 打印元素

/**
 * 打印元素
 *
 * @return
 */
@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("{ size = ").append(size).append(" , Node = [ ");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            builder.append(",");
        }
        builder.append(node.element);
        node = node.next;
    }
    builder.append(" ]}");
    return builder.toString();
}

4.10. 测试用例

public class LinkedListTest {

    @Test
    public void testAddAndGet() {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(0, 1);
        linkedList.add(1, 2);
        linkedList.add(2, 3);

        assertEquals((Object) 1, linkedList.get(0));
        assertEquals((Object) 2, linkedList.get(1));
        assertEquals((Object) 3, linkedList.get(2));
        System.out.println("linkedList ===> " + linkedList);
    }

    @Test
    public void testSet() {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add(0, "apple");
        linkedList.add(1, "banana");

        assertEquals("apple", linkedList.set(0, "orange"));
        assertEquals("orange", linkedList.get(0));
        System.out.println("linkedList ===> " + linkedList);
    }

    @Test
    public void testRemove() {
        LinkedList<Character> linkedList = new LinkedList<>();
        linkedList.add(0, 'a');
        linkedList.add(1, 'b');
        linkedList.add(2, 'c');

        assertEquals('b', (char) linkedList.remove(1));
        assertEquals("{ size = 2 , Node = [ a,c ]}", linkedList.toString());
    }

    @Test
    public void testIndexOf() {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(0, 10);
        linkedList.add(1, 20);
        linkedList.add(2, 30);

        assertEquals(1, linkedList.indexOf(20));
        assertEquals(-1, linkedList.indexOf(40));
    }

    @Test
    public void testClear() {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add(0, "one");
        linkedList.add(1, "two");

        linkedList.clear();
        assertEquals("{ size = 0 , Node = [  ]}", linkedList.toString());
    }
}

---

5. 总结

5.1. 双向链表 VS 单向链表

• 单项链表：单项链表主要解决了内存空间的浪费，也是在数组的基础上进行了一个优化。
• 双向链表：作为单向链表的升级版，查询的速度减半了，可以根据索引的大小进行判断是从前驱节点还是后驱节点进行查找，新增了一个节点元素。

5.2. 双向链表 VS 动态数组

数据结构	优点	缺点	适用场景
动态数组	开辟、销毁内存空间次数相对较少	可能造成内存浪费（可缩容解决）	1. 频繁尾部操作 2. 快速查询（随机访问）
双向链表	不会造成内存空间的浪费	开辟、销毁内存空间的次数相对较多	1. 频繁头部操作 2. 任意位置快速操作

---

6. 参考博文

• 恋上数据结构与算法(第一季)-MJ大神精选