疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

深入Java集合系列之LinkedList


 

   前言

  LinkedList底层使用的双端链表,即每个节点既包含指向其后继的引用也包括指向其前驱的引用,LinkedList实现了List接口,继承了AbstractSequentialList类,在频繁进行插入以及删除的情况下效率较高。

  LinkedList使用较多的是add、get和remove,源码的分析也将对这三个方法进行分析。

  add方法

  先看add方法:

  [code]public boolean add(E e) {

  //把e放在链表的最后一个位置

  linkLast(e);

  return true;

  }

  void linkLast(E e) {

  //last是链表最后一个节点的引用,现在l也指向最后一个节点

  final Node l = last;

  //调用Node(Node prev, E element, Node next)构造方法

  final Node newNode = new Node<>(l, e, null);

  //last节点指向newNode

  last = newNode;

  //如果l为空,则链表为空,直接把newNode链接在首节点后面即可,否则把newNode链接//在l节点的后面

  if (l == null)

  first = newNode;

  else

  l.next = newNode;

  //链表的元素个数增加1

  size++;

  //modCount是链表发生结构性修改的次数(结构性修改是指发生添加或者删除操作)

  modCount++;

  }

  可以看出,插入一个节点非常快,直接找到该位置的节点,修改节点的前驱以及后继的引用即可

  get方法

  下面看看get方法:

  [code]public E get(int index) {

  //检查index是否合法

  checkElementIndex(index);

  //如果合法就返回该节点位置的值

  return node(index).item;

  }

  //获取index位置上的节点

  Node node(int index) {

  //断言index在链表中

  // assert isElementIndex(index);

  //从第一个节点开始寻找直到index位置,然后返回index//位置的节点

  if (index < (size >> 1)) {

  Node x = first;

  for (int i = 0; i < index; i++)

  x = x.next;

  return x;

  } else {//从最后一个节点开始往前寻找节点

  Node x = last;

  for (int i = size - 1; i > index; i--)

  x = x.prev;

  return x;

  }

  }

  //检查index值的合法性

  private void checkElementIndex(int index) {

  if (!isElementIndex(index))

  throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  }

  //判断index是否存在于链表中

  private boolean isElementIndex(int index) {

  return index >= 0 && index < size;

  }

  可以看出获取index节点的值要从头或尾遍历链表,当数据量很大的时候,效率无疑是低下的

  remove方法

  最后看看remove操作:

  [code]public E remove(int index) {

  checkElementIndex(index);

  return unlink(node(index));

  }

  E unlink(Node x) {

  // assert x != null;

  //保存x节点的值

  final E element = x.item;

  //保存x节点的后继

  final Node next = x.next;

  //保存x节点的前驱

  final Node prev = x.prev;

  //如果前驱为null,说明要移除的是第一个节点,把First指向下一个节点就行

  if (prev == null) {

  first = next;

  } else {//否则,把x节点前驱的后继指向x的后继,并把x的前驱设置为null

  prev.next = next;

  x.prev = null;

  }

  //如果后继为null则要移除的是最后一个节点,则把last的引用指向x节点的前驱就ok

  if (next == null) {

  last = prev;

  } else {//否则,把x节点的后继的前驱设置为x节点的前驱,并x节点的后继设为null

  next.prev = prev;

  x.next = null;

  }

  //把x节点的值设为null,这样x就没有任何引用了,gc处理

  x.item = null;

  //把链表的size减少1

  size--;

  //结构性修改的次数增加1

  modCount++;

  //返回x节点的值,在移除之前已经保存在element中了

  return element;

  }

  LinkedList小结

  LinkedList是基于双向循环链表实现的,除了可以当做链表来操作外,还可以当做栈、队列和双端队列使用(⊙o⊙)哦。同样是非线程安全的。

  基于双端循环链表,并且头节点不存放数据

  在查找和删除元素的时候,分为元素null和不为null进行处理,允许元素为空

  不存在容量不足的问题

  Entry entry(int index)方法返回制定位置处的节点,使用加速动作。源码中先将index与长度size的一半(size >> 2)比较,如果index更小,那么就从位置0开始遍历到inde处,否则从size位置往前遍历,这样可以减少一部分不必要的遍历。实际上提高的效率有限。

  LinkedList是基于链表实现的,插入删除效率比较高,查找效率低。