LinkedList底层链表结构
- 前言概述
- 核心代码
- 效果展示
第一章 前言概述
第01节 简述说明
LinkedList 底层
LinkedList 底层采用的是 双向链表完成，特点是 增删快，查询慢。
LinkedList 体系
第02节 特有方法
说明
在 LinkedList 当中，包含有大量的操作头和尾的方法。
例如：
1. 添加头、添加尾
2. 删除头、删除尾
3. 查询头、查询尾
方法
【1】添加相关的方法
public void addFirst(E e){ .... } //添加头
public void addLast(E e) { .... } //添加尾
public void push(E e){ .... } //添加头（底层调用的也是添加头的方法）将元素压入到集合的0号索引位置
【2】删除相关的方法
public E removeFirst() { .... } //删除头
public E removeLast() { .... } //删除尾
public E pop() { ..... } //删除尾（底层调用的也是删除尾的方法）删除掉最后一位索引位置的元素
【3】获取相关的方法
public E getFirst(){ .... } //获取头
public E getLast() { .... } //获取尾
第二章 核心代码
第01节 成员变量
成员变量相关的核心代码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
/**
* 集合的长度大小
*/
transient int size = 0;
/**
* 头节点
*/
transient Node<E> first;
/**
* 尾节点
*/
transient Node<E> last;
/**
* 空参数构造方法
*/
public LinkedList() {
}
/**
* 带参数构造方法，当前方法会调用 addAll()方法，
* 此方法来自于祖父接口 Collection接口，表示将 c集合当中的数据添加到 LinkedList集合对象当中
* 例如:
* Collection<String> c = new ArrayList<>();
* c.add("hello");
* c.add("world");
* 当我们创建 LinkedList集合对象的格式如下的时候
* LinkedList<String> linked = new LinkedList<>(c);
* 那么在 linked 当中包含的数据就是 "hello" 和 "world"
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 来自于 LinkedList 底层的内部类，主要是记录节点的对象
* 记录的数据包括三部分: item next prev
* 成员变量 E item： 这里的 item 的泛型是 E 表示当前存放的元素
* 成员变量 Node<E> next: 这里的 next 表示的是下一个节点的对象
* 成员变量 Node<E> prev: 这里的 prev 表示的是上一个节点的对象
*/
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;
}
}
}
链表的效果图（理解Node内部类）
第02节 成员方法
核心代码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
/**
* 将指定的元素追加到此列表的末尾，这个方法等效于 void addLast(E e) 方法
* 参数e: 表示要添加到此列表的元素
* 返回值是 true 表示无论什么元素都能添加成功，因为是List系列的集合，假如是Set系列的则可能会为false
* 方法体当中调用的是 下面的 linkLast(e) 这个方法
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 将参数 e 添加到linkedList集合的最后
* final Node<E> l = last 表示的是记录当前尾节点的数据值，这里的 last 是成员变量
* Node<E> newNode = new Node<>(l, e, null) 表示创建新的节点对象，将l和e作为参数传入
* last = newNode 表示记录 last 的值是最新对象的地址值
* if (l == null) 判断是否为null 如果是null则表示是第一个元素，那么就记录 first=newNode
* 否则记录 l.next = newNode; 表示不是第一个节点，则记录为 l.next=newNode
* 当做好记录之后，长度 size 自增，来自于父类的变量 modCount 自增
*/
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++;
}
}
第三章 效果展示
第01节 案例代码
public class Test {
public static void main(String[] args) {
LinkedList<String> linked = new LinkedList<>();
linked.add("aa");
linked.add("bb");
linked.add("cc");
linked.add("dd");
System.out.println(linked); //[aa, bb, cc, dd]
}
}
第02节 过程实现
核心代码分析
核心方法分析
//说明: first 和 last 都是LinkedList 集合的成员变量Node<E>的对象
void linkLast(E e) {
//这里的 l 记录的是 last 当中的地址信息，刚开始的时候 last 记录的是null
final Node<E> l = last;
//这里的 newNode 就是创建的节点的对象，记录的节点的地址值，例如地址值 0x01
final Node<E> newNode = new Node<>(l, e, null);
//这里将节点记录的地址值，赋值给了 last 那么last当中记录地址，也就是 0x01
last = newNode;
//判断之前记录的l是否为null, 如果是第一个元素，之前没有 l 则为 null
if (l == null)
//当第一个元素的时候，LinkedList的成员变量 first 就记录为 上面地址 0x01
first = newNode;
else
//如果不是null, 则表示之前存在对象，那么前一个对象的下一个节点就记录地址 0x01
l.next = newNode;
//当上面的内容记录完毕之后，长度 size改变, 父类成员变量modCount值也改变
size++;
modCount++;
}
小结说明
- 这里的变量
l记录的是上一个节点Node的地址值，如果是第一个元素，则l为null值- 这里的变量
newNode对象当中，包含着三个部分，分别是 前一个节点的地址值、当前的元素值、下一个节点的地址值- 两个变量
first和last都是LinkedList集合当中维护的成员变量，他们的类型都是Node<E>这种类型
图1（添加第一次数据）
图二（添加第二次数据）
图三（添加第三次数据）
图四（添加第四次数据）