LinkedList数据结构设计原理的简要深入分析

成员变量以及节点定义

transient int size = 0;

/**
 * Pointer to first node.
 等效判断一定是头节点的类型： first为空且last为空，那么肯定是头节点，或者first的前驱节点为空且first节点内容不为空
 * Invariant: (first == null && last == null) || // 空头节点
 *            (first.prev == null && first.item != null) // 非空头节点
 */
transient Node<E> first;

/**
 * Pointer to last node.
 //同上
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

节点定义

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; // 指向前驱节点
    }
}

linkFirst

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first; // 暂存链表
  	//① 头插法，新建节点时，节点的next节点直接指向链表头节点
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode; // first指针指向newNode
    if (f == null) // 如果原头节点是空，说明此时newNode就是作为链表的第一个节点，显然last也是要指向它
        last = newNode;
    else// 原头节点不为空，那么在前面①头插法后，那么newNode就可以作为原头节点前驱节点
        f.prev = newNode;
    size++;
    modCount++; // 新增节点肯定属于链表结构变化
}

linkLast

  // 尾插法
void linkLast(E e) {
      final Node<E> l = last; // 暂存尾节点
      final Node<E> newNode = new Node<>(l, e, null); // 够建新节点，前驱节点指向尾部节点
      last = newNode; // 原尾部指针更新，指向新的尾部节点
      if (l == null) // 如果l为空，那么将first指针指向新增节点
          first = newNode;
      else
          l.next = newNode; // 尾节点不为空时插入，原为节点的next指针当然要指向新增的节点
      size++;
      modCount++;
  }

linkBefore

/**
 * Inserts element e before non-null Node succ.
 */
// 在一个为非空的后继节点插入新节点
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev; // 暂存后继节点的前节点
    final Node<E> newNode = new Node<>(pred, e, succ);// p<=>e<=>succ
    succ.prev = newNode; // 后继节点的前驱指针指向新节点
    if (pred == null) // 如果pred为空，说明此时succ其实first节点，那么在first节点前插入新节点，可知插入结束后，将first更新指向新节点
        first = newNode;
    else
        pred.next = newNode; // 原pred.next是指向succ，现在指向newNode，而newNode的next指向succ
    size++;
    modCount++;
}

unlinkFirst

  /**
   * Unlinks non-null first node f.
   */
// 将非空头节点脱离链表
  private E unlinkFirst(Node<E> f) {
      // assert f == first && f != null;
      final E element = f.item;
      final Node<E> next = f.next; // 暂存除去头节点之后的子链表
      f.item = null;
      f.next = null; // help GC
      first = next; // 更新first指向next节点，也即此时next节就是头节点角色
      if (next == null) // 如果next为空，说明处理f时，链表仅有一个头节点，删除后，last指针也要指向null
          last = null;
      else
          next.prev = null; // 若还未执行next.prev = null时，next.prev是指向原f节点，上面完成f节点删除后，next作为头节点角色，当然pred指针需要指向null
      size--;
      modCount++;
      return element;
  }

为何要先对xx节点判断为空时，就指向A操作，不为空时再执行B操作，

因为当xx节点不为空时，才能对xx节点的next或者pred指针进行操作

unlinkLast

  /**
   * Unlinks non-null last node l.
   */
// 将尾节点脱离链表
  private E unlinkLast(Node<E> l) {
      // assert l == last && l != null;
      final E element = l.item; 
      final Node<E> prev = l.prev; // 暂存last节点之前的子链
      l.item = null;
      l.prev = null; // help GC，此时last节点脱离原链表
      last = prev;  // 将last指针更新指向prev节点
      if (prev == null) // 如果pred节点为空，说明此时pred就是头节点
          first = null; 
      else
          prev.next = null; // 如果pred节点不为空，那么此时pred作为子链的最后一个节点，next指针自然要指向null
      size--;
      modCount++;
      return element;
  }

unlink

  /**
   * Unlinks non-null node x.
   */
// 将一个非空节点x脱离链表
  E unlink(Node<E> x) {
      // assert x != null;
      final E element = x.item;   
      final Node<E> next = x.next;  // 前子链<=>x<=>后子链 中的 x<=>后子链
      final Node<E> prev = x.prev;  // 前子链<=>x<=>后子链 中的 前子链<=>x

      if (prev == null) {   // 如果x的前驱节的为空，说明此时删除x就是删除头节点，那么删除节后，first更新指向为next节点，此时next节点作为新的头节点
          first = next;
      } else {
          prev.next = next; // 将pred.next=>x=>next 改为pred.next => next
          x.prev = null; // 将x节点脱离前驱节点
      }

      if (next == null) { // pred<=>x->null  变为 pred->null，那么删除x后，last更新指向新的尾节点pred
          last = prev;
      } else {
          next.prev = prev;  // 原来next的前驱指针是指向x，那么x删除后，next.pred指向x节点的前驱节点即可：pred.next <= next
          x.next = null; // 将x节点脱离后继节点
      }

      x.item = null; // 前面已经完成pred、next引用指向为null，那么再将x节点的数据域置为null，help GC
      size--;
      modCount++;
      return element;
  }

