赤峰建设厅官方网站,建设摩托车官网报价及图片,做网站用的大图,eclipse与jsp网站开发1、背景 我们咨询一下腾讯混元大模型#xff0c;什么是“LinkedList”。 以下是混元大模型的回答#xff1a; LinkedList 是 Java 集合框架中的一种数据结构#xff0c;它实现了 List 和 Deque 接口。LinkedList 是一个双向链表#xff0c;这意味着每个元素都包含对前一个和… 1、背景 我们咨询一下腾讯混元大模型什么是“LinkedList”。 以下是混元大模型的回答 LinkedList 是 Java 集合框架中的一种数据结构它实现了 List 和 Deque 接口。LinkedList 是一个双向链表这意味着每个元素都包含对前一个和后一个元素的引用。
这种数据结构允许在列表的两端进行高效的插入和删除操作。 LinkedList 的主要特点 动态大小与数组不同LinkedList 的大小可以动态增长或缩小。高效的插入和删除在 LinkedList 的开头、结尾或中间插入或删除元素时不需要移动其他元素因此这些操作通常比在 ArrayList 中执行得更快。内存效率由于不需要连续的内存空间来存储元素LinkedList 在内存使用上可能比 ArrayList 更有效。访问速度与 ArrayList 相比LinkedList 的随机访问速度较慢因为需要从头部或尾部开始遍历链表才能找到特定位置的元素。线程不安全LinkedList 不是线程安全的。如果多个线程同时修改 LinkedList可能会导致数据不一致。在多线程环境中可以使用 Collections.synchronizedList() 方法将 LinkedList 包装成线程安全的列表或者使用 CopyOnWriteArrayList尽管它更适合读多写少的场景。 2、源码分析 2.1类定义 public class LinkedListEextends AbstractSequentialListEimplements ListE, DequeE, Cloneable, java.io.Serializable
{} 源码分析 LinkedList 继承了AbstractSequentialList AbstractSequentialList 是 Java 集合框架中的一个抽象类它实现了 List 接口并提供了一个顺序访问列表元素的迭代器。AbstractSequentialList 为那些希望以顺序方式访问其元素的列表提供了一个通用的基础实现。LinkedList 实现了List接口具备线性表的操作如 size、isEmpty、contains、containsAlladd、addAll、removeAll、retainAll、clear、subListLinkedList 实现了Deque接口具备双向链表的操作如 addFirst、removeFirst、pollFirst、getFirst、peekFirstaddLast、removeLast、pollLast、getLast、peekLast 2.2基本属性 transient int size 0;/*** Pointer to first node.*/
transient NodeE first;/*** Pointer to last node.*/
transient NodeE last;/** 修改次数 */
protected transient int modCount 0; 源码分析 LinkedList 内置了两个指针包括头结点first和末尾指针lastLinkedList 也设置了size标识有效元素数量不包括头结点和末尾指针LinkedList设置了modCount标识修改操作次数modCount字段用于跟踪列表的结构修改次数以确保在迭代过程中发生并发修改时能够快速失败会直接触发异常ConcurrentModificationException 2.3 基本操作增删改查 1增加元素 通过阅读源码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 NodeE l last;final NodeE newNode new Node(l, e, null);last newNode;if (l null)first newNode;elsel.next newNode;size;modCount;
}Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;
} 源码分析 linkLast(e)尾插法新建Node节点前继指针指向last当前数据为e后继指针为null容量size1修改次数1 2删除元素 解析remove()方法源码 源码分析 public E remove() {return removeFirst();
}public E removeFirst() {final NodeE f first;if (f null)throw new NoSuchElementException();return unlinkFirst(f);
}private E unlinkFirst(NodeE f) {// assert f first f ! null;final E element f.item;// 【1】final NodeE 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;
} 源码解析 中间变量next局部变量 承载被删节点的next指针下个元素地址设置被删节点的item数值为null设置被删节点的next指针为null设置first指针为next局部变量 (下个元素地址)如果next局部变量为null说明没有元素了顺带设置last为null否则设置next局部变量 的前继指针为null因为此后next局部变量 的元素为头结点了容量-1操作次数1返回被删数据 3修改元素 更新set()方法源码 public E set(int index, E element) {// 【1】checkElementIndex(index);// 【2】NodeE x node(index);// 【3】E oldVal x.item;// 【4】x.item element;// 【5】return oldVal;
}NodeE node(int index) {// assert isElementIndex(index);// 【2.1】右移位运算size/2if (index (size 1)) {// 【2.2】NodeE x first;// 【2.3】从头部进行遍历for (int i 0; i index; i)// 【2.4】x x.next;// 【2.5】return x;} else {// 【2.6】从尾部进行遍历NodeE 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;
} 源码分析 检查元素是否合法不合法抛出异常IndexOutOfBoundsException通过遍历链表得到元素地址 计算要更新的索引下标离first更近还是离last更近离first更近从头部开始遍历for循环遍历得到前一个元素的next指向的元素地址离last更近从尾部开始遍历for循环遍历得到后一个元素的prev指向的元素地址获取更新前数值更新新数值返回更新前数值 4获取元素 获取某个索引下标get()方法源码 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));
}NodeE node(int index) {// assert isElementIndex(index);// 【2.1】右移位运算size/2if (index (size 1)) {// 【2.2】NodeE x first;// 【2.3】从头部进行遍历for (int i 0; i index; i)// 【2.4】x x.next;// 【2.5】return x;} else {// 【2.6】从尾部进行遍历NodeE x last;for (int i size - 1; i index; i--)// 【2.7】x x.prev;// 【2.8】return x;}
} 源码解析 会发现其实获取元素的逻辑就是修改元素的前置操作 检查元素是否合法不合法抛出异常IndexOutOfBoundsException通过遍历链表得到元素地址 计算要更新的索引下标离first更近还是离last更近离first更近从头部开始遍历for循环遍历得到前一个元素的next指向的元素地址离last更近从尾部开始遍历for循环遍历得到后一个元素的prev指向的元素地址 3、总结 LinkedList 是一个双向链表这意味着每个元素都包含对前一个和后一个元素的引用。这种数据结构允许在列表的两端进行高效的插入和删除操作。 3.1 ArrayList和LinkedList比较 ArrayList底层基于动态数组实现LinkedList底层基于链表实现对于随机访问get/set方法ArrayList通过index直接定位到数组对应位置的节点而LinkedList需要从头结点或尾节点开始遍历直到寻找到目标节点因此在效率上ArrayList优于LinkedList对于插入和删除add/remove方法ArrayList需要移动目标节点后面的节点使用System.arraycopy方法移动节点而LinkedList只需修改目标节点前后节点的next或prev属性即可因此在效率上LinkedList优于ArrayList。
