概述

1 LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。

　　2 底层的数据结构是基于双向链表的，该数据结构我们称为节点。它也可以被当作堆栈、队列（实现了List 接口）或双端队列（实现了Deque 接口）进行操作。

　　3 双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。

　　4 它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到

　　优化：结点在前半段则从头开始遍历，后半段则从尾开始遍历，专业爆炸遍历最多一般结点就可以找到结点。

源码分析

继承结构

属性

{    // 实际元素个数    transient int size = 0;    // 头结点    transient Node
     
       first;    // 尾结点    transient Node
      
        last;}

构造方法

1）无参构造函数    public LinkedList() {    }2）有参构造函数public LinkedList(Collection
      c) {        this();        addAll(c);}

内部类

private static class Node
     
       {        E item; // 数据域（当前节点的值）        Node
      
        next; // 后继（指向当前一个节点的后一个节点）        Node
       
         prev; // 前驱（指向当前节点的前一个节点）                // 构造函数        Node(Node
        
          prev, E element, Node
         
           next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }

核心方法

add

public boolean add(E e) {       　　 // 添加到末尾        　　linkLast(e);        　　return true;  　　  }    void linkLast(E e) {        final Node
     
       l = last;    //临时节点l(L的小写)保存last，也就是l指向了最后一个节点        final Node
      
        newNode = new Node<>(l, e, null);//将e封装为节点，并且e.prev指向了最后一个节点        last = newNode;　　//newNode成为了最后一个节点，所以last指向了它        if (l == null)    //判断是不是一开始链表中就什么都没有，如果没有，则newNode就成为了第一个节点，first和last都要指向它            first = newNode;        else    //正常的在最后一个节点后追加，那么原先的最后一个节点的next就要指向现在真正的最后一个节点，原先的最后一个节点就变成了倒数第二个节点            l.next = newNode;        size++;//添加一个节点，size自增        modCount++;    }

remove

//首先通过看上面的注释，我们可以知道，如果我们要移除的值在链表中存在多个一样的值，那么我们会移除index最小的那个，也就是最先找到的那个值，如果不存在这个值，那么什么也不做    public boolean remove(Object o) {//这里可以看到，linkedList也能存储null        if (o == null) {//循环遍历链表，直到找到null值，然后使用unlink移除该值。下面的这个else中也一样            for (Node
     
       x = first; x != null; x = x.next) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            for (Node
      
        x = first; x != null; x = x.next) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }//不能传一个null值过，注意，看之前要注意之前的next、prev这些都是谁。    E unlink(Node
       
         x) {        // assert x != null;//拿到节点x的三个属性        final E element = x.item;        final Node
        
          next = x.next;        final Node
         
           prev = x.prev;//这里开始往下就进行移除该元素之后的操作，也就是把指向哪个节点搞定。        if (prev == null) {//说明移除的节点是头节点，则first头节点应该指向下一个节点            first = next;        } else {//不是头节点，prev.next=next：有1、2、3，将1.next指向3            prev.next = next;//然后解除x节点的前指向。            x.prev = null;        }        if (next == null) {//说明移除的节点是尾节点            last = prev;        } else {//不是尾节点，有1、2、3，将3.prev指向1. 然后将2.next=解除指向。            next.prev = prev;            x.next = null;        }//x的前后指向都为null了，也把item为null，让gc回收它        x.item = null;        size--;    //移除一个节点，size自减        modCount++;        return element;    //由于一开始已经保存了x的值到element，所以返回。    }

get(index)

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

indexOf(Object o)

//这个很简单，就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似，只是返回类型不一样。   public int indexOf(Object o) {        int index = 0;        if (o == null) {            for (Node
     
       x = first; x != null; x = x.next) {                if (x.item == null)                    return index;                index++;            }        } else {            for (Node
      
        x = first; x != null; x = x.next) {                if (o.equals(x.item))                    return index;                index++;            }        }        return -1;    }

迭代器

ListItr

　　不止有向后迭代的方法，还有向前迭代的方法，所以我们就知道了这个ListItr这个内部类干嘛用的了，就是能让linkedList不光能像后迭代，也能向前迭代。

　　看一下ListItr中的方法，可以发现，在迭代的过程中，还能移除、修改、添加值得操作。

转载于:https://www.cnblogs.com/RobertLionLin/p/11420090.html

你可能感兴趣的文章