LinkedList源码解析(手把手带你熟悉链表)
前言
链表是常见的数据结构之一,但是很多同学只听说过链表,并不知道什么是链表,所以本文将会带领各位同学手写一个LinkedList,源码跟官方会有点不一样,不过思路是大概相同的,最后再带领大家读官方源码
为了降低源码难度简化泛型代码,手写的LinkedList只能添加String类型数据
什么是链表?
可以理解为,把一些数据按照顺序排好,手拉手 每一个数据就是一个节点,所有节点连在一起,就组成了链表
LinkedList的节点定义
LinkedList是双链表,所以有左节点和右节点,我们先定义一个实体类,这个实体类就可以理解为节点
/**
* 节点实体类
*/
private static class NodeBean {
NodeBean leftNode; //左节点
String value; //节点的值
NodeBean rightNode; //右节点
}
复制代码节点怎么连接?
看完上面的图片,应该大概知道两个节点的连接方法了,我们只需要:
节点1.右节点 = 节点2
节点2.左节点 = 节点1
复制代码我们先实现链表的add方法,add方法其实就是将两个节点连接:
/**
* 添加值
*/
public void add(String value) {
//先获取尾节点(上一个节点)
NodeBean lastNode = this.lastNode;
//创建一个新节点
NodeBean newNode = new NodeBean();
//为节点赋值
newNode.value = value;
//左节点为最后一个节点(尾节点)
newNode.leftNode = lastNode;
//由于是添加节点,所以右节点为null,可以不写
newNode.rightNode = null;
//将成员变量的最后一个节点改为当前新节点
this.lastNode = newNode;
//判断头节点是否为空
if (this.firstNode == null) {
//如果为空说明当前是第一个节点,需要把头结点也设为当前节点
this.firstNode = newNode;
}else{
//如果不为空,需要把前一个节点的右节点指向当前节点
//两个节点相连接的条件是:
// 1. 前一个节点的右节点指向当前节点
// 2. 当前节点的左节点指向上一个节点
lastNode.rightNode = newNode;
}
//链表长度+1
size++;
}
复制代码节点怎么断开?
两个节点断开只需要将自己的上一个节点的右节点指向自己的下一个节点左节点,同时自己的下一个节点的左节点,指向上一个节点的右节点
注意看下图箭头方向,这样节点2就可以直接断开,节点1和节点3直接连接,这里也可以很明显的看出,链表增删很快,只需要断开前后节点就可以
先看一下断开节点的大概代码思路:
节点2.左节点 = null
节点2.右节点 = null
节点1.右节点 = 节点3
节点3.左节点 = 节点1
这样就可以断开当前节点,并且将链表重新连接起来
复制代码现在我们来实现remove(index)方法,根据索引删除指定节点:
/**
* 删除值
*/
public void remove(int index){
这里代码通过索引查找节点,为了简化代码,请忽略这里的代码
通过索引查找节点,下面会写到
...
***indexNode就是我们通过索引拿到的节点***
indexNode = 通过索引查找节点(index)
//拿到该节点的左节点、右节点以及值
NodeBean leftNode = indexNode.leftNode;
NodeBean rightNode = indexNode.rightNode;
//判断左节点是否为空,如果为空说明当前节点为(头结点)第一个节点
if (leftNode == null) {
this.firstNode = indexNode;
}else{
//左节点不为空,需要断开自己的左节点
indexNode.leftNode = null;
//将上一个节点的右节点连接到下一个节点
leftNode.rightNode = rightNode;
}
//判断右节点是否为空,如果为空说明当前为(尾节点)最后一个节点
if (rightNode == null) {
this.lastNode = indexNode;
}else{
//右节点不为空,需要断开自己的右节点
indexNode.rightNode = null;
//将下一个节点的左节点连接到上一个节点
rightNode.leftNode = leftNode;
}
//当前节点值置空
indexNode.value = null;
size--;
}
复制代码通过索引查找节点
1. 先拿到头节点
2. 拿到当前要查找的索引index
3. 循环index的次数
4. 每循环一次,就从头结点开始往后移动一个节点
复制代码现在我们来实现以下get(index)方法,通过索引获取置顶节点:
/**
* 通过索引获取节点的值
*/
public String get(int index){
//由于链表没有索引,所以只能一个一个遍历查找
//先拿到链表的第一个节点(头节点)
NodeBean firstNode = this.firstNode;
for (int i = 0; i < index; i++) {
//每次循环就从头结点往后挪动一个节点
firstNode = firstNode.rightNode;
}
//为了简化代码便于理解,这里不考虑tempNode为null的情况
return firstNode.value;
}
复制代码总结
- 链表的每个节点之间都有连接,如果新增节点只需要直接插入就行,所以==链表新增快==
- 链表断开节点只需要将自己的前后节点重新连接就可以,所以链表==删除快==
- 链表没有索引,查找需要循环整个链表,所以==查询慢==
MyLinkedList完整代码:
public class MyLinkedList {
private int size; //当前链表的长度
private NodeBean firstNode; //头节点
private NodeBean lastNode; //尾节点
/**
* 添加值
*/
public void add(String value) {
//先获取尾节点
NodeBean lastNode = this.lastNode;
//创建一个新节点
NodeBean newNode = new NodeBean();
//为节点赋值
newNode.value = value;
//左节点为最后一个节点(尾节点)
newNode.leftNode = lastNode;
//由于是添加节点,所以右节点为null,可以不写
newNode.rightNode = null;
//将成员变量的最后一个节点改为当前新节点
this.lastNode = newNode;
//判断头节点是否为空
if (this.firstNode == null) {
//如果为空说明当前是第一个节点,需要把头结点也设为当前节点
this.firstNode = newNode;
}else{
//如果不为空,需要把前一个节点的右节点指向当前节点
//两个节点相连接的条件是:
// 1. 前一个节点的右节点指向当前节点
// 2. 当前节点的左节点指向上一个节点
lastNode.rightNode = newNode;
}
//链表长度+1
size++;
}
/**
* 删除值
*/
public void remove(int index){
//先找到当前索引对应的节点
//由于链表没有索引,所以只能一个一个遍历查找
//先拿到链表的第一个节点(头节点)
NodeBean indexNode = this.firstNode;
for (int i = 0; i < index; i++) {
//每次循环就从头结点往后挪动一个节点
indexNode = indexNode.rightNode;
}
//拿到该节点的左节点、右节点以及值
NodeBean leftNode = indexNode.leftNode;
NodeBean rightNode = indexNode.rightNode;
//判断左节点是否为空,如果为空说明当前节点为(头结点)第一个节点
if (leftNode == null) {
this.firstNode = indexNode;
}else{
//左节点不为空,需要断开自己的左节点
indexNode.leftNode = null;
//将上一个节点的右节点连接到下一个节点
leftNode.rightNode = rightNode;
}
//判断右节点是否为空,如果为空说明当前为(尾节点)最后一个节点
if (rightNode == null) {
this.lastNode = indexNode;
}else{
//右节点不为空,需要断开自己的右节点
indexNode.rightNode = null;
//将下一个节点的左节点连接到上一个节点
rightNode.leftNode = leftNode;
}
//当前节点值置空
indexNode.value = null;
size--;
}
/**
* 通过索引获取节点的值
*/
public String get(int index){
//由于链表没有索引,所以只能一个一个遍历查找
//先拿到链表的第一个节点(头节点)
NodeBean firstNode = this.firstNode;
for (int i = 0; i < index; i++) {
//每次循环就从头结点往后挪动一个节点
firstNode = firstNode.rightNode;
}
//为了简化代码便于理解,这里不考虑tempNode为null的情况
return firstNode.value;
}
/**
* 获取链表长度
*/
public int getSize(){
return this.size;
}
/**
* 节点实体类
*/
private static class NodeBean {
NodeBean leftNode; //左节点
String value; //节点的值
NodeBean rightNode; //右节点
}
}
复制代码重点
- 如果你看完上面的增删查方法, 可以完全看懂了,就可以继续往下看了
- 如果你没看懂,请复制上面的完整代码到编辑器,自己断点研究一下
==如果上面的代码理解了,恭喜你! 现在你应该已经可以看懂官方源码了==
官方代码解析
节点实体类
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;
}
}
复制代码代码对比
插入节点
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++;
}
复制代码代码对比
断开节点
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;
size--;
modCount++;
return element;
}
复制代码代码对比
最后总结
- 如果现在你可以看懂官方的这三个方法了,那可以尝试自己去读剩下的部分方法,比如==unlinkFirst()和linkFirst()==
- 读源码并不可怕,只要理解源码的思路,顿时豁然开朗