getFirst

    /**
     * Returns the first element in this list.
     *
     * @return the first element in this list
     * @throws NoSuchElementException if this list is empty
     */
// 如果是空链表调用getFirst()方法就会抛出NSEE异常
public E getFirst() {
    final Node<E> f = first; // 
    if (f == null) // 注意技巧：先取出节点，再判断节点是否为空
        throw new NoSuchElementException();
    return f.item; 
}

removeFirst

//NoSuchElementException – if this list is empty
//如果是空链表调用removeFirst直接抛出异常
public E removeFirst() {
    final Node<E> f = first;  // 先取出节点
    if (f == null) // 说明是空链表
        throw new NoSuchElementException();
    return unlinkFirst(f); // 非空链表情况下调用unlinkFirst将first节点脱离链表
}

removeLast同理

addFirst

addFirst内部调用linkFirst实现将e节点使用头插法插入链表

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

add

/**
 * Appends the specified element to the end of this list.
 默认使用尾插法插入节点
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */

public boolean add(E e) {
    linkLast(e);
    return true;
}

remove

/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
// 分两种删除方法
public boolean remove(Object o) {
    if (o == null) {
      	// 1、如果给定的对象为空，那么直接遍历链表，找出链表的item为null的节点x，并删除x节点
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
      // 2、如果给定的对象为空，那么就遍历链表节点的item和o.item相等的节点，并删除之
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    // 找不到给定o，当然是返回false
    return false;
}

clear

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next; // 先暂存除去x节点的子类，next显然为子链头节点
        x.item = null;
        x.next = null;
        x.prev = null; // help GC
        x = next; // 将x指针更新指向next节点
    }
    first = last = null; // 头尾指针也要置空
    size = 0; // size肯定为0
    modCount++;
}

此外链表也提供索引方式来访问元素

package concurrent.demo;

import java.util.LinkedList;

public class LinkedListDemo {
     public static void main(String[] args) {
        LinkedList<String> list=new LinkedList<>();
        list.add("foo");
        list.add("bar");
        list.add("foobar");
         System.out.println(list.indexOf("bar")); // 1
         System.out.println(list.get(0)); // foo
         System.out.println(list.get(10)); //IndexOutOfBoundsException
     }

}

// Positional Access Operations

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

checkElementIndex

  private void checkElementIndex(int index) {
      if (!isElementIndex(index))
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

  /**
   * Tells if the argument is the index of an existing element.
   */
  //索引是从0开始到size-1,注意：这里是检查已存在节点的索引
  private boolean isElementIndex(int index) {
      return index >= 0 && index < size;
  }



  /**
   * Tells if the argument is the index of a valid position for an
   * iterator or an add operation.
   */
// 为迭代器或者add操作判断给定索引是否有效位置
  private boolean isPositionIndex(int index) {
      return index >= 0 && index <= size;
  }

indexOf

 //Returns the index of the first occurrence of the specified element in this list,
//从链表头节点位置开始遍历
public int indexOf(Object o) {
       int index = 0; //从0开始计数
       if (o == null) { 
           for (Node<E> x = first; x != null; x = x.next) {
               if (x.item == null) // 如果first节点恰好为null，那么return的index就是0，因此头节点和索引0可对齐，那么其他节点和之后的索引也能对齐。
                   return index;
               index++;
           }
       } else {
           for (Node<E> x = first; x != null; x = x.next) {
               if (o.equals(x.item))
                   return index;
               index++;
           }
       }
       return -1;
   }

indexOf是从头节点开始遍历链表，而lastIndexOf是从尾部节点方向遍历

public int lastIndexOf(Object o) {
    int index = size; //取链表长度作为起始点
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--; 
            if (x.item == null) 
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;// 这里为何先自减1呢？ 因为链表的索引范围是0到size-1
            if (o.equals(x.item))//假设尾节点恰好满足条件，那么返回的index就是size-1值，所以上面一行用index++的原因。
                return index;
        }
    }
    return -1;
}

node

根据索引返回链表中的节点，这是一个关键方法

通过它可以直接复用链表遍历的所有方法，因为node返回index指向的节点，那么套用入参为节点类型的方法即可完成复用

