Board logo

标题: Java 容器源码分析之Queue(6) [打印本页]

作者: look_w    时间: 2018-12-17 17:47     标题: Java 容器源码分析之Queue(6)

LinkedList    现在,我们在来看看LinkedList对应Queue的实现部分。在前面一篇文章中,已经讨论过LinkedList里面Node的结构。它本身包含元素值,prev、next两个引用。对链表的增加和删除元素的操作不像数组,不存在要考虑下标的问题,也不需要扩展数组空间,因此就简单了很多。先看查找元素部分:
Java代码  [url=][/url]

[url=][/url]
public E getFirst() {      final Node<E> f = first;      if (f == null)          throw new NoSuchElementException();      return f.item;  }    public E getLast() {      final Node<E> l = last;      if (l == null)          throw new NoSuchElementException();      return l.item;  }  [url=][/url]


    这里唯一值得注意的一点就是last引用是指向队列最末尾和元素,和前面ArrayDeque的情况不一样。
    添加元素的方法如下:
[url=][/url]
public boolean add(E e) {      linkLast(e);      return true;  }    public boolean offer(E e) {      return add(e);  }    void linkLast(E e) {      final Node<E> l = last;      final Node<E> newNode = new Node<>(l, e, null);      last = newNode;      if (l == null)          first = newNode;      else          l.next = newNode;      size++;      modCount++;  }  [url=][/url]




    linkLast的方法在前一篇文章里已经分析过,就不再重复。
    删除元素的方法主要有remove():
[url=][/url]
public boolean remove(Object o) {      if (o == null) {          for (Node<E> x = first; x != null; x = x.next) {              if (x.item == null) {                  unlink(x);                  return true;              }          }      } else {          for (Node<E> x = first; x != null; x = x.next) {              if (o.equals(x.item)) {                  unlink(x);                  return true;              }          }      }      return false;  }    E unlink(Node<E> x) {      // assert x != null;      final E element = x.item;      final Node<E> next = x.next;      final Node<E> prev = x.prev;        if (prev == null) {          first = next;      } else {          prev.next = next;          x.prev = null;      }        if (next == null) {          last = prev;      } else {          next.prev = prev;          x.next = null;      }        x.item = null;      size--;      modCount++;      return element;  }  [url=][/url]




    这部分的代码看似比较长,实际上是遍历整个链表,如果找到要删除的元素,则移除该元素。这部分的难点在unlink方法里面。我们分别用要删除元素的前面和后面的引用来判断各种当prev和next为null时的各种情况。虽然不是很复杂,但是很繁琐。




欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0