手写 JDK 的 LinkedList 实现

前言

这里将参考 JDK 的 LinkedList 底层源码，模拟手写一个简易版的 LinkedList。

代码

• 定义接口

public interface MyList<E> {

    /**
     * 添加节点
     */
    void add(E element);

    /**
     * 设置节点
     */
    E set(int index, E element);

    /**
     * 获取节点
     */
    E get(int index);

    /**
     * 删除节点
     */
    E remove(int index);

    /**
     * 清空链表节点
     */
    void clear();

    /**
     * 获取节点数量
     */
    int size();

}

• 基于双向链表实现 LinkedList

public class MyLinkedList<E> implements MyList<E> {

    private int size = 0;   // 链表节点的数量

    private Node<E> first;  // 头节点

    private Node<E> last;   // 尾节点

    public MyLinkedList() {

    }

    /**
     * 添加节点到链表的尾部
     */
    private void linkLast(E element) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(l, element, null);
        last = newNode;
        // 判断是否首次添加节点
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    /**
     * 移除节点
     */
    private E unlink(Node<E> node) {
        E data = node.data;
        Node<E> prev = node.prev;
        Node<E> next = node.next;

        // 判断是否移除头节点
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }

        // 判断是否移除尾节点
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

        node.data = null;
        size--;
        return data;
    }

    /**
     * 检查索引范围
     */
    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 检查索引范围
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 获取指定位置的节点
     */
    private Node<E> node(int index) {
        checkElementIndex(index);
        Node<E> cur = first;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    @Override
    public void add(E element) {
        linkLast(element);
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E oldData = node.data;
        node.data = element;
        return oldData;
    }

    @Override
    public E get(int index) {
        Node<E> node = node(index);
        return node.data;
    }

    @Override
    public E remove(int index) {
        Node<E> node = node(index);
        return unlink(node);
    }

    @Override
    public void clear() {
        Node<E> cur = first;
        while (cur != null) {
            Node<E> next = cur.next;
            // GC
            cur.prev = null;
            cur.next = null;
            cur.data = null;
            cur = next;
        }
        first = null;
        last = null;
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        Node<E> cur = first;
        while (cur != null) {
            stringBuilder.append(cur.data);
            if (cur != last) {
                stringBuilder.append(", ");
            }
            cur = cur.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    /**
     * 节点
     */
    static class Node<E> {

        /**
         * 数据
         */
        E data;

        /**
         * 上一个节点
         */
        Node<E> prev;

        /**
         * 下一个节点
         */
        Node<E> next;

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

    }

}

测试

public class MyLinkedListTest {

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.add(13);
        list.add(12);
        list.add(11);
        list.add(14);
        list.add(17);
        list.add(15);
        list.add(18);
        System.out.println(list);

        Integer value = list.get(5);
        System.out.println("value = " + value);

        Integer oldValue = list.set(1, 23);
        System.out.println("oldValue = " + oldValue);
        System.out.println(list);

        list.remove(1);
        list.remove(1);
        list.remove(1);
        System.out.println(list);
        System.out.println("size = " + list.size());

        list.clear();
        System.out.println(list);
        System.out.println("size = " + list.size());
    }

}

输出结果：

[13, 12, 11, 14, 17, 15, 18]
value = 15
oldValue = 12
[13, 23, 11, 14, 17, 15, 18]
[13, 17, 15, 18]
size = 4
[]
size = 0