Java源码-集合-LinkedList

时间：2021-08-21 17:16:45

基于JDK1.8.0_191

介绍

  LinkedList是以节点来保存数据的，不像数组在创建的时候需要申请一段连续的空间，LinkedList里的数据是可以存放在不同的空间当中，然后以内存地址作为寻找的工具，比如第一个节点里保存了第二个节点的地址信息，第二个节点又保存了第三个节点的地址信息，以此类推
节点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;
        }
    }

LinkedList有以下特性

  • 是双向链表，每个节点保存着下一个节点的信息，也保存了上一个节点的信息
  • 不是线程安全的，线程安全可以通过
List list = Collections.synchronizedList(new LinkedList(...));

实现

  • LinkedList可以作为堆栈和队列使用，它包含了许多对应的方法，比如poll、push等等

构造函数

  LinkedList的构造函数比较简单，它不需要初始化大小，因为它不存在扩容的要求

  • public LinkedList();
    第一个是无参构造函数，方法体里什么都不做

  • public LinkedList(Collection<? extends E> c);
    第二个是带初始化数据的，也就是创建一个带有c数据的LinkedList，c数据通过LinkedList的addAll方法插入

部分源码解析

点击查看详细内容

//在末尾插入节点，主要通过linkLast()实现
public boolean add(E e);
    /**
     * 在末尾插入节点
     */
    void linkLast(E e) {
        //LinkedList专门有last对象，用来保存最后一个节点信息
        final Node
   
   
   
     l = last; //创建新的节点 final Node 
    
      newNode = new Node<>(l, e, null); last = newNode; //如果之前LinkedList是null的，那新插入的就是第一个节点 if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //在指定位置插入节点 public void add(int index, E element) { checkPositionIndex(index); //如果指定位置是最后，调用linkLast方法 if (index == size) linkLast(element); else linkBefore(element, node(index)); } //在指定节点前面插入节点，下面代码的逻辑就是改变插入位置前一个节点，当前要插入的节点和后一个节点的prev和next的指向 void linkBefore(E e, Node 
     
       succ) { final Node 
      
        pred = succ.prev; final Node 
       
         newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } //在指定位置插入集合 public boolean addAll(int index, Collection 
         c) { checkPositionIndex(index); //转为数组 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //要插入位置的前一个节点和后一个节点 Node 
        
          pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } //循环插入节点 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node 
         
           newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } //处理要插入位置的后一个节点 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } //循环遍历LinkedList，然后把所有数据设为NULL public void clear(); //循环遍历LinkedList，然后做==或者equals操作 public int indexOf(Object o);

LinkedListList的查询

  LinkedList是不建议做频繁的查询操作，那么如果需要查询，哪种更快呢，我们可以试一下

  • 第一种
  for(int i = 0; i < list.size; i++){
    list.get(i);
  }

这种是最差的方式，完全不用测试，因为在for循环里，get操作又是通过另一个for循环实现的，所以这个操作等于是for循环的嵌套

  • 第二种
for(String str : list){}

在1千万数据时，耗时150ms

  • 第三种
for(Iterator<String> iter = list.iterator(); iter.hasNext();iter.next();){}

同样的数据耗时165ms，和第二种差不多

我们通过查看编译后的代码可以知道，第二种编译后的代码是

for(Iterator var4 = list.iterator(); var4.hasNext(); var5 = (String)var4.next()) {}

其实也就是通过迭代的方式
而第三种是

Iterator iter = list.iterator();
while(iter.hasNext()) {iter.next();}

通过while循环操作
本质上第二种和第三种差不多，只要不使用第一种就行

标签：

相关文章