LinkedList源码解析
源码 解析 LinkedList
2023-06-13 09:15:59 时间
转载请以链接形式标明出处: 本文出自:103style的博客
base on jdk_1.8.0_77
目录
- 简介
LinkedList
的变量介绍LinkedList
的构造函数LinkedList
的数据操作函数- 小结
- 参考文章
简介
LinkedList
和ArrayList
一样,都实现了List
接口,但其内部的数据结构有本质的不同。LinkedList
是基于 链表 实现的(通过名字也能区分开来),所以它的 插入和删除 操作比ArrayList
更加高效。但也是由于其为基于链表的,所以 随机访问的效率 要比ArrayList
差。
LinkedList
继承自AbstractSequenceList
,实现了List
、Deque
、Cloneable
、java.io.Serializable
接口。AbstractSequenceList
提供了List
接口骨干性的实现以减少实现List
接口的复杂度,Deque
接口定义了双端队列的操作。在
LinkedList
中除了本身自己的方法外,还提供了一些可以使其作为栈、队列或者双端队列的方法。这些方法可能彼此之间只是名字不同,以使得这些名字在特定的环境中显得更加合适。
LinkedList
也是 fail-fast 的(前边提过很多次了)。
LinkedList的变量介绍
-
transient int size = 0;
:链表长度 -
transient Node<E> first;
:头节点 -
transient Node<E> last;
:尾节点
LinkedList的构造函数
无参构造函数没做啥操作,有参的则是进行数据添加操作,下面会介绍。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList的数据操作函数
node(int index)
:获取对应节点addFirst(E e)
andaddLast(E e)
: 添加头尾节点getFirst()
andgetLast()
: 获取头尾节点remove()
、removeFirst()
andremoveLast()
:删除头尾节点remove(int index)
andremove(Object o)
: 删除对象get(int index)
andset(int index, E element)
:获取和设置对应节点peek()
、peekFirst()
andpeekLast()
:获取对应节点的值element()
:获取头节点的值poll()
、pollFirst()
andpollLast()
:返回对应节点,并从链表中删除offer(E e)
、offerFirst(E e)
andofferLast(E e)
:添加节点push(E e)
:插入一个节点到头部pop()
:删除头部一个节点
node(int index) 获取对应节点
- 根据索引的位置靠近头还是尾,靠近那头则从那头开始遍历查找。
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
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;
}
}
addFirst(E e) and addLast(E e) 添加头尾节点
addFirst(E e)
构建节点newNode
,赋值first = newNode
,如果之前的头节点f
为空则将last
设置为newNode
,否则将f
的prev
节点为newNode
.addLast(E e)
构建节点newNode
,赋值last = newNode
,如果之前的尾节点l
为空则将first
设置为newNode
,否则将l
的next
节点为newNode
.
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
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++;
}
element() 、getFirst() and getLast() 获取头尾节点
- 如果头尾节点为空则会抛出异常
NoSuchElementException
,否则返回对应的item
值。
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
remove()、removeFirst() and removeLast() 删除头尾节点
remove()
即为删除头节点- 删除即为更新节点的
prev
和next
节点。
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
remove(int index) and remove(Object o) 删除对象
remove(int index)
会检查下标,然后删除节点remove(Object o)
则会更具o
是否为null
用=
或equals
找到对应的节点,再删除。删除成功会返回ture
,失败则为false
.
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object o) {
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);
return true;
}
}
}
return false;
}
get(int index) and set(int index, E element)
- 都先检查索引,
get
直接返回节点的值,set
则修改节点的值并返回之前的旧值。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
peek()、peekFirst() and peekLast()
- 返回头尾节点的值,如果节点为
null
再返回null
.
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
poll()、pollFirst() and pollLast()
- 返回头尾节点,并总链表中移除
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
offer(E e)、offerFirst(E e) and offerLast(E e)
- 添加节点
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
push(E e)
- 插入一个节点到头部
public void push(E e) {
addFirst(e);
}
pop()
- 删除头节点
public E pop() {
return removeFirst();
}
小结
- LinkedList查找类似二分查找, 靠近那边则从那边开始查。
参考文章
以上
相关文章
- 优酷地址解析php源码
- Hmily 源码解析(一)
- Hmily 源码解析 (三) —— himly事务上下文
- Android 源码解析 之 setContentView「建议收藏」
- Lucene源码解析–TokenStream和AttributeSource
- 【说站】虎年2022新UI春节送祝福微信小程序源码 支持多种流量主
- Demo佛萨奇2.0魔豹联盟系统开发技术源码解析
- SecurityAutoConfiguration源码解析
- Thread的源码解析
- arrayqueue源码_一次视频解析源码
- jdk1.7 hashmap扩容_Java并发实现原理:JDK源码剖析
- mybatis3源码解析--核心流程
- mybatis3源码解析--spring下mapper注册详解
- react源码解析9.diff算法
- PriorityQueue源码解析
- react源码解析10.commit阶段
- EVM 源码解析
- ArrayList源码解析
- 六张图详解LinkedList 源码解析
- 详解HashMap源码解析(上)
- Spring源码学习方法
- kafka源码解析之十三KafkaHealthcheck详解编程语言
- LinkedList源码解析详解编程语言
- Linux内核源码之旅:一次全面、深度的导读(linux内核源码导读)
- 解析Linux SS 源码探索: 一探究竟(linuxss源码)
- MySQL必知必会:解析源码(mysql必知必会源码)