Java容器源码LinkedList原理解析

Java容器源码LinkedList原理解析

LinkedList简介

LinkedList是一个使用双向链表结构实现的容器，与ArrayList一样，它能动态扩充其长度，LinkedList相较于ArrayList，其任意位置插入速度比ArrayList要快，但是其查询速度要比ArrayList要慢；LinkedList继承自AbstractSequentialList，实现了List、Deque、Cloneable、Serializable接口。

LinkedList UML图如下：

和ArrayList一样，LinkedList也不是一个线程安全的容器。

LinkedList源码分析

构造方法

LinkedList有两个构造方法：

public LinkedList() {

}

//从已有的一个容器创建一个LinkedList对象

public LinkedList(Collection extends E> c) {

this();

addAll(c);

}

addAll()方法：

public boolean addAll(Collection extends E> c) {

return addAll(size, c);

}

public boolean addAll(int index, Collection extends E> c) {

//检查index是否溢出

checkPositionIndex(index);

Object[] a = c.toArray();

int numNew = a.length;

if (numNew == 0)

return false;

//获取第index位置的node元素和node的前一个元素

//succ：第index位置的node元素

//pred：index位置前一个node元素

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

}

add方法

LinkedList也有两个add方法，如下：

public boolean add(E e) {

//添加元素到队尾

linkLast(e);

return true;

}

public void add(int index, E element) {

//检查index是否溢出

checkPositionIndex(index);

if (index == size)

//index == size，直接添加到队尾

linkLast(element);

else

//index != size，添加元素到index位置

linkBefore(element, node(index));

}

linkLast方法：

void linkLast(E e) {

final Node l = last;

//新建一个node，将其前一个元素指针指向原链表的最后一个元素

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

//更新尾指针

last = newNode;

if (l == null)

//若原last==null说明此时链表就一个元素

first = newNode;

else

//更新原链表尾元素指针

l.next = newNode;

size++;

modCount++;

}

linkBefore方法：

void linkBefore(E e, Node succ) {

// assert succ != null;

//获取指定位node元素的前一个元素pred

final Node pred = succ.prev;

//新建一个node，将其前指针指向pred元素

final Node newNode = new Node<>(pred, e, succ);

//将指定位置的node元素的前指针指向新元素，完成插入

succ.prev = newNode;

if (pred == null)

first = newNode;

else

pred.next = newNode;

size++;

modCount++;

}

获取指定位置node指针方法node：

Node node(int index) {

// assert isElementIndex(index);

//index > size/2时，说明在链表前半段，从前往后搜索

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

Node x = first;

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

x = x.next;

return x;

//index < size/2时，从后往前搜索

} else {

Node

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

x = x.prev;

return x;

}

}

get方法也比较简单，首先检测index是否溢出，然后直接找到index位置的元素，并返回其item。

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

x = x.prev;

return x;

}

}

get方法也比较简单，首先检测index是否溢出，然后直接找到index位置的元素，并返回其item。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。