LinkedList增删改查操作底层实现原理

上一篇 <<<ArrayList的动态扩容、ModCount及fail-fast原理
下一篇 >>>

LinkedList数据结构：双向链表头尾相接

实现原理

• a、在底层中使用静态内部类Node节点存放节点元素
  三个属性 pred（关联的上一个节点） item 当前的值 next 下一个节点
• b、Add原理是如何实现 一直在链表之后新增
• C、Get原理 链表缺点：查询效率非常低，所以linkeList中采用折半查找/二分查找 范围查询定位node节点，时间复杂度为O(logN)

JaryeLinkList.Node<E> node(int index) {
    /**
     * 如果index小于size/2，说明index在链表的前半部分，则从首尾开始一直找next
     */
    if (index < (size >> 1)) {
        JaryeLinkList.Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else {
        /**
         * 如果index在后半段，则从后面往前面找
         */
        JaryeLinkList.Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}

• D、删除原理：就是改变头尾指针的指向