上海百度seo网站优化,免费法律咨询24小时在线,建设银行重庆市分行官方网站,淘宝的网站建设引言
链表作为基础数据结构之一#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)内存占用更紧凑每个元素额外占用空间
