集合框架——LinkedList集合源码分析
2024-09-18 09:03:52
目录
总结：
- LinkedList继承自List，具备有序性
- LinkedList继承自Deque，具备链表关联性
- LinkedList集合进行增删改查操作底层实际是操作Node节点的前后链接关系
- LinkedList进行增删操作时，仅需要操作节点的前后链接关系，因此效率较ArrayList高
- LinkedList进行查找操作时，必须从头或者从尾进行查找，因此较底层依靠数组进行存储的ArrayList查找效率低
示例代码
public class LinkedList01 {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList(); //执行第1步
linkedList.add(1); //执行第2步
linkedList.add(2); //执行第3步
linkedList.add(3); //执行第4步
linkedList.add(1 , new Intger(8)); //执行第8步
linkedList.add(5);
linkedList.remove(); //执行第5步
linkedList.remove(2); //执行第6步
linkedList.remove(new Integer(3)); //执行第7步
System.out.println(linkedList);
}
}
底层代码
第1步（初始化集合）
//LinkedList类默认构造器
public LinkedList() {}
transient int size = 0; //集合存放对象个数
transient Node<E> first; //集合中第一个节点
transient Node<E> last; //集合中最后一个节点
...
//AbstractSequentialList类默认构造器
protected AbstractSequentialList() {}
...
//AbstractList类默认构造器
protected AbstractList() {}
protected transient int modCount = 0;
...
//AbstractCollection类默认构造器
protected AbstractCollection() {}
...
//Object类默认构造器
public Object() {}
结果：还没有存放对象，属于空集合
第2步（往集合中添加一个元素）
public boolean add(E e) { //e = 1
linkLast(e);
return true;
}
...
void linkLast(E e) {
final Node<E> l = last;//l = null
final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，当前节点的prev和next属性均为null，将存入集合的对象赋值给item
last = newNode;//LinkedList集合的last属性指向新节点
if (l == null)//此时i=null，条件成立
first = newNode;//LinkedList集合的first属性指向新节点
else
l.next = newNode;
size++;//LinkedList集合的容量自加1
modCount++;//LinkedList集合修改次数自加1
}
......
//Node是LinkedList类的内部类
private static class Node<E> {
E item; //LinkedLIst实际存放的对象
Node<E> next; //当前节点的下一个节点
Node<E> prev; //当前节点的前一个节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
结果：集合中存放1个元素，LinkedList类中first与last属性相同，Node类中prev与next属性为null
第3步（往集合中添加第二个元素）
public boolean add(E e) { //e = 2
linkLast(e);
return true;
}
...
void linkLast(E e) {
final Node<E> l = last;//l = 1，表示上一个节点
final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，节点的prev属性指向上一个节点，item属性存放当前对象
last = newNode;//LinkedList集合的last属性指向新节点
if (l == null)//此时i！=null，条件不成立
first = newNode;
else
l.next = newNode;//上一个节点的next属性指向当前节点，即新创建的节点
size++;//LinkedList集合的容量自加1
modCount++;//LinkedList集合修改次数自加1
}
结果：
第4步（往集合中添加第三个元素）
public boolean add(E e) { //e = 3
linkLast(e);
return true;
}
...
void linkLast(E e) {
final Node<E> l = last;//l = 2，表示上一个节点
final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，节点的prev属性指向上一个节点，
item属性存放当前对象
last = newNode;//LinkedList集合的last属性指向新节点
if (l == null)//此时i！=null，条件不成立
first = newNode;
else
l.next = newNode;//上一个节点的next属性指向当前节点，即新创建的节点
size++;//LinkedList集合的容量自加1
modCount++;//LinkedList集合修改次数自加1
}
结果：
LinkedList添加元素流程示意图
第5步（删除集合中第一个元素）
public E remove() {
return removeFirst();
}
...
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
...
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item; //将集合中第一个节点的item 属性赋值给element
final Node<E> next = f.next; //将集合中第一个节点的next属性赋值给next
f.item = null;
f.next = null; // help GC
first = next; //将原集合中的第二个节点赋给集合的first属性
if (next == null)
last = null;
else
next.prev = null;//将原集合中的第二个节点的prev属性赋值为null
size--; //集合元素个数自减1
modCount++; //集合修改次数自加1
return element; //返回被删除的节点item值
}
第6步（根据索引来删除集合中的元素）
public E remove(int index) { //index = 2
checkElementIndex(index); //1.嵌套执行下边两个方法①和②，确定索引正确后继续往下执行
return unlink(node(index)); //2.执行方法③与④
}
...
//方法①
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
...
//方法②
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
...
//方法③
Node<E> node(int index) { //index = 2, size = 4
// assert isElementIndex(index);
if (index < (size >> 1)) { //index < size/2时
Node<E> x = first; //x记录首个节点
for (int i = 0; i < index; i++)
x = x.next; //找到索引位置对应的节点
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return 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; //此时该节点中的属性item、prev、next均为null
size--; //集合元素个数自减1
modCount++; //集合修改次数自加1
return element; //返回被删除节点中的内容
}
第7步（根据对象内容来删除集合中的元素）
//本方法可以用来删除集合中对象和null
public boolean remove(Object o) { o = new Integer(3)
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); //调用方法与第6步中流程一致
return true;
}
}
}
return false;
}
第8步（根据索引位置往集合中添加元素）
public void add(int index, E element) { //index=1, element = new Integer(8)
checkPositionIndex(index); //检查索引没有问题
if (index == size) //如果索引与集合大小相等
linkLast(element);
else
linkBefore(element, node(index)); //node(index)方法找到该索引位置的节点，然后采用linkBefore方法在其节点前链接入新的节点
}
...
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++;
}
...
void linkBefore(E e, Node<E> succ) { //e = new Integer(8)待链接入的节点，succ为原index位置的节点
// 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++;
}
最新文章
- Servlet学习四——传输文本
- MySql 导出excel
- WPF VlC 实现视频的播放（1）
- Android 使用 ksoap2-android 访问WebService(C#)
- python 列表函数
- 深入浅出Android动态载入jar包技术
- 课程助理For Windows（预览版，正方教务系统学生查分工具）
- Android 常用系统控件
- final的深入理解 - final数据
- Hadoop学习笔记-008-CentOS_6.5_64_yum安装mysql
- vue的双向绑定原理及实现
- BZOJ_3048_[Usaco2013 Jan]Cow Lineup _双指针
- S0.3 直方图
- like contains
- leetcode2
- 解析oracle的rownum（转）
- nginx如何处理请求
- Remove duplicates
- FreeRTOS 独立看门狗监测任务执行状态
- 增量式PID的matlab实现