手机版
你好,游客 登录 注册
背景:
阅读新闻

List源码解析之LinkedList 源码分析

[日期:2017-11-26] 来源:简书  作者:jimzhang [字体: ]

LinkedList简介

实现了List和Deque接口,既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)(处理栈和队列问题,首选ArrayDeque,它的性能比LinkedList作栈和队列使用好很多)。
LinkedList是一种双向链表,通过firstlast引用分别指向链表的第一个和最后一个元素。
LinkedList是非线程安全的,也就是说它不是同步的,适合单线程环境使用;需要多个线程并发访问,可以先采用Collections.synchronizedList()方法对其进行包装。
LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。

属性和构造函数

transient int size = 0;    //数量    
transient Node<E> first;   //首节点    
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;
  }
}


/** * Constructs an empty list. */
public LinkedList() {
}

/** * 构造一个包含指定collection 的元素的列表,这些元素按照 * 该collection 的迭代器返回它们的顺序排列的 */
public LinkedList(Collection<? extends E> c) {
  this();
  addAll(c);
}

存储

set(int index, E element)

// 用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素  
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

add(E e)

// 添加指定元素到链表尾部,花费时间为常数时间
publicbooleanadd(E e) {
  linkLast(e);
  return true;
}

/** * Links e as last element. 链接e作为最后一个元素,默认向表尾节点加入新的元素 */
voidlinkLast(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++;
}

add(int index, E element)

// 在指定位置插入
publicvoidadd(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// 下标位置越界检查
privatevoidcheckPositionIndex(int index) {
    if (!isPositionIndex(index))
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

  /**   * Inserts element e before non-null Node succ.   */
  voidlinkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
      first = newNode;
    else
      pred.next = newNode;
    size++;
    modCount++;
  }

addAll(Collection<? extends E> c)

// 按照指定collection 的迭代器所返回的元素顺序,将该collection 中的所有元素添加到此列表的尾部
publicbooleanaddAll(Collection<? extends E> c) {
  return addAll(size, c);
}

// 具体看源码吧

读取

get(int index)

// 返回指定下标的元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

删除

1.先找到要删除元素的引用,2.修改相关引用,完成删除操作

remove(int index)

使用下标计数

// 删除指定位置的元素,并返回
public E remove(int index) {
  checkElementIndex(index); // 检查下标是否越界
  return unlink(node(index));
}

    /**     * Unlinks non-null node x.     */
    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; //let GC work
        size--;
        modCount++;
        return element;
    }

remove(Object o)

使用equales方法

// 删除指定元素
publicbooleanremove(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;
}

增删元素的时候,只需改变指针,不需要像数组那样对整体数据进行移动、复制等消耗性能的操作。

遍历

遍历的时候耗时,for循环(无穷大) > ForEach > 迭代器,优先使用迭代器方式。

```Java
for(Iterator it = list.iterator();it.hasNext();){}

```

队列操作

E peek()

// 获取第一个元素
public E peek() {
  final Node<E> f = first;
  return (f == null) ? null : f.item;
}

E peekFirst()

// 获取第一个元素,同E peek() 
public E peekFirst() {
  final Node<E> f = first;
  return (f == null) ? null : f.item;
}

E peekLast()

// 获取最后一个元素
public E peekLast() {
  final Node<E> l = last;
  return (l == null) ? null : l.item;
}

E pop()

// 移除第一个元素并返回
public E pop() {
  return removeFirst();
}

E pollFirst()

// 移除第一个元素,同E pop()
public E pollFirst() {
  final Node<E> f = first;
  return (f == null) ? null : unlinkFirst(f);
}

E pollLast()

// 移除最后一个元素
public E pollLast() {
  final Node<E> l = last;
  return (l == null) ? null : unlinkLast(l);
}

push(E e)

// 队首添加一个元素
publicvoidpush(E e) {
  addFirst(e);
}

总结

  1. 基于双向循环链表实现,不存在容量不足的问题,没有扩容的方法
  2. 增删元素快,查找慢
  3. 元素排列有序,可重复,可为null
  4. 实现了栈和队列的操作方法,因此也可以作为栈、队列和双端队列来使用。
  5. 非同步,线程不安全

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-11/148892.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款