数据结构（六）

数组Array核心操作与性能优化数组是一种线性表数据结构它使用连续的内存空间来存储相同类型的数据。数组的核心优势在于支持随机访问通过下标直接访问元素时间复杂度为O(1)但插入和删除操作效率较低尤其是在数组中间或头部操作时。基础增删改查的实现添加与删除逻辑添加操作的本质是将目标位置及后续的所有元素整体后移为新元素腾出空间然后在指定位置插入新元素。操作逻辑判断插入位置的合法性如是否越界。从插入位置开始将每个元素向后移动一位需从后往前遍历避免数据覆盖。在插入位置放入新元素。时间复杂度O(n)需要移动n个元素n为数组长度。代码示例Javapublic class ArrayOperations { // 添加元素到数组指定位置 public int[] addElement(int[] arr, int index, int value) { // 检查数组是否已满此处简化处理假设传入的是可扩展的数组实际开发中可使用动态数组 if (arr.length 0) { return new int[]{value}; } // 创建新数组长度1 int[] newArr new int[arr.length 1]; // 复制插入位置之前的元素 System.arraycopy(arr, 0, newArr, 0, index); // 放入新元素 newArr[index] value; // 复制插入位置之后的元素 System.arraycopy(arr, index, newArr, index 1, arr.length - index); return newArr; } public static void main(String[] args) { ArrayOperations op new ArrayOperations(); int[] arr {1, 2, 3, 4, 5}; int[] newArr op.addElement(arr, 2, 10); // 在索引2位置插入10 System.out.println(Arrays.toString(newArr)); // 输出[1, 2, 10, 3, 4, 5] } }删除操作的本质是通过数据覆盖实现核心是避免频繁移动数据可通过双指针快慢指针实现原地删除提升效率。传统删除问题直接删除指定位置元素后需要将后续元素前移仍会导致O(n)的移动开销。双指针优化使用快指针fast遍历数组慢指针slow记录有效元素的位置。快指针跳过需要删除的元素慢指针实时更新有效元素的位置最终将慢指针长度作为新数组长度实现原地删除。代码示例双指针删除指定值的元素public class ArrayDeleteWithTwoPointers { // 原地删除数组中值为target的元素返回删除后数组的长度 public int removeElement(int[] nums, int target) { int slow 0; // 慢指针指向下一个有效元素的位置 for (int fast 0; fast nums.length; fast) { // 快指针遍历数组 // 如果快指针指向的元素不是目标值将其赋值给慢指针位置 if (nums[fast] ! target) { nums[slow] nums[fast]; slow; } } return slow; // 慢指针的值即为删除后的有效长度 } public static void main(String[] args) { ArrayDeleteWithTwoPointers op new ArrayDeleteWithTwoPointers(); int[] nums {3, 2, 2, 3, 4}; int newLength op.removeElement(nums, 3); // 删除所有值为3的元素 System.out.println(删除后数组长度 newLength); // 输出3 // 打印有效元素长度为newLength for (int i 0; i newLength; i) { System.out.print(nums[i] ); // 输出2 2 4 } } }核心要点双指针删除的本质是用慢指针压缩有效数据范围避免了后续元素的批量移动同时不依赖额外空间是数组删除操作的高效优化方案。查找与修改查找操作无序数组的查找只能通过遍历实现逐个比对元素直到找到目标值或遍历完成。时间复杂度O(n)最坏情况下需要遍历所有元素。实现逻辑遍历数组判断当前元素是否为目标值找到则返回下标否则继续遍历遍历完未找到返回-1。代码示例public class ArrayFind { // 在无序数组中查找目标值的下标不存在则返回-1 public int findIndex(int[] arr, int target) { for (int i 0; i arr.length; i) { if (arr[i] target) { return i; } } return -1; } public static void main(String[] args) { ArrayFind op new ArrayFind(); int[] arr {5, 3, 8, 1, 9}; int index op.findIndex(arr, 1); // 查找值为1的元素 System.out.println(元素1的下标 index); // 输出3 } }修改操作数组支持随机访问可直接通过下标定位元素并覆盖时间复杂度为O(1)若需通过条件定位修改则需遍历时间复杂度为O(n)。直接下标修改arr[index] newValue直接覆盖目标位置元素。条件遍历修改遍历数组找到满足条件的元素进行修改。代码示例public class ArrayModify { // 通过下标直接修改元素 public void modifyByIndex(int[] arr, int index, int newValue) { if (index 0 index arr.length) { arr[index] newValue; } } // 修改所有值为target的元素为newValue public void modifyByCondition(int[] arr, int target, int newValue) { for (int i 0; i arr.length; i) { if (arr[i] target) { arr[i] newValue; } } } public static void main(String[] args) { ArrayModify op new ArrayModify(); int[] arr {2, 5, 2, 7, 3}; op.modifyByIndex(arr, 1, 10); // 修改索引1的元素为10 op.modifyByCondition(arr, 2, 20); // 将所有值为2的元素修改为20 System.out.println(Arrays.toString(arr)); // 输出[20, 10, 20, 7, 3] } }有序数组的算法优化当数组是有序的如升序、降序我们可以利用其有序性对核心操作进行算法优化显著降低时间复杂度其中最核心的优化是二分查找法以及基于有序性的高效插入策略。二分查找法Binary Search核心原理利用数组的有序性每次通过中间元素将查找区间缩小一半快速定位目标元素将查找时间复杂度从O(n)降至O(log n)是有序数组查找的最优算法。关键要素三个核心指针left左边界、right右边界、mid中间位置mid left (right - left) / 2避免整数溢出。循环终止条件left right确保区间内存在元素时才进行查找。指针移动规则根据中间元素与目标值的比较结果缩小查找区间target nums[mid]则right mid - 1target nums[mid]则left mid 1避免死循环和数据遗漏。插入与遍历操作尾插法追加到链表末尾尾插法将新节点添加到链表末尾需先遍历到最后一个节点再修改其next指针指向新节点。// 尾插法示例 public ListNode appendNode(ListNode head, int value) { ListNode newNode new ListNode(value); if (head null) { return newNode; // 若链表为空新节点即为头节点 } ListNode current head; while (current.next ! null) { current current.next; // 遍历到最后一个节点 } current.next newNode; // 将新节点链接到末尾 return head; }头插法插入到链表头部头插法将新节点插入到链表头部新节点的next指向原头节点并更新头节点引用。// 头插法示例 public ListNode prependNode(ListNode head, int value) { ListNode newNode new ListNode(value); newNode.next head; // 新节点指向原头节点 return newNode; // 返回新头节点 }任意位置插入在指定位置插入新节点需先定位插入位置的前驱节点再调整指针指向。// 在指定位置插入节点 public ListNode insertAtPosition(ListNode head, int value, int position) { if (position 0) { return prependNode(head, value); // 位置≤0视为头插 } ListNode newNode new ListNode(value); ListNode current head; for (int i 0; i position - 1 current ! null; i) { current current.next; // 移动到插入位置的前驱节点 } if (current null) { return appendNode(head, value); // 位置超范围则尾插 } newNode.next current.next; current.next newNode; return head; }遍历操作遍历链表时从头节点开始依次访问每个节点的值直到遇到null。// 遍历链表并打印节点值 public void traverseList(ListNode head) { ListNode current head; while (current ! null) { System.out.print(current.value - ); current current.next; } System.out.println(null); }删除操作删除节点需定位目标节点的前驱节点修改其next指针跳过目标节点。// 删除指定值的节点首次出现 public ListNode deleteNode(ListNode head, int value) { if (head null) return null; if (head.value value) { return head.next; // 删除头节点 } ListNode current head; while (current.next ! null current.next.value ! value) { current current.next; // 定位到目标节点的前驱节点 } if (current.next ! null) { current.next current.next.next; // 跳过目标节点 } return head; }双向链表操作示例双向链表的插入和删除需同时维护prev和next指针。// 双向链表节点插入在指定节点后插入 public void insertAfter(DoubleListNode node, int value) { DoubleListNode newNode new DoubleListNode(value); newNode.next node.next; newNode.prev node; if (node.next ! null) { node.next.prev newNode; // 更新后继节点的prev指针 } node.next newNode; } // 双向链表节点删除 public void deleteNode(DoubleListNode node) { if (node.prev ! null) { node.prev.next node.next; } if (node.next ! null) { node.next.prev node.prev; } }尾插法与头插法尾插法将新节点插入到链表的末尾保证链表元素的插入顺序与原始顺序一致常用于按顺序构建链表。操作逻辑找到链表的尾节点遍历至node.next null的节点将尾节点的next指向新节点。如果链表为空头节点直接指向新节点。代码示例尾插法public class LinkedListTailInsert { public ListNode tailInsert(ListNode head, int value) { ListNode newNode new ListNode(value); if (head null) { return newNode; } ListNode tail head; while (tail.next ! null) { tail tail.next; } tail.next newNode; return head; } public static void main(String[] args) { LinkedListTailInsert op new LinkedListTailInsert(); ListNode head null; head op.tailInsert(head, 1); head op.tailInsert(head, 2); head op.tailInsert(head, 3); printList(head); // 输出1 2 3 } public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); } }头插法将新节点插入到链表的头部新节点的next指向原头节点同时更新头节点指向新节点常用于实现链表倒序。操作逻辑创建新节点新节点的next指向当前头节点更新头节点为新节点。代码示例头插法public class LinkedListHeadInsert { public ListNode headInsert(ListNode head, int value) { ListNode newNode new ListNode(value); newNode.next head; return newNode; } public static void main(String[] args) { LinkedListHeadInsert op new LinkedListHeadInsert(); ListNode head null; head op.headInsert(head, 1); head op.headInsert(head, 2); head op.headInsert(head, 3); printList(head); // 输出3 2 1 } public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); } }任意位置插入在链表的指定位置插入新节点核心是先找到插入位置的前驱节点Pre再通过指针修改实现插入。操作逻辑定位插入位置的前驱节点pre创建新节点新节点的next指向pre.next修改pre.next指向新节点。边界情况插入位置为0头部等同于头插法插入位置为链表末尾等同于尾插法。代码示例在指定索引位置插入节点public class LinkedListInsertAtIndex { public ListNode insertAtIndex(ListNode head, int index, int value) { ListNode newNode new ListNode(value); if (index 0) { newNode.next head; return newNode; } ListNode pre head; int currentIndex 0; while (pre ! null currentIndex index - 1) { pre pre.next; currentIndex; } if (pre null) { ListNode tail head; while (tail.next ! null) { tail tail.next; } tail.next newNode; return head; } newNode.next pre.next; pre.next newNode; return head; } public static void main(String[] args) { LinkedListInsertAtIndex op new LinkedListInsertAtIndex(); ListNode head new ListNode(1); head.next new ListNode(2); head.next.next new ListNode(3); head op.insertAtIndex(head, 1, 5); printList(head); // 输出1 5 2 3 head op.insertAtIndex(head, 5, 10); printList(head); // 输出1 5 2 3 10 } public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); } }遍历与打印链表的遍历是通过游标Cursor从头节点开始依次访问每个节点直到节点为null。代码示例遍历与打印链表public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); }遍历与打印链表链表的遍历是通过游标Cursor从头节点开始依次访问每个节点直到节点为null。遍历是所有链表操作的基础打印链表则是遍历的直接应用可通过循环拼接或重写toString方法实现。代码示例链表遍历与打印的多种方式public class LinkedListTraverse { // 方式1普通循环遍历打印 public static void printListByLoop(ListNode head) { ListNode cur head; if (cur null) { System.out.println(链表为空); return; } StringBuilder sb new StringBuilder(); while (cur ! null) { sb.append(cur.value); if (cur.next ! null) { sb.append( - ); } cur cur.next; } System.out.println(链表内容 sb.toString()); } // 方式2递归遍历打印 public static void printListByRecursion(ListNode head) { if (head null) { System.out.println(); return; } System.out.print(head.value); if (head.next ! null) { System.out.print( - ); } printListByRecursion(head.next); } // 方式3重写节点的toString递归构建链表字符串 public static String listToString(ListNode head) { if (head null) { return ; } return head.toString() (head.next ! null ? - listToString(head.next) : ); } public static void main(String[] args) { // 构建链表1 - 2 - 3 - 4 ListNode head new ListNode(1); head.next new ListNode(2); head.next.next new ListNode(3); head.next.next.next new ListNode(4); printListByLoop(head); // 输出链表内容1 - 2 - 3 - 4 printListByRecursion(head); // 输出1 - 2 - 3 - 4 System.out.println(listToString(head)); // 输出1 - 2 - 3 - 4 } }遍历的核心意义遍历是链表查找、统计、修改等操作的基础无论是插入、删除还是后续的快慢指针问题都依赖对链表的熟练遍历确保指针移动的准确性。链表删除操作与面试高频考点快慢指针链表的删除操作需要注意指针的处理避免内存泄漏而快慢指针是链表面试的核心考点能解决一系列经典问题包括寻找中间节点、判断环形链表、寻找倒数第K个节点等。删除操作的分类处理链表删除的核心是修改前驱节点的指针跳过被删除的节点需根据删除位置的不同进行分类处理同时可借助虚拟头节点统一逻辑简化代码。指定位置删除删除指定位置的节点需分两种情况处理删除头节点和删除非头节点中间或末尾。删除头节点直接将头节点更新为原头节点的下一个节点head head.next原头节点失去引用会被垃圾回收。删除非头节点需先找到被删除节点的前驱节点pre修改pre.next指向被删除节点的下一个节点pre.next pre.next.next。代码示例删除指定索引的节点索引从0开始public class LinkedListDeleteAtIndex { // 删除链表中指定索引的节点返回删除后的头节点 public ListNode deleteAtIndex(ListNode head, int index) { // 处理空链表 if (head null) { return null; } // 删除头节点索引为0 if (index 0) { return head.next; // 头节点指向下一个节点 } // 寻找前驱节点pre索引为index-1的节点 ListNode pre head; int currentIndex 0; while (pre ! null currentIndex index - 1) { pre pre.next; currentIndex; } // 如果pre为null或pre.next为null说明索引无效直接返回原链表 if (pre null || pre.next null) { return head; } // 删除非头节点pre.next指向pre.next.next pre.next pre.next.next; return head; } public static void main(String[] args) { LinkedListDeleteAtIndex op new LinkedListDeleteAtIndex(); // 构建链表1 - 2 - 3 - 4 ListNode head new ListNode(1); head.next new ListNode(2); head.next.next new ListNode(3); head.next.next.next new ListNode(4); // 删除索引1的节点值为2预期链表1 - 3 - 4 head op.deleteAtIndex(head, 1); printList(head); // 输出1 3 4 // 删除索引0的节点头节点值为1预期链表3 - 4 head op.deleteAtIndex(head, 0); printList(head); // 输出3 4 // 删除索引2的节点超出范围无效操作链表不变 head op.deleteAtIndex(head, 2); printList(head); // 输出3 4 } public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); } }虚拟头节点Dummy Node技巧删除操作中最麻烦的是需要特殊处理头节点的情况虚拟头节点的核心作用是统一删除逻辑避免对头节点进行特殊判断让删除操作的处理逻辑完全一致大大简化代码。虚拟头节点的定义创建一个不存储数据的新节点其next指向原链表的头节点新的虚拟头节点作为链表的新入口。删除逻辑无论删除哪个位置的节点都统一找到被删除节点的前驱节点此时前驱节点一定是虚拟头节点或后续节点修改其next指针最后返回虚拟头节点的next作为新头节点。代码示例使用虚拟头节点删除指定值的节点public class LinkedListDeleteWithDummyNode { // 删除链表中所有值为target的节点使用虚拟头节点统一逻辑 public ListNode deleteElement(ListNode head, int target) { // 创建虚拟头节点next指向原头节点 ListNode dummy new ListNode(-1); // -1为虚拟值不存储实际数据 dummy.next head; // 前驱节点pre初始为虚拟头节点 ListNode pre dummy; // 遍历链表找到需要删除的节点 while (pre.next ! null) { if (pre.next.value target) { // 删除pre.next指向的节点 pre.next pre.next.next; } else { // 仅当不删除时pre才后移 pre pre.next; } } // 返回虚拟头节点的下一个节点作为新头节点 return dummy.next; } public static void main(String[] args) { LinkedListDeleteWithDummyNode op new LinkedListDeleteWithDummyNode(); // 构建链表2 - 1 - 2 - 3 - 2 ListNode head new ListNode(2); head.next new ListNode(1); head.next.next new ListNode(2); head.next.next.next new ListNode(3); head.next.next.next.next new ListNode(2); // 删除所有值为2的节点预期链表1 - 3 ListNode newHead op.deleteElement(head, 2); printList(newHead); // 输出1 3 // 测试删除头节点的场景链表1 - 2 - 3删除1预期2 - 3 ListNode head2 new ListNode(1); head2.next new ListNode(2); head2.next.next new ListNode(3); ListNode newHead2 op.deleteElement(head2, 1); printList(newHead2); // 输出2 3 } public static void printList(ListNode head) { ListNode cur head; while (cur ! null) { System.out.print(cur.value ); cur cur.next; } System.out.println(); } }核心优势虚拟头节点让删除操作的逻辑完全统一不需要判断是否删除头节点代码更简洁且降低了边界条件出错的概率是面试中链表删除问题的常用技巧。面试高频考点快慢指针快慢指针是链表面试的杀手锏通过两个移动速度不同的指针能在一次遍历中解决多个经典问题包括寻找中间节点、判断环形链表、寻找倒数第K个节点等是面试中的必考知识点。快慢指针的核心思想是快指针移动速度是慢指针的两倍通过两者的速度差来控制遍历节奏解决特定问题。寻找中间节点利用快慢指针的速度差当快指针遍历到链表末尾时慢指针刚好指向链表的中间节点适用于链表长度为奇数和偶数的情况。核心逻辑初始化快指针fast和慢指针slow均指向头节点。 移动规则快指针每次移动2步fast fast.next.next慢指针每次移动1步slow slow.next。 终止条件当快指针无法移动2步时fast null或fast.next null慢指针指向的节点即为中间节点。 奇偶处理链表长度为奇数中间节点唯一慢指针指向正中间节点。链表长度为偶数中间节点有两个慢指针指向后一个中间节点若需指向前一个可调整移动逻辑。代码示例寻找链表中间节点public class FindMiddleNode { // 使用快慢指针寻找链表中间节点 public ListNode findMiddle(ListNode head) { if (head null) { return null; } ListNode slow head; ListNode fast head; // 快指针每次走2步慢指针每次走1步 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 当快指针无法再走2步时慢指针即为中间节点 return slow; } public static void main(String[] args) { FindMiddleNode op new FindMiddleNode(); // 测试1奇数长度链表1 - 2 - 3 - 4 - 5中间节点为3 ListNode head1 new ListNode(1); head1.next new ListNode(2); head1.next.next new ListNode(3); head1.next.next.next new ListNode(4); head1.next.next.next.next new ListNode(5); ListNode middle1 op.findMiddle(head1); System.out.println(奇数长度链表中间节点 middle1.value); // 输出3 // 测试2偶数长度链表1 - 2 - 3 - 4中间节点为3后一个 ListNode head2 new ListNode(1); head2.next new ListNode(2); head2.next.next new ListNode(3); head2.next.next.next new ListNode(4); ListNode middle2 op.findMiddle(head2); System.out.println(偶数长度链表中间节点 middle2.value); // 输出3 } }判断环形链表环形链表是指链表的最后一个节点的next指向链表中的某个节点形成环形。判断环形链表的核心是快慢指针是否相遇如果相遇则说明有环否则无环。核心逻辑初始化快指针fast和慢指针slow均指向头节点。 移动规则快指针每次移动2步慢指针每次移动1步与寻找中间节点一致。 终止条件若快指针遇到nullfast null或fast.next null说明链表无环返回false。若快指针追上慢指针fast slow说明链表有环返回true。为什么快慢指针一定能追上在有环的情况下快指针比慢指针速度快两者的距离每次缩小1步最终会在环内相遇。代码示例判断链表是否有环public class HasCycle { // 判断链表是否有环有环返回true无环返回false public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; // 空链表或只有一个节点肯定无环 } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; // 快慢指针相遇说明有环 if (fast slow) { return true; } } // 快指针走到null说明无环 return false; } public static void main(String[] args) { HasCycle op new HasCycle(); // 测试1无环链表1 - 2 - 3 - 4 ListNode head1 new ListNode(1); head1.next new ListNode(2); head1.next.next new ListNode(3); head1.next.next.next new ListNode(4); System.out.println(无环链表判断结果 op.hasCycle(head1)); // 输出false // 测试2有环链表1 - 2 - 3 - 4 - 24指向2形成环 ListNode head2 new ListNode(1); ListNode node2 new ListNode(2); ListNode node3 new ListNode(3); ListNode node4 new ListNode(4); head2.next node2; node2.next node3; node3.next node4; node4.next node2; // 构造环 System.out.println(有环链表判断结果 op.hasCycle(head2)); // 输出true } }寻找倒数第K个节点寻找链表倒数第K个节点通过快慢指针可以高效解决核心是让快指针先走K步再让快慢指针同步前进当快指针到达末尾时慢指针指向的节点即为倒数第K个节点。核心逻辑初始化快指针fast和慢指针slow均指向头节点。快指针先走K步循环K次让fast fast.next此时快慢指针的距离为K个节点。同步前进如果快指针还能继续移动fast ! null则快慢指针同时后移fast fast.nextslow slow.next。终止条件当快指针到达null时慢指针指向的节点即为倒数第K个节点。边界处理若K大于链表长度返回null若链表为空返回null。代码示例寻找链表倒数第K个节点public class FindKthFromEnd { // 寻找链表倒数第K个节点返回该节点不存在返回null public ListNode findKthFromEnd(ListNode head, int k) { if (head null || k 0) { return null; } ListNode fast head; ListNode slow head; // 快指针先走k步 for (int i 0; i k; i) { if (fast null) { return null; // k大于链表长度返回null } fast fast.next; } // 快慢指针同步前进直到快指针为null while (fast ! null) { fast fast.next; slow slow.next; } // 此时slow指向倒数第k个节点 return slow; } public static void main(String[] args) { FindKthFromEnd op new FindKthFromEnd(); // 构建链表1 - 2 - 3 - 4 - 5 ListNode head new ListNode(1); head.next new ListNode(2); head.next.next new ListNode(3); head.next.next.next new ListNode(4); head.next.next.next.next new ListNode(5); // 寻找倒数第2个节点预期为4 ListNode result1 op.findKthFromEnd(head, 2); System.out.println(倒数第2个节点的值 result1.value); // 输出4 // 寻找倒数第5个节点预期为1 ListNode result2 op.findKthFromEnd(head, 5); System.out.println(倒数第5个节点的值 result2.value); // 输出1 // k6大于链表长度返回null ListNode result3 op.findKthFromEnd(head, 6); System.out.println(k6的结果 result3); // 输出null } }核心优势该方法仅需一次遍历时间复杂度O(n)空间复杂度O(1)是解决倒数第K个节点问题的最优解也是面试中链表问题的高频考点。