数组与链表
基础入门
数组
初始化数组
访问元素
插入元素
删除元素
遍历元素
查找元素
扩容元素
链表
初始化数组
插入元素
访问元素
删除元素
遍历元素
查找元素
扩容元素
重点知识
数组和链表的区别
数组优点
数组缺点
链表优点
链表缺点
总结
相关题解
leetcode21.合并两个有序链表
法一：递归
法二：迭代
leetcode206.反转链表
法一：迭代
法二：递归
leetcode86.分隔链表
法一：模拟
leetcode237.删除链表中的节点
法一：和下一个节点交换
基础入门
数组
初始化数组
// 初始化数组
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };访问元素
// 访问元素
int firstElement = nums[0]; // 访问第一个元素，值为 1
int secondElement = nums[1]; // 访问第二个元素，值为 3插入元素
// 插入元素 (假设将元素插入到数组中某个位置)
int[] newArray = new int[nums.length + 1];
int insertIndex = 2; // 想要插入的位置
int newValue = 6; // 插入的值for (int i = 0, j = 0; i < newArray.length; i++) {if (i == insertIndex) {newArray[i] = newValue; // 插入新值} else {newArray[i] = nums[j]; // 复制旧值j++;}
}删除元素
// 删除元素 (假设删除某个位置的元素)
int deleteIndex = 1; // 要删除的元素的索引
int[] arrayAfterDelete = new int[nums.length - 1];for (int i = 0, j = 0; i < nums.length; i++) {if (i != deleteIndex) {arrayAfterDelete[j++] = nums[i]; // 复制旧值}
}遍历元素
// 遍历数组
for (int num : nums) {System.out.println(num); // 打印每个元素
}查找元素
// 查找元素
int target = 3;
boolean found = false;
for (int num : nums) {if (num == target) {found = true; // 找到目标元素break;}
}扩容元素
// 扩容数组 (假设扩容到原来的两倍)
int[] largerArray = new int[nums.length * 2];
for (int i = 0; i < nums.length; i++) {largerArray[i] = nums[i]; // 复制旧值
}链表
初始化数组
// 初始化链表public LinkedList() {head = null;}插入元素
// 插入元素（在链表的头部插入）public void insertAtHead(int value) {ListNode newNode = new ListNode(value);newNode.next = head;head = newNode;}访问元素
// 访问元素public int get(int index) {ListNode current = head;for (int i = 0; i < index; i++) {if (current == null) throw new IndexOutOfBoundsException();current = current.next;}return current.val;}
删除元素
// 删除元素（根据值删除第一个匹配的节点）public void delete(int value) {if (head == null) return;if (head.val == value) {head = head.next; // 删除头节点return;}ListNode current = head;while (current.next != null) {if (current.next.val == value) {current.next = current.next.next; // 删除当前节点的下一个节点return;}current = current.next;}}
遍历元素
// 遍历链表public void traverse() {ListNode current = head;while (current != null) {System.out.print(current.val + " ");current = current.next;}System.out.println();}
查找元素
// 查找元素（返回第一个匹配的节点的索引）public int find(int value) {ListNode current = head;int index = 0;while (current != null) {if (current.val == value) {return index; // 找到目标元素，返回索引}current = current.next;index++;}return -1; // 未找到}扩容元素
// 扩容（链表本身不需要扩容，但可以理解为在链表中插入更多的节点）public void append(int value) {ListNode newNode = new ListNode(value);if (head == null) {head = newNode; // 如果链表为空，则直接插入return;}ListNode current = head;while (current.next != null) {current = current.next; // 找到链表的尾节点}current.next = newNode; // 将新节点添加到链表尾部}重点知识
数组和链表的区别
(1)数组的元素个数是固定的,而组成链表的结点个数可按需要增减:因此定义数组可能会浪费内存空间
(2)数组元素的存诸单元在数组定义时静态分配，链表结点的存储单元在程序执行时动态向系统申请
(3)数组中的元素顺序关系由元素在数组中的索引位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现
(4)对于元素的插入、删除操作非常频繁的场合,用数组不适合，用链表实现适合，原因见如下例子:
在一个数组(列表)中间要插入一个新元素，为完成插入工作，插入处之后的全部元素必须向后移动一个位置空出的位置用于存储新元素。
在一个数组(列表)中删除一个元素，为保持数组中元素相对位置连续递增，删除处之后的元素都得向前移一个位置。如用链表实现插入和删除操作，链表结点的插入或删除操作不再需要移动结点，只需改变相关的结点中的后继结点指针的值即可，与结点的实际存储位置无关。
数组优点
随机存取，查找效率快
数组缺点
插入和删除效率低，要求连续的内存空间，大小固定，不能动态扩展
链表优点
不需要连续空间(逻辑相邻，物理上不一定相邻)
插入删除效率高
内存利用率高，不会浪费内存
链表缺点
不能随机查找，必须从第一个开始遍历
总结
对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表
相关题解
leetcode21.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
法一：递归
// 定义一个用于合并两个有序链表的类
public class Method01 {// 合并两个有序链表的方法，返回合并后的链表public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}if (list1.val > list2.val) {list2.next = mergeTwoLists(list1, list2.next);return list2;} else {list1.next = mergeTwoLists(list1.next, list2);return list1;}}
}法二：迭代
// 用于合并两个已排序链表的类
public class Method02 {// 合并两个已排序链表并返回合并后的链表public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;while (list1 != null && list2 != null) {if (list1.val > list2.val) {prev.next = list2;prev = prev.next;list2 = list2.next;} else {prev.next = list1;prev = prev.next;list1 = list1.next;}}prev.next = list1 == null ? list2 : list1;return prehead.next;}
}
leetcode206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
法一：迭代
// 定义一个名为Method01的类
public class Method01 {// 反转链表的方法，接收链表头结点作为参数并返回反转后的链表头结点public ListNode reverseList(ListNode head) {ListNode prev = null;while (head != null) {ListNode next = head.next;head.next = prev;prev = head;head = next;}return prev;}
}法二：递归
// 方法02类，用于操作链表
public class Method02 {// 反转链表的方法，传入链表头节点public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode next = reverseList(head.next);head.next.next = head;head.next = null;return next;}
}leetcode86.分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
法一：模拟
/*** 方法名称: Method01* 描述: 该类包含一个方法，用于将链表按照给定值x进行分区。*/
public class Method01 {/*** 方法名称: partition* 描述: 将链表中节点的值根据给定值x进行重新排序，使得所有小于x的节点在前，所有大于或等于x的节点在后。* * @param head 链表的头节点* @param x 进行分区的基准值* @return 新的链表头节点*/public ListNode partition(ListNode head, int x) {ListNode leftHead = new ListNode(0);ListNode left = leftHead;ListNode rightHead = new ListNode(0);ListNode right = rightHead;while (head != null) {if (head.val < x) {left.next = head;left = left.next;} else {right.next = head;right = right.next;}head = head.next;}right.next = null;left.next = rightHead.next;return leftHead.next;}
}
leetcode237.删除链表中的节点
法一：和下一个节点交换
// 定义一个名为Method01的类
public class Method01 {// 定义一个删除节点的方法，接收一个ListNode类型的节点作为参数public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}
}
