1.LinkedList底层Node节点的结构是怎样的
LinkedList是Java集合框架中的一个
双向链表
实现类，它实现了
List
和
Deque
接口。LinkedList底层使用Node节点来表示链表的元素。
在Java的LinkedList实现中，Node是一个私有内部类，它包含以下属性：
private static class Node<E> {
E element; // 存储的元素值
Node<E> next; // 后继节点的引用
Node<E> previous; // 前驱节点的引用
Node(Node<E> previous, E element, Node<E> next) {
this.previous = previous;
this.element = element;
this.next = next;
}
}
Node类有三个属性：
-
element
：保存当前节点的元素值。 -
next
：保存下一个节点的引用。如果当前节点是最后一个节点，则next为null。 -
previous
：保存前一个节点的引用。如果当前节点是第一个节点，则previous为null。
通过这样的引用关系，LinkedList的节点形成一个双向链表，可以在常数时间内（O(1)）进行插入和删除操作。
请注意，在Java中的实现中，LinkedList还有一个头节点（
first
）和一个尾节点（
last
），它们是LinkedList的特殊节点，用于标示链表的头部和尾部。它们不包含具体的元素值，只是作为链表的起始和结束标记。当节点Node的first前驱是null表示是头元素，当节点Node的last后继是null表示该节点是尾元素。
LinkedList通过这样的节点结构，实现了双向链表的功能，支持在头部、尾部和任意位置插入和删除节点，为LinkedList提供了灵活的元素操作能力。需要注意的是，LinkedList相对于ArrayList的额外空间开销要更大。
LinkedList不需要像ArrayList一样进行扩容操作，因为LinkedList的底层数据结构是双向链表，它是动态的，没有固定的容量限制。
在LinkedList中，添加和删除元素时，并不会直接涉及容量的调整。因为在双向链表中，每个节点都包含了对前一个节点和后一个节点的引用，通过修改节点间的引用关系，可以方便地插入和删除节点，而不需要进行数组元素的移动和容量的调整。尽管LinkedList不需要进行扩容操作，但在插入或删除大量元素时，可能会导致链表的遍历变得较慢，因为每次操作都需要遍历链表来定位插入或删除的位置。
2.LinkedList如何查找指定下标元素的
在LinkedList中，查找指定下标的元素通常需要遍历链表来找到对应的节点。
-
首先，可以根据下标值的范围判断查找的方向。如果下标值在链表长度的一半之前，从头节点开始往后遍历；如果下标值在链表长度的一半之后，从尾节点开始往前遍历。
-
接下来，根据查找方向选择遍历的起始位置。若从头节点开始遍历，则先获取头节点的引用；若从尾节点开始遍历，则先获取尾节点的引用。
-
遍历链表，根据所选择的查找方向，依次访问节点的后继节点或前驱节点，直到找到目标节点。
-
若链表为空或下标越界，则返回null或抛出异常。
下面是一个示例代码，展示如何在LinkedList中查找指定下标的元素：
public E get(int index) {
// 链表为空或下标越界
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 根据下标值的范围选择查找方向
Node<E> current;
if (index < size / 2) {
// 从头节点开始往后遍历
current = first;
for (int i = 0; i < index; i++) {
current = current.next;
}
} else {
// 从尾节点开始往前遍历
current = last;
for (int i = size - 1; i > index; i--) {
current = current.previous;
}
}
return current.element;
}
需要注意的是，由于LinkedList是基于链表结构的，查找操作的时间复杂度通常是O(n)，其中n是链表的长度。因此，相对于ArrayList来说，在LinkedList中进行随机访问的效率较低。如果需要频繁进行随机访问操作，建议使用ArrayList。