Java基础---LinkList

一. 描述

双向链表（Doubly-linked）实现了接口List和Deque（双端队列），实现了所有的list操作并允许元素可为null。

对于双向链表，所有的操作都符合预期。索引到列表的操作将从列表头或者列表尾开始遍历列表，以便更接近指定的索引为准。（不支持类似数组的随机访问，根据下标访问链表的话，需要从链表头或者链表尾开始遍历。）

　　与ArrayList一样，此实现不是同步的。如果有多个线程访问同一个链表的话，并且至少上一个线程在结构上修改了链表，他必须对外同步。（结构修改是指r任何操作添加或者删除多个元素，仅仅设置元素值不是修改。）。这通常是在某些对象上的同步完成封装的。如果不存在这样的对象，则应该使用java.util. Collections.synchronizedList(new LinkedList(....))。

　　快速失败，在ArrayList已经介绍了。

二. 结构

　　 LinkedList内部元素采用Node，链表来实现。代码如下，可以发现这是一个私有的内部类，导致我们无法直接获取Node，只能获取Node的值。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

　　这个就导致了一个很经典的面试问题，for循环遍历LinkedList为什么比遍历数组慢。原因：主要原因for循环遍历LinkedList我们无法获取Node类，无法获取节点属性的next（下一个节点），如果可以获取的话，那么我们从头部或者尾部遍历都是很快的。那么我们就只能通过下标去访问了，数组支持随机访问，根据下标访问的需要的时间复杂度O(1)；而我们看下LinkedList的下标访问返回的是值，不是节点，我们无法获取到当前节点，也就无法获取下一个节点。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

　　接下来，我们继续查询获取节点的算法，我们发现根据下标来获取Node节点，需要从第一个节点或者最后一个节点遍历，直到到达下标的地方，这样时间复杂度最多需要O(2/n)，由此可见for循环遍历效率比较低。那么迭代器为啥可以比较快呢，因为迭代器可以直接访问节点...还有下个节点，代码如下：

Node<E> node(int index) {
    // assert isElementIndex(index);

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

　　那么结论来了：linkedList底层是链表实现，（1）下标随机访问链表，通过分析get方法，算法要求从头或者从尾依次访问节点，直到达到指定的节点，并且返回的是值而不是节点对象。（2）由于返回的是节点对象，我们无法直接获取节点对象的下一个对象地址，只能再通过get方法，再走一遍1的流程。（3）iterator可以访问节点，可以获取当前节点的下个节点，时间复杂度o(1)

Java基础---LinkList

相关推荐