1. 概述
通过类名可以想象到, 该类的结构是一个链表结构.
但是它是一个类似于数组的链表, 意思就是普通的添加操作与数组类似, 将新元素添加到链表的尾端. 并支持通过下标来进行访问.
它实现了Deque接口, 提供了栈和队列的操作, 也就是该类的主要功能吧.
对于元素的增删改比ArrayList强; 对于元素的查询不如ArrayList.
2. 构造函数
它提供了两个构造函数, 比ArrayList少一个构造方法那就是没有提供带有初始化容量的构造方法, 也是与该类的存储结构有关.
因为是链表结构, 所以不会有扩容操作, ArrayList的初始化容量是为了避免不必要的扩容操作.
2-1. 无参构造函数
/**
* Constructs an empty list.
*/
public LinkedList() {
}
2-2. 传入集合的构造函数
public LinkedList(Collection c) {
this();
addAll(c);
}
直接调用了addAll方法, 了解到这, 在下面解释addAll方法.
3. 存储结构
通过上面的解释, 知道它是一个链表结构, 由节点(Node)组成, 每个节点之间有相互指向的引用.
4. 操作
操作包含三部分:
List的增删改查操作
栈的进栈出栈
队列的进队列出队列
4-1. 查询
对于Java来说, 注重业务实现, 所以函数以及变量的见名知意比较重要. 所以我们日常中使用的话, 偏getFirst()和getLast()的使用比较多.
对于node(index)方法, 因为是链式结构, 所以需要从头结点一个一个的寻找, 源码中使用了一个二分进行了快速查询.
Nodenode(int index) {
// assert isElementIndex(index);
if (index (size 1)) {
Nodex = first;
for (int i = 0; i index; i++)
x = x.next;
return x;
} else {
Nodex = last;
for (int i = size - 1; i index; i--)
x = x.prev;
return x;
}
}
下面我们看一下getFirst()和getLast()的源码, 其它方法的源码类似, 就是找到节点返回节点值.
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
// 获取头结点
final Nodef = first;
if (f == null)
throw new NoSuchElementException();
// 返回头结点的值
return f.item;
}
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
// 获取尾节点
final Nodel = last;
if (l == null)
throw new NoSuchElementException();
// 获取尾节点的值
return l.item;
}
4-2. 添加
添加的方法有:
可以发现, 最终的方法落实到了linkFirst(E)和linkLast(E)两个方法.
源码:
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 获取链表的头节点
final Nodef = first;
// 创建一个新节点
final NodenewNode = new Node(null, e, f);
// 使头结点为新节点
first = newNode;
if (f == null)
// 如果原先的头结点为null, 说明链表为空链表, 给尾节点也为该新节点
last = newNode;
// 否则头结点的prev指向新节点
else
f.prev = newNode;
// 改变元素数量的大小
size++;
// 链表结构的改变次数
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Nodel = last;
final NodenewNode = new Node(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
4-3. 删除
删除操作就会涉及到节点之间引用关系的改变.
比如:
A - B - C = A - C
先把B的prev的next指向B的next, 再把B的next的prev指向B的prev, 然后把B置为null.
至于其它的删除方法, 也与之类似, 改变节点引用, 该节点置为null, size–, modCount–.
4-4. 修改
修改操作几乎用不到, 也是使用了List接口的set(int, E)方法.
很简单, 找到具体的元素进行修改即可.
public E set(int index, E element) {
checkElementIndex(index);
Nodex = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
5. 总结
基于链表结构的存储方式, 随机访问性能差, 元素的增删性能比较好.
没有扩容操作, 同等元素的情况下, 占用内存比ArrayList多, 因为还要存储节点之间的引用.
可以作为栈或者队列使用.
不要因为知识简单就忽略, 不积跬步无以至千里.
网友评论