一.ArrayList 的特性1. 访问效率高基于数组实现支持随机访问通过索引 get(int index)时间复杂度为 O(1)这是 ArrayList 对比 LinkedList 最核心的优势LinkedList 随机访问是 O(n)。2. 增删效率分场景尾部增删add (E e)/remove (size-1)效率高时间复杂度 O(1)无扩容时中间 / 头部增删add (int index, E e)/remove (int index)需要移动后续元素时间复杂度 O(n)效率低原因数组元素在内存中是连续存储的中间插入 / 删除会导致后续元素整体移位。3. 线程不安全ArrayList 是非线程安全的集合多线程环境下同时读写会导致数据错乱如 ConcurrentModificationException解决方案使用 Collections.synchronizedList(new ArrayList()) 包装成线程安全版本用 CopyOnWriteArrayList并发包下写操作时复制数组读写分离适合读多写少场景。4. 空值与重复元素允许存储 null 值可以通过 add(null) 添加允许存储重复元素如 add(“a”); add(“a”) 是合法的。5. Cloneable 与浅拷贝1.ArrayList 实现了 Cloneable 接口调用 clone() 方法会返回一个新的 ArrayList 实例但同样是浅拷贝2.新 ArrayList 的数组是新对象但数组中的元素引用类型仅复制引用地址示例如果 ArrayList 中存自定义类对象修改原对象会影响克隆后的 ArrayList 元素。二.链表链表的概念和结构链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。一.链表的种类链表的种类有8种其中的主要分类可以是1.带头和不带头带头节点的实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 头结点不存储实际数据publicLinkedList(){headnewNode(-1);// 初始化头结点}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}// 删除节点publicvoiddelete(intdata){Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}不带头的链表实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 直接指向第一个有效节点publicLinkedList(){headnull;// 初始化为空}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);if(headnull){headnewNode;}else{Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}}// 删除节点publicvoiddelete(intdata){if(headnull)return;if(head.datadata){headhead.next;return;}Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}关键区别初始化带头结点的链表初始化时创建一个虚拟头节点不带头结点的链表直接初始化为null。插入/删除操作带头结点的链表无需单独处理头节点为空的情况不带头结点的链表需要额外判断头节点是否为空。代码复杂度不带头结点的链表在操作头节点时需要更多边界条件判断带头结点的链表逻辑更统一。2.单向和双向// 单向链表节点classSinglyNode{intdata;SinglyNodenext;}// 双向链表节点classDoublyNode{intdata;DoublyNodenext;DoublyNodeprev;}复杂度对比操作单向链表双向链表插入/删除头部O1O1插入/删除尾部OnO(1)插入/删除中间部O(n)O(1)逆向遍历不支持O(n)3.循环和非循环循环的代码实现片段classNode{intdata;Nodenext;Node(intdata){this.datadata;}}非循环的代码实现片段// 创建循环链表NodeheadnewNode(1);head.nextnewNode(2);head.next.nexthead;// 尾节点指向头节点NodeheadnewNode(1);head.nextnewNode(2);// 尾节点默认next为null循环链表的尾节点指向头节点形成一个闭环结构。这种设计允许从任意节点出发遍历整个链表适用于需要循环访问的场景。非循环链表的尾节点指向null表示链表结束。遍历时需从头节点开始到达尾节点时终止结构简单且直观。二.链表中的重要方法方法作用void addFirst(int data)在头部插入数据void addLast(int data)在尾部插入数据void addIndex(int index,int data)在index位置处插入数据boolean contains(int key)判断key元素是否在链表中void remove(int key)移除链表中的第一次出现的key元素void removeAllKey(int key)移除所有的出现的key元素int size()访问数组的长度void display()打印链表的val值void clear()将链表的元素清空
一.ArrayList 的特性1. 访问效率高基于数组实现支持随机访问通过索引 get(int index)时间复杂度为 O(1)这是 ArrayList 对比 LinkedList 最核心的优势LinkedList 随机访问是 O(n)。2. 增删效率分场景尾部增删add (E e)/remove (size-1)效率高时间复杂度 O(1)无扩容时中间 / 头部增删add (int index, E e)/remove (int index)需要移动后续元素时间复杂度 O(n)效率低原因数组元素在内存中是连续存储的中间插入 / 删除会导致后续元素整体移位。3. 线程不安全ArrayList 是非线程安全的集合多线程环境下同时读写会导致数据错乱如 ConcurrentModificationException解决方案使用 Collections.synchronizedList(new ArrayList()) 包装成线程安全版本用 CopyOnWriteArrayList并发包下写操作时复制数组读写分离适合读多写少场景。4. 空值与重复元素允许存储 null 值可以通过 add(null) 添加允许存储重复元素如 add(“a”); add(“a”) 是合法的。5. Cloneable 与浅拷贝1.ArrayList 实现了 Cloneable 接口调用 clone() 方法会返回一个新的 ArrayList 实例但同样是浅拷贝2.新 ArrayList 的数组是新对象但数组中的元素引用类型仅复制引用地址示例如果 ArrayList 中存自定义类对象修改原对象会影响克隆后的 ArrayList 元素。二.链表链表的概念和结构链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。一.链表的种类链表的种类有8种其中的主要分类可以是1.带头和不带头带头节点的实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 头结点不存储实际数据publicLinkedList(){headnewNode(-1);// 初始化头结点}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}// 删除节点publicvoiddelete(intdata){Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}不带头的链表实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 直接指向第一个有效节点publicLinkedList(){headnull;// 初始化为空}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);if(headnull){headnewNode;}else{Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}}// 删除节点publicvoiddelete(intdata){if(headnull)return;if(head.datadata){headhead.next;return;}Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}关键区别初始化带头结点的链表初始化时创建一个虚拟头节点不带头结点的链表直接初始化为null。插入/删除操作带头结点的链表无需单独处理头节点为空的情况不带头结点的链表需要额外判断头节点是否为空。代码复杂度不带头结点的链表在操作头节点时需要更多边界条件判断带头结点的链表逻辑更统一。2.单向和双向// 单向链表节点classSinglyNode{intdata;SinglyNodenext;}// 双向链表节点classDoublyNode{intdata;DoublyNodenext;DoublyNodeprev;}复杂度对比操作单向链表双向链表插入/删除头部O1O1插入/删除尾部OnO(1)插入/删除中间部O(n)O(1)逆向遍历不支持O(n)3.循环和非循环循环的代码实现片段classNode{intdata;Nodenext;Node(intdata){this.datadata;}}非循环的代码实现片段// 创建循环链表NodeheadnewNode(1);head.nextnewNode(2);head.next.nexthead;// 尾节点指向头节点NodeheadnewNode(1);head.nextnewNode(2);// 尾节点默认next为null循环链表的尾节点指向头节点形成一个闭环结构。这种设计允许从任意节点出发遍历整个链表适用于需要循环访问的场景。非循环链表的尾节点指向null表示链表结束。遍历时需从头节点开始到达尾节点时终止结构简单且直观。二.链表中的重要方法方法作用void addFirst(int data)在头部插入数据void addLast(int data)在尾部插入数据void addIndex(int index,int data)在index位置处插入数据boolean contains(int key)判断key元素是否在链表中void remove(int key)移除链表中的第一次出现的key元素void removeAllKey(int key)移除所有的出现的key元素int size()访问数组的长度void display()打印链表的val值void clear()将链表的元素清空
