数据结构-数组扩容
一、数组扩容
动态数组：与普通数组不同，动态数组的大小可在运行时调整， ArrayList 类是典型实例。
数组扩容机制：当数组元素数量达到容量极限时，需创建更大数组并复制原元素。新数组长度常为原数组的1.5倍。
数组复制：扩容时，原数组元素要复制到新数组，逐个赋值实现
package com.qcby.array;// 数组扩容
public class ArrayList {private int[] arr = new int[10];// 初始容量为10的数组，用于存储元素private int size = 0;// 记录数组中有效元素的个数// 添加元素到数组末尾public void add(int num) {// 检查是否需要扩容if (size == arr.length) {// 创建一个长度为原数组1.5倍的新数组int[] brr = new int[(int) (arr.length * 1.5)];// 将原数组元素复制到新数组for (int i = 0; i < arr.length; i++) {brr[i] = arr[i];}// 将引用指向新数组arr = brr;}// 将新元素添加到数组末尾arr[size] = num;// 有效元素个数加1size++;}// 将数组转换为字符串表示@Overridepublic String toString() {// 使用StringBuilder构建字符串，提高效率StringBuilder res = new StringBuilder("[");for (int i = 0; i < size; i++) {res.append(arr[i]);// 如果不是最后一个元素，添加逗号和空格if (i != size - 1) {res.append(", ");}}res.append("]");return res.toString();}// 主方法，用于测试public static void main(String[] args) {ArrayList list = new ArrayList();// 添加多个元素到数组list.add(10);list.add(1);list.add(20);list.add(8);list.add(9);list.add(5);list.add(2);list.add(11);list.add(13);list.add(18);list.add(21);list.add(22);list.add(3);list.add(5);list.add(7);// 打印数组内容System.out.println(list);}// 在指定位置插入元素public void add(int position, int num) {// 检查插入位置是否合法if (position < 0 || position > size) {System.out.println("插入位置不合理");return;}// 检查是否需要扩容if (size == arr.length) {// 创建一个长度为原数组1.5倍的新数组int[] brr = new int[(int) (arr.length * 1.5)];// 将原数组元素复制到新数组for (int i = 0; i < arr.length; i++) {brr[i] = arr[i];}// 将引用指向新数组arr = brr;}// 将插入位置及其之后的元素向后移动for (int i = size - 1; i >= position; i--) {arr[i + 1] = arr[i];}// 将新元素插入到指定位置arr[position] = num;// 有效元素个数加1size++;}// 删除数组中的某个元素public void delete(int num) {// 遍历数组，从后向前查找要删除的元素for (int i = size - 1; i >= 0; i--) {if (arr[i] == num) {// 将删除位置之后的元素向前移动for (int j = i + 1; j < size; j++) {arr[j - 1] = arr[j];}// 有效元素个数减1size--;}}}// 获取数组中有效元素的个数public int size() {return size;}// 查找元素在数组中的位置public int search(int num) {// 遍历数组，查找指定元素for (int i = 0; i < size; i++) {if (arr[i] == num) {return i; // 找到元素，返回其索引}}return -1; // 未找到元素，返回-1}
}
二、二分查找法
二分查找法对有序数组适用。它重复将数组中点与目标值比对，依大小关系缩小搜索区间，直至找到目标或确定查找失败。
时间复杂度为 O(log n)
适用场景：适用于查找有序数组或列表中的元素，可扩展到变体问题，如查找第一个大于等于目标值的元素等。
实现步骤：初始化左右指针，计算中间位置并与目标值比较，调整搜索范围，重复直至找到目标或搜索范围为空。
package com.qcby.array;
//二分查找法
public class BinarySearch {public static void main(String[] args) {int[] arr = {12, 37, 49, 71, 85, 88, 93, 100, 456};System.out.println(binarysearch(88, arr));}public static int binarysearch(int num, int[] arr) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (left + right) / 2;if (num == arr[mid]) {return mid;} else if (num > arr[mid]) {left = mid + 1;} else {right = mid - 1;}}return -1;}}三、链表插入方法
1.头插法
头插法是在链表的头部插入一个新节点。
过程：
创建一个新节点。
如果链表为空，新节点成为头节点。
如果链表不为空，新节点的 next 指针指向当前头节点，然后将头指针更新为新节点。
// 头插法public void insertHead(int num) {Node node = new Node(num); // 创建一个新节点if (head == null) { // 如果链表为空head = node; // 新节点成为头节点return;}node.next = head; // 新节点的 next 指向当前头节点head = node; // 更新头指针为新节点}
2.尾插法
在链表的尾部插入一个新节点。
过程：
创建一个新节点
如果链表为空，新节点成为头节点
如果链表不为空，找到当前链表的最后一个节点，将该节点的 next 指针指向新节点
// 尾插法public void insert(int num) {Node node = new Node(num); // 创建一个新节点if (head == null) { // 如果链表为空head = node; // 新节点成为头节点return;}Node index = head; // 从头节点开始遍历while (index.next != null) { // 找到最后一个节点index = index.next;}index.next = node; // 将最后一个节点的 next 指向新节点}3.获取链表长度和任意节点
length 方法：计算链表中有效节点的数量。
实现：初始化计数器 count 为 0，然后遍历链表，每访问一个节点就将计数器加 1，直到遍历完整个链表。
返回值：返回计数器的值，即链表的长度。
search 方法：在链表中查找具有特定值的节点。
实现：从头节点开始遍历链表，检查每个节点的值是否等于目标值。如果找到匹配的节点，则返回该节点；如果遍历完整个链表都没有找到，则返回 null 。
返回值：如果找到匹配的节点，则返回该节点；否则返回 null 。
// 链表的长度
public int length() {int count = 0; // 初始化计数器，用于记录节点数量Node index = head; // 从头节点开始遍历while (index != null) { // 当前节点不为空时继续循环count++; // 计数器加一，表示找到一个节点index = index.next; // 移动到下一个节点}return count; // 返回计数器的值，即链表长度
}// 查找
public Node search(int num) {Node index = head; // 从头节点开始查找while (index != null) { // 当前节点不为空时继续循环if (index.value == num) { // 如果当前节点的值等于要查找的值return index; // 返回当前节点}index = index.next; // 移动到下一个节点}return null; // 如果遍历完整个链表仍未找到，返回null
}
4.在任意位置插入
// 任意位置插入
public void insertAtPosition(int num, int position) {// 检查插入位置是否合理，即不小于0或大于链表长度if (position < 0 || position > length()) {System.out.println("插入位置不合理");return;}// 如果位置为0，即在链表头部插入if (position == 0) {insertHead(num);} else if (position == length()) {// 如果位置等于链表长度，即在链表尾部插入insert(num);} else {// 在链表的中间位置插入新节点Node node = new Node(num);Node index = head;Node pre = null;int count = 0;// 遍历链表找到插入位置的前一个节点while (index != null) {if (count == position) {// 找到插入位置，执行插入操作pre.next = node;node.next = index;return;}pre = index;index = index.next;count++;}// 如果遍历完成后仍未找到插入，说明position超出链表长度，将新节点添加到链表尾部pre.next = node;node.next = index;}
}
四、总体
node类初始化一个节点，后续才有头插尾插