湘潭做网站的公司,上海信息技术做网站,网站开发后端菜鸟教程,wordpress程序员博客节点#xff08;Node#xff09;结构
LinkedList 的核心是一个内部类 Node#xff0c;每个 Node 对象代表链表中的一个元素#xff0c;并且每个节点包含三个部分#xff1a;
元素值 (item)#xff1a;存储实际的数据。前驱节点引用 (prev)#xff1a;指向当前节点前面…节点Node结构
LinkedList 的核心是一个内部类 Node每个 Node 对象代表链表中的一个元素并且每个节点包含三个部分
元素值 (item)存储实际的数据。前驱节点引用 (prev)指向当前节点前面的节点。后继节点引用 (next)指向当前节点后面的节点。 private static class NodeE {E item;NodeE next;NodeE prev;Node(NodeE prev, E element, NodeE next) {this.item element;this.next next;this.prev prev;}}
LinkedList 类维护了两个引用分别是指向链表的头部节点和尾部节点
头节点 (first)指向链表的第一个节点。尾节点 (last)指向链表的最后一个节点。长度size
transient int size 0;
transient NodeE first;
transient NodeE last;
链表的基本操作 插入操作 插入新节点时通常需要更新相邻节点的前后指针以及链表的头尾指针。例如插入到链表尾部的操作addLast()
创建一个新的 Node 实例。将新节点的 prev 指向当前尾部节点。如果链表为空则同时设置 first 和 last 指向新节点否则设置当前尾部节点的 next 指向新节点并更新 last 指向新节点。
源码 public void addLast(E e) {linkLast(e);}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;} 示例
public class LinkedListTest {public static void main(String[] args) {LinkedListString sites new LinkedList();sites.add(Google);sites.addLast(Wiki);System.out.println(sites);}
} 删除操作 找到要删除的节点。更新前驱节点的 next 指针和后继节点的 prev 指针。如果删除的是头部节点更新 first如果是尾部节点更新 last。
部分源码 public boolean remove(Object o) {//处理null值if (o null) {for (NodeE x first; x ! null; x x.next) {if (x.item null) {unlink(x);//删除return true;}}} else {for (NodeE x first; x ! null; x x.next) {if (o.equals(x.item)) {unlink(x);//删除return true;}}}return false;}//删除操作E unlink(NodeE x) {final E element x.item;final NodeE next x.next;final NodeE prev x.prev;if (prev null) {first next;} else {prev.next next;x.prev null;}if (next null) {last prev;} else {next.prev prev;x.next null;}x.item null;size--;modCount;return element;}
查找操作
查找一个节点通常是从头节点开始遍历链表直到找到目标节点或到达尾部节点。
源码
public int indexOf(Object o) {int index 0;for (NodeE x first; x ! null; x x.next) {if (o null ? x.item null : o.equals(x.item))return index;index;}return -1;
}
基于源码他有以下特点 快速插入和删除: 插入和删除操作的时间复杂度通常为 O(1)。插入和删除操作只需要修改相邻节点的引用而不需要移动元素。这一点与 ArrayList 不同ArrayList 在插入或删除时可能需要移动大量元素。 随机访问相对较慢: 随机访问某个位置的元素需要从头或尾开始遍历时间复杂度为 O(n)。这是因为链表不像数组那样连续存储数据无法直接通过索引访问元素。 允许重复元素 允许 null 值 线程不安全: LinkedList 的基本操作如 add, get, set, remove 等不是线程安全的。如果多个线程并发地访问或修改 LinkedList需要外部同步机制。 所有指定位置的操作都是从头开始遍历进行的: 对于基于索引的操作如 get(int index) 或 set(int index, E element)遍历会从头部开始直到到达指定的位置。 有序性:即元素的顺序保持不变除非显式地重新排序或修改链表。 实现多种接口: LinkedList 实现了 List、Deque双端队列、Queue 等接口因此可以作为队列、堆栈或双端队列使用。
什么时候会使用到这些接口
使用 List 接口
如果你需要一个有序的列表那么使用 List 接口。
例如
维护一个动态的历史记录列表例如浏览器的历史记录或者最近打开的文件列表。实现一个灵活的任务列表其中任务可能被添加或移除并且这种操作非常频繁。
使用 Queue 接口
如果你需要一个先进先出的数据结构那么使用 Queue 接口。
例如
消息队列处理来自客户端的消息或事件。任务队列例如用于异步处理的作业队列如批量处理任务、打印队列等。缓存队列例如在内存中缓存最近访问的数据项当队列满时移除最旧的数据项。
使用 Deque 接口
如果你需要一个可以从两端进行操作的数据结构那么使用 Deque 接口。
例如
滑动窗口算法在算法问题中需要维护一个固定长度的滑动窗口例如计算滑动窗口内的最大值或最小值。后进先出LIFO操作虽然 Deque 支持 FIFO 和 LIFO 操作但如果你需要一个简单的栈可以使用 Deque 的相关方法。双端队列队列例如在实现优先级队列时你可以使用双端队列来存储不同优先级的元素。
示例代码
import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;public class LinkedListExample {public static void main(String[] args) {// 使用 LinkedList 作为 QueueQueueString queue new LinkedList();queue.offer(One);queue.offer(Two);System.out.println(Queue: queue);System.out.println(Poll from Queue: queue.poll());// 使用 LinkedList 作为 DequeDequeInteger deque new LinkedList();deque.addFirst(1);deque.addLast(2);System.out.println(Deque: deque);System.out.println(Remove from front of Deque: deque.removeFirst());}
}
