广州番禺服装网站建设外贸单页网站案例

当前位置： 首页 > news >正文

广州番禺服装网站建设,外贸单页网站案例,湖南省水利水电建设工程学校网站,高端网站建设好的公司引言 链表作为基础数据结构之一#xff0c;在Java集合框架中以LinkedList的形式提供。本文将深入分析Java原生LinkedList的实现机制#xff0c;并介绍我自定义实现的MyLinkedList#xff0c;最后对比两者的设计差异与实现特点。 Java原生LinkedList解析 基本结构 Java的…引言 链表作为基础数据结构之一在Java集合框架中以LinkedList的形式提供。本文将深入分析Java原生LinkedList的实现机制并介绍我自定义实现的MyLinkedList最后对比两者的设计差异与实现特点。 Java原生LinkedList解析 基本结构 Java的LinkedList是基于双向链表实现的列表主要特点包括 双向链表结构每个节点包含前驱和后继指针 高效端点操作头尾插入/删除时间复杂度为O(1) 队列功能实现了Deque接口支持队列操作
核心实现机制 // JDK中的关键字段 transient int size 0; transient NodeE first; // 头节点 transient NodeE last; // 尾节点// 节点定义 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;} } 插入操作示例 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; } 时间复杂度分析 头尾插入/删除O(1) 按索引访问平均O(n/2) 中间插入/删除O(n)需要先定位节点
自定义MyLinkedList实现 package com.zsy;import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Objects;/*** 自定义双向链表实现支持泛型元素存储和基本列表操作** p本实现提供类似Java LinkedList的核心功能包括/p* ul* li基于节点的双向链表结构/li* li支持头部和尾部高效操作/li* li提供元素遍历功能/li* li实现基本的增删改查操作/li* /ul** pb特性说明/b/p* ul* li时间复杂度访问O(n)头尾操作O(1)/li* li空间复杂度O(n)/li* lib非线程安全/b - 多线程环境下需要外部同步/li* /ul** param E 列表元素类型* author zsy* see List/ public class MyLinkedListE implements ListE {/** 当前列表中元素的数量/private int size;/** 链表头节点/private NodeE head;/** 链表尾节点/private NodeE tail;/** 将指定元素追加到列表末尾** param element 要添加的元素/Overridepublic void add(E element) {NodeE newNode new Node(tail, element, null);if (tail ! null) {tail.next newNode;} else {head newNode;}tail newNode;size;}/** 在列表的指定位置插入指定元素** param element 要插入的元素* param index 插入位置的索引* throws IndexOutOfBoundsException 如果索引超出范围/Overridepublic void add(E element, int index) {rangeCheckForAdd(index);if (index size) {add(element);return;}NodeE target getNode(index);NodeE prev target.pre;NodeE newNode new Node(prev, element, target);if (prev null) {head newNode;} else {prev.next newNode;}target.pre newNode;size;}/** 移除并返回列表中指定位置的元素** param index 要移除元素的索引* return 被移除的元素* throws IndexOutOfBoundsException 如果索引超出范围/Overridepublic E remove(int index) {rangeCheck(index);return unlink(getNode(index));}/** 从列表中移除首次出现的指定元素** param element 要移除的元素* return 如果列表包含该元素则返回true/Overridepublic boolean remove(E element) {for (NodeE x head; x ! null; x x.next) {if (Objects.equals(element, x.value)) {unlink(x);return true;}}return false;}/** 替换列表中指定位置的元素** param index 要替换元素的索引* param element 要存储的元素* return 先前在指定位置的元素* throws IndexOutOfBoundsException 如果索引超出范围/Overridepublic E set(int index, E element) {rangeCheck(index);NodeE node getNode(index);E oldVal node.value;node.value element;return oldVal;}/** 返回列表中指定位置的元素** param index 要返回元素的索引* return 列表中指定位置的元素* throws IndexOutOfBoundsException 如果索引超出范围/Overridepublic E get(int index) {rangeCheck(index);return getNode(index).value;}/** 返回列表中的元素数量** return 列表中的元素数量/Overridepublic int size() {return size;}/** 返回此列表中元素的迭代器** return 按适当顺序包含此列表中所有元素的迭代器/Overridepublic IteratorE iterator() {return new LinkedListIterator();}// 私有辅助方法 /** 获取指定索引处的节点/private NodeE getNode(int index) {if (index (size 1)) {NodeE x head;for (int i 0; i index; i)x x.next;return x;} else {NodeE x tail;for (int i size - 1; i index; i–)x x.pre;return x;}}/** 从链表中移除指定节点/private E unlink(NodeE node) {final E element node.value;final NodeE next node.next;final NodeE prev node.pre;if (prev null) {head next;} else {prev.next next;node.pre null;}if (next null) {tail prev;} else {next.pre prev;node.next null;}node.value null;size–;return element;}/** 检查索引是否在有效范围内/private void rangeCheck(int index) {if (index 0 || index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/** 检查添加操作的索引是否在有效范围内/private void rangeCheckForAdd(int index) {if (index 0 || index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}/** 构造索引越界异常信息/private String outOfBoundsMsg(int index) {return Index: index, Size: size;}// 内部类实现 /** 双向链表节点实现/private static class NodeE {/** 前驱节点/NodeE pre;/** 后继节点/NodeE next;/** 节点存储的值/E value;Node(NodeE pre, E value, NodeE next) {this.pre pre;this.value value;this.next next;}}/** 链表迭代器实现/private class LinkedListIterator implements IteratorE {/** 当前迭代节点/private NodeE current head;/** 检查是否还有更多元素可迭代** return 如果迭代有更多元素则返回true/Overridepublic boolean hasNext() {return current ! null;}/** 返回迭代中的下一个元素** return 迭代中的下一个元素* throws NoSuchElementException 如果迭代没有更多元素*/Overridepublic E next() {if (!hasNext())throw new NoSuchElementException();E element current.value;current current.next;return element;}} } 性能考虑 双向链表与数组列表的性能对比 操作ArrayListLinkedList随机访问O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除平均O(1)O(1)中间插入/删除O(n)O(n)内存占用更紧凑每个元素额外占用空间