注意索引指向的节点：例如index=2，表示指向第3个节点

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
//如果索引小于链表长度的一半，则从链表头节点开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first; //应对index=0的情况，此时无需进入for，直接返回x
        for (int i = 0; i < index; i++) //针对其他节点，注意是从0开始遍历，如果index=2，对应的节点位置是在第3个节点位置，因为x=first算是一次，接下来在for循环恰好可以遍历2次，总共三次。
            x = x.next;
        return x;
    } else {
      	//如果索引大于链表长度的一半，则从尾部节点开始遍历
        Node<E> x = last; //从尾部节点开始，注意是从size-1开始，考察index=size-1时，则i>index不会满足，不进入for循环而直接返回尾节点
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

add方法-添加对象

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

add方法-索引

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index); // 这里的index可以取到size值：index>=0 && <=size
	
    if (index == size) // 如果index就是size大小，那么说明是要在尾部插入新元素
        linkLast(element);
    else
      // 注意：在这里是将新元素添加到node(index)这个节点的前面
        linkBefore(element, node(index));  
  		// pred<-->ele<-->node(index)
}

public E remove(int index) {
    checkElementIndex(index); // remove时的索引判断范围：index>=0&&index<size,如果取index<=size，那么=号就会造成越界
    return unlink(node(index)); // nodex(index)找到index指向的节点，然后复用unlink方法完成删除节点
}

peek

记着：先取出头节点，然后判断是否为null在做出其他操作处理

public E peek() {
    final Node<E> f = first;  //
    return (f == null) ? null : f.item;
}

模拟stack的方法

public void push(E e) {
    addFirst(e);
}

    public E pop() {
    return removeFirst();
}

removeLastOccurrence

从尾部移除首次符合给定item的节点

public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
      	//从尾部遍历，删除首次符合条件的节点
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);// 找到这个节点后，用unlink删除之
                return true;
            }
        }
    }
    return false;
}

toArray

创建一个size同大的数组，然后从链表中，一个个拷贝到这个空数组中

public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0; // 当然是从0开始拷贝
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item; //如果有2个节点，那么此时i++=1,也即res[1]=第2个节点的item
    return result;
}

链表迭代器创建

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

		// 内部迭代器类
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index); //next指向index对应的节点，注意这里不是
          /*x.next=node(index)的写法，next节点就是指代当前index节点
          foo->bar->foobar->null,node(index=1)就是指bar这个节点，next也是指向bar这个节点，而不是next指向node(index=1)的next节点——foobar
          */
            nextIndex = index; 
          // 其实next和nextIndex都是指向给定index的初始位置，然后不断移动指针
        }

        public boolean hasNext() {
            return nextIndex < size; //只要遍历指针不超过size，就说明还有节点
        }
