我们咨询一下腾讯混元大模型,什么是“LinkedList”。
以下是混元大模型的回答:
LinkedList 是 Java 集合框架中的一种数据结构,它实现了 List 和 Deque 接口。
LinkedList 是一个双向链表,这意味着每个元素都包含对前一个和后一个元素的引用。
这种数据结构允许在列表的两端进行高效的插入和删除操作。
LinkedList 的主要特点:
LinkedList
的大小可以动态增长或缩小。LinkedList
的开头、结尾或中间插入或删除元素时,不需要移动其他元素,因此这些操作通常比在 ArrayList
中执行得更快。LinkedList
在内存使用上可能比 ArrayList
更有效。ArrayList
相比,LinkedList
的随机访问速度较慢,因为需要从头部或尾部开始遍历链表才能找到特定位置的元素。LinkedList
不是线程安全的。如果多个线程同时修改 LinkedList
,可能会导致数据不一致。在多线程环境中,可以使用 Collections.synchronizedList()
方法将 LinkedList
包装成线程安全的列表,或者使用 CopyOnWriteArrayList
(尽管它更适合读多写少的场景)。public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}
源码分析:
LinkedList
继承了AbstractSequentialListAbstractSequentialList
是 Java 集合框架中的一个抽象类,它实现了 List
接口并提供了一个顺序访问列表元素的迭代器。AbstractSequentialList
为那些希望以顺序方式访问其元素的列表提供了一个通用的基础实现。LinkedList
实现了List接口:具备线性表的操作,如:LinkedList
实现了Deque接口:具备双向链表的操作,如:
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
/** 修改次数 */
protected transient int modCount = 0;
源码分析:
LinkedList
内置了两个指针,包括头结点first和末尾指针lastLinkedList
也设置了size,标识有效元素数量(不包括头结点和末尾指针)LinkedList
设置了modCount,标识修改操作次数,modCount
字段用于跟踪列表的结构修改次数,以确保在迭代过程中发生并发修改时能够快速失败,会直接触发异常ConcurrentModificationException通过阅读源码,LinkedList
有7种添加元素方法,
add(E e)
:在列表的末尾添加一个元素(默认在列表的末尾添加,即尾插法)add(int index, E element)
:在指定位置插入一个元素。addFirst(E e)
:在列表的开头添加一个元素。addLast(E e)
:在列表的末尾添加一个元素(与 add(E e)
相同)。push(E e)
:在列表的开头添加一个元素(与 addFirst(E e)
相同)。addAll
的两个重载方法:则是批量插入元素解析 add(E e)
方法源码public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
源码分析:
源码分析:
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;
// 【1】
final Node<E> next = f.next;
// 【2】
f.item = null;
// 【3】
f.next = null; // help GC
// 【4】
first = next;
// 【5】
if (next == null)
last = null;
else
// 【6】
next.prev = null;
// 【7】
size--;
modCount++;
// 【8】
return element;
}
源码解析:
public E set(int index, E element) {
// 【1】
checkElementIndex(index);
// 【2】
Node<E> x = node(index);
// 【3】
E oldVal = x.item;
// 【4】
x.item = element;
// 【5】
return oldVal;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 【2.1】右移位运算,size/2
if (index < (size >> 1)) {
// 【2.2】
Node<E> x = first;
// 【2.3】从头部进行遍历
for (int i = 0; i < index; i++)
// 【2.4】
x = x.next;
// 【2.5】
return x;
} else {
// 【2.6】从尾部进行遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
// 【2.7】
x = x.prev;
// 【2.8】
return x;
}
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
源码分析:
public E get(int index) {
// 【1】
checkElementIndex(index);
// 【2】
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 【2.1】右移位运算,size/2
if (index < (size >> 1)) {
// 【2.2】
Node<E> x = first;
// 【2.3】从头部进行遍历
for (int i = 0; i < index; i++)
// 【2.4】
x = x.next;
// 【2.5】
return x;
} else {
// 【2.6】从尾部进行遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
// 【2.7】
x = x.prev;
// 【2.8】
return x;
}
}
源码解析:
(会发现,其实获取元素的逻辑,就是修改元素的前置操作)
LinkedList 是一个双向链表,这意味着每个元素都包含对前一个和后一个元素的引用。这种数据结构允许在列表的两端进行高效的插入和删除操作。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。