Java源码-集合-LinkedList

时间:2022-08-18 17:20:50

基于JDK1.8.0_191

介绍

  LinkedList是以节点来保存数据的,不像数组在创建的时候需要申请一段连续的空间,LinkedList里的数据是可以存放在不同的空间当中,然后以内存地址作为寻找的工具,比如第一个节点里保存了第二个节点的地址信息,第二个节点又保存了第三个节点的地址信息,以此类推

节点Node的代码如下

    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;
}
}

LinkedList有以下特性

  • 是双向链表,每个节点保存着下一个节点的信息,也保存了上一个节点的信息
  • 不是线程安全的,线程安全可以通过
List list = Collections.synchronizedList(new LinkedList(...));

实现

  • LinkedList可以作为堆栈和队列使用,它包含了许多对应的方法,比如poll、push等等

构造函数

  LinkedList的构造函数比较简单,它不需要初始化大小,因为它不存在扩容的要求

  • public LinkedList();

    第一个是无参构造函数,方法体里什么都不做

  • public LinkedList(Collection<? extends E> c);

    第二个是带初始化数据的,也就是创建一个带有c数据的LinkedList,c数据通过LinkedList的addAll方法插入

部分源码解析

点击查看详细内容

//在末尾插入节点,主要通过linkLast()实现
public boolean add(E e);
/**
* 在末尾插入节点
*/
void linkLast(E e) {
//LinkedList专门有last对象,用来保存最后一个节点信息
final Node l = last;
//创建新的节点
final Node newNode = new Node(l, e, null);
last = newNode;
//如果之前LinkedList是null的,那新插入的就是第一个节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//在指定位置插入节点
public void add(int index, E element) {
checkPositionIndex(index);
//如果指定位置是最后,调用linkLast方法
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
} //在指定节点前面插入节点,下面代码的逻辑就是改变插入位置前一个节点,当前要插入的节点和后一个节点的prev和next的指向
void linkBefore(E e, Node<E> succ) {
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++;
} //在指定位置插入集合
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
//转为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//要插入位置的前一个节点和后一个节点
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//循环插入节点
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//处理要插入位置的后一个节点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
} size += numNew;
modCount++;
return true;
} //循环遍历LinkedList,然后把所有数据设为NULL
public void clear(); //循环遍历LinkedList,然后做==或者equals操作
public int indexOf(Object o);

LinkedListList的查询

  LinkedList是不建议做频繁的查询操作,那么如果需要查询,哪种更快呢,我们可以试一下

  • 第一种
  for(int i = 0; i < list.size; i++){
list.get(i);
}

这种是最差的方式,完全不用测试,因为在for循环里,get操作又是通过另一个for循环实现的,所以这个操作等于是for循环的嵌套

  • 第二种
for(String str : list){}

在1千万数据时,耗时150ms

  • 第三种
for(Iterator<String> iter = list.iterator(); iter.hasNext();iter.next();){}

同样的数据耗时165ms,和第二种差不多

我们通过查看编译后的代码可以知道,第二种编译后的代码是

for(Iterator var4 = list.iterator(); var4.hasNext(); var5 = (String)var4.next()) {}

其实也就是通过迭代的方式

而第三种是

Iterator iter = list.iterator();
while(iter.hasNext()) {iter.next();}

通过while循环操作

本质上第二种和第三种差不多,只要不使用第一种就行