/*
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
         ListIterator<String> listIterator=list.listIterator(1); 
         System.out.println(listIterator.next());  //输出：bar节点，注意这里不是输出foobar节点！！！
  */
        public E next() {
          /*checkForComodification方法很实用，因为在创建链表迭代器时就默认将expectedModCount=modCount，
          因此在迭代过程中，如果没有删除或者写入节点操作，那么modCount计数将不会改变。
             final void checkForComodification() {
                  if (modCount != expectedModCount)
                      throw new ConcurrentModificationException();
              }
              //实际场景
              while (listIterator.hasNext()){
                   System.out.println(listIterator.next());
                   list.remove("bar");
               }
            */
          // 1、查看是否迭代过程有写操作
            checkForComodification();
          // 2、没有节点可迭代，抛出异常
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next; //暂存当前节点结果，用于返回
            next = next.next; //next指针指向下一个节点
            nextIndex++;// nextIndex指针自增
            return lastReturned.item; // 第一次调用next()方法不要以为是调用下一个节点，而是指向当前首个节点
        }

      	
        public boolean hasPrevious() {
          //因为是从index开始反向迭代，nextIndex=index,然后nextIndex自减，只要自减到不等于0就说明还有节点，为何不是=0？
            return nextIndex > 0;
        }

        //反向迭代
      /*
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
         ListIterator<String> listIterator=list.listIterator(1); 
         System.out.println(listIterator.previous()); //输出：虽然index=1指向bar这个节点，但输出时foo节点
        */
        public E previous() {
          	//前面两个条件同next()
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev; //当前节点的上一个节点
            nextIndex--;
            return lastReturned.item;// 返回next（index指向的节点）的前一个节点
        }

        public int nextIndex() {
            return nextIndex; // 在new阶段， nextIndex = index，绝不是index的下一个索引值
        }

        public int previousIndex() {
            return nextIndex - 1; //因为index作为nextIndex，那么index的前一个指针值显然就是nextIndex-1
        }

      
      /*
      remove方法的使用：必须有next()迭代器调用后，才能执行一次remove，每次remove结束后，lastReturned会置为null，说明每次next()对应一次remove，否则会抛出错误
      
      （1） 未启用过next()
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator(1);
        listIterator.remove(); //lastReturned表示上次返回的节点，显然这里还没开始调用next()就直接调用remove，因此抛出错误
        System.out.println(list);   
        
        （2）启用过next()
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator(1);
        listIterator.next(); // bar
        listIterator.remove();// 删除的bar节点，不是 forbar！
        System.out.println(list); // [foo, foobar]
      */
      
        public void remove() {
            checkForComodification();
           // 若还没使用next()迭代一次，抛出非法状态
            if (lastReturned == null)
                throw new IllegalStateException();
						// 调用next()后，next指向索引index的节点，且lastReturned也是指向next
            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned); // 删除的是index节点
            if (next == lastReturned)
                next = lastNext; //将next指针指向lastReturned的下一个节点
            else
                nextIndex--;
            lastReturned = null; // 这里lastReturned为null保证了每次next()才能remove
            expectedModCount++;
        }

      	// 同样，迭代器需要启用一次next()方法，调用set方法才不会抛出异常，这是因为next()方法调用会将lastReturned指向next首个遍历节点，否则就认为在无指向节点情况非法使用set方法
			/*
			  list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator(1);
        listIterator.next(); // bar
        listIterator.set("newbar");// 因为next指向bar，而lastReturned指向next，因此lastReturned执行bar节点，执行lastReturned.item="newbar"覆盖了bar值，
        输出为：[foo, newbar, foobar]
        */
      
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;//其实这里的lastReturned就是next，而next指向当前index节点。          
        }

      	/*首先，add是不需要next()来启动迭代器的
      	（1）next指向非空节点
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator(1);  next指向node(index=1)也即next指向bar这个节点
        listIterator.add("newbar"); // next指向非空节点，则使用linkBefore(e,next)
        System.out.println(list); // [foo, newbar, bar, foobar]

  		 （2）next指向空链表
        LinkedList<String> list = new LinkedList<>();
        ListIterator<String> listIterator = list.listIterator();
        listIterator.add("newbar"); //空链表，直接linkLast(e)
        System.out.println(list); 
        
       （3）next指向非空链表的尾节点
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator(3); //checkPositionIndex(index)，可等于size
        listIterator.add("newbar"); //因为index的值为size=3，因此index指向第4个节点，即为null，因此根据next = (index == size) ? null : node(index)；next指向null，故在add内部使用linkLast(e)
        System.out.println(list);
        */
        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

  /*
        LinkedList<String> list = new LinkedList<>();
        list.add("foo");//0
        list.add("bar");//1
        list.add("foobar");//2
        ListIterator<String> listIterator = list.listIterator();
//        list.forEach(s->System.out.println(s+":"+s.length()));
        listIterator.next(); // 已经消耗bar这个节点，next()方法内部，lastReturned指向next，然后next指针更新，将next=next.next，
        //剩下的两个节点将会被forEachRemaining输出
        listIterator.forEachRemaining(s->System.out.println(s+":"+s.length()));

  
  */
      
        public void forEachRemaining(Consumer<? super E> action) {
          	//  action：非空的lambda函数
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
              	// 在next()方法内部，next = next.next，也即next已经更新到指向下一个节点，因此可以实现“Remaining”的效果
              // 当前节点处理时next
                action.accept(next.item);
                lastReturned = next; // 更新lastReturned指针指向新节点
                next = next.next; //更新next指针指向新节点
                nextIndex++;// 索引加1
            }
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

反向迭代器

实例：

LinkedList<String> list = new LinkedList<>();
list.add("foo");//0
list.add("bar");//1
list.add("foobar");//2
Iterator<String>  itr=list.descendingIterator();
System.out.println(itr.next());

descendingIterator

设计很巧妙：使用一个私有方法将正向迭代器的相关方法封装以下，然后在一个公开方法内部new一个私有迭代器

public Iterator<E> descendingIterator() { // 注意：公开方法是Iterator类型，不是ListIterator，因此在实例使用中使用Iterator<String>  itr=list.descendingIterator()  创建反向迭代器
    return new DescendingIterator();
}

/**
 * Adapter to provide descending iterators via ListItr.previous
 */
private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size()); // 这里的index取的是size值，因此在next()方法调用previous()方法时，previous()方法内部的next是指向null的，因此DescendingIterator的next()方法首次是返回last节点。
  
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

参考previous方法

  public E previous() {
      checkForComodification();
      if (!hasPrevious())
          throw new NoSuchElementException();
//如果ListItr itr = new ListItr(size()) ，那么next指针是指向null，因此根据下面可知，当previous()调用时，next要被更新指向last
      lastReturned = next = (next == null) ? last : next.prev;
      nextIndex--;
      return lastReturned.item;
  }