LinkedList详解

简介

添加

• 在末尾插入元素时间复杂度为 O(1)

• 在指定位置 index 插入，会先寻找 index 节点 node，在 node 前插入

# 根据index查询节点
public Node<T> node(int index) {
        // 下标小于前半部分，从头往后找
        if (index < (size >> 1)) {
            Node<T> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { // 下标大于后半部分，从尾往前找
            Node<T> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
}

删除

修改

查询