# 数组与链表

## 目录
- [数组基础](#数组基础)
- [链表基础](#链表基础)
- [数组与链表对比](#数组与链表对比)
- [常见操作](#常见操作)
- [算法题](#算法题)
- [面试常见问题](#面试常见问题)

---

## 数组基础

### 数组定义

```java
// 数组：连续的内存空间存储相同类型的数据
int[] arr = new int[10];
String[] strs = {"a", "b", "c"};
```

### 数组特点

```java
// 优点：
// 1. 随机访问快：O(1)
// 2. 内存连续，缓存友好

// 缺点：
// 1. 插入删除慢：O(n)
// 2. 大小固定
```

### 数组操作

```java
// 访问
int value = arr[0]; // O(1)

// 插入
// 需要移动元素：O(n)

// 删除
// 需要移动元素：O(n)

// 查找
// 遍历查找：O(n)
// 有序数组二分查找：O(log n)
```

---

## 链表基础

### 链表定义

```java
// 链表：非连续的内存空间，通过指针连接
public class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
    }
}
```

### 链表类型

```java
// 1. 单链表
public class ListNode {
    int val;
    ListNode next;
}

// 2. 双链表
public class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
}

// 3. 循环链表
// 尾节点指向头节点
```

### 链表特点

```java
// 优点：
// 1. 插入删除快：O(1)
// 2. 动态大小

// 缺点：
// 1. 随机访问慢：O(n)
// 2. 内存不连续，缓存不友好
```

---

## 数组与链表对比

### 对比表

| 特性 | 数组 | 链表 |
|------|------|------|
| 内存 | 连续 | 非连续 |
| 访问 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
| 大小 | 固定 | 动态 |

---

## 常见操作

### 数组操作

```java
// 1. 反转数组
public void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// 2. 查找最大值
public int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}
```

### 链表操作

```java
// 1. 反转链表
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 2. 查找中间节点
public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
```

---

## 算法题

### 题1：两数之和

```java
// 给定数组和目标值，找出两数之和等于目标值
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}
```

### 题2：合并两个有序链表

```java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}
```

---

## 面试常见问题

### Q1: 数组和链表的区别？

**答案：**
- **数组**：连续内存，随机访问快，插入删除慢
- **链表**：非连续内存，插入删除快，随机访问慢

### Q2: 什么时候用数组，什么时候用链表？

**答案：**
- **数组**：需要随机访问，数据大小固定
- **链表**：需要频繁插入删除，数据大小动态

### Q3: 如何反转链表？

**答案：**
- 使用三个指针：prev、curr、next
- 遍历链表，逐个反转指针

---

*最后更新：2024年*
