---

一、第一部分：手写有序动态数组

1 项目结构

com.qcby.数组
├─ ArrayList.java  // 有序动态数组核心类
└─ Test.java       // 测试运行类

2 完整源码

2.1 ArrayList.java

package com.qcby.数组;

import java.util.Arrays;

public class ArrayList {
    // 底层物理数组，固定容量
    int[] arr = new int[10];
    // size：有效元素个数（逻辑长度）
    int size = 0;

    // 无序尾部追加（普通add）
    public void add(int value) {
        // 判断扩容
        if (size == arr.length) {
            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] = value;
        size++;
    }

    // 【重点】有序插入，插入后数组永久升序
    public void insert(int value) {
        // 扩容判断
        if (size == arr.length) {
            int[] brr = new int[(int) (arr.length * 1.5)];
            for (int i = 0; i < arr.length; i++) {
                brr[i] = arr[i];
            }
            arr = brr;
        }

        // 场景1：数组为空
        if (size == 0) {
            arr[size] = value;
            size++;
        }
        // 场景2：比最后一个元素大，直接尾插无需移位
        else if (value > arr[size - 1]) {
            arr[size] = value;
            size++;
        }
        // 场景3：插入数组中间，元素整体右移腾出空位
        else {
            for (int i = 0; i < size; i++) {
                if (arr[i] > value) {
                    // 从后往前移位，防止数据覆盖
                    for (int j = size - 1; j >= i; j--) {
                        arr[j + 1] = arr[j];
                    }
                    arr[i] = value;
                    size++;
                    break;
                }
            }
        }
    }

    // 二分查找（仅有序数组可用，左闭右开 [0,size)）
    public int find(int value) {
        int left = 0;
        int right = size;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] == value) {
                return mid;
            } else if (arr[mid] > value) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return -1; // 不存在返回-1
    }

    // 方式1：倒序遍历，删除单个匹配元素
    public void delete(int value) {
        for (int i = size - 1; i >= 0; i--) {
            if (arr[i] == value) {
                // 后方元素统一左移覆盖
                for (int j = i + 1; j < size; j++) {
                    arr[j - 1] = arr[j];
                }
                size--;
            }
        }
    }

    // 方式2：快慢指针，一次性删除全部相同元素
    public void remove(int value) {
        int slow = 0;
        for (int fast = 0; fast < size; fast++) {
            if (arr[fast] != value) {
                arr[slow++] = arr[fast];
            }
        }
        size = slow;
    }

    // 普通线性查找，有序/无序数组通用
    public int search(int value) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }

    // 格式化输出数组 [1, 5, 10]
    @Override
    public String toString() {
        String str = "[";
        for (int i = 0; i < size; i++) {
            if (i == size - 1) {
                str = str + arr[i];
            } else {
                str = str + arr[i] + ", ";
            }
        }
        str = str + "]";
        return str;
    }
}

2.2 Test.java 测试类

package com.qcby.数组;

public class Test {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.insert(10);
        list.insert(5);
        list.insert(14);
        list.insert(1);
        list.insert(7);
        list.insert(26);
        list.insert(19);
        list.insert(31);
        list.insert(179);
        list.insert(20);
        list.insert(50);
        list.insert(80);
        list.insert(90);

        System.out.println("有序数组：" + list.toString());
        System.out.println("二分查找179下标：" + list.find(179));
    }
}

3 核心方法解析

3.1 有序插入 insert () 三大分支

1. 空数组：直接存入下标 0
2. 大于末尾最大值：尾部追加，无元素移位，性能最优
3. 中间插入：
   • 遍历找到第一个大于目标值的下标 i（插入点）
   • 从size-1倒序右移元素，必须倒序，否则数据被提前覆盖
   • 空位赋值，有效长度 size++

3.2 二分查找 find ()

区间规则：[left, right) 左闭右开，效率 O (logn)，是有序数组独有优势。 普通线性查找 search () O (n)，无序数组只能用这个。

3.3 两种删除对比

• delete(value)：循环匹配删除单个元素，多次匹配会逐个删除
• remove(value)：快慢指针原地过滤，一趟遍历删除所有匹配值，效率更高

3.4 自动扩容机制

底层数组长度固定，容量填满时新建 1.5 倍容量数组，复制旧数据完成扩容。

4 有序数组优缺点

✅ 优点

1. 连续内存，按下标随机访问 O (1)
2. 支持二分查找，海量数据查询速度极快
3. 内存紧凑，CPU 缓存命中率高

❌ 缺点

1. 头部 / 中间插入删除需要批量移位，时间复杂度 O (n)
2. 需要预留扩容空间，存在内存浪费
3. 必须连续大块内存，内存碎片化场景不友好

二、第二部分：手写单向链表

1 项目结构

com.qcby.链表
├─ Node.java     // 链表节点类
├─ LinkList.java // 链表完整实现（头插/尾插/指定位置/删除/查找）
└─ Test.java     // 测试类

2 完整源码

2.1 Node.java 节点实体

package com.qcby.链表;

public class Node {
    int value;    // 存储数据
    Node next;    // 指向下一个节点引用

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node [value=" + value + ", next=" + next + "]";
    }
}

2.2 LinkList.java 完整功能链表

package com.qcby.链表;

public class LinkList {
    // 头节点引用
    public Node head = null;

    // 尾插法
    public void insert(int value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
            return;
        }
        Node index = head;
        while (index.next != null) {
            index = index.next;
        }
        index.next = node;
    }

    // 头插法（效率O(1)）
    public void headInsert(int value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
            return;
        }
        node.next = head;
        head = node;
    }

    // 指定下标位置插入
    public void add(int value, int position) {
        if (position < 0 || position > length()) {
            System.out.println("插入位置非法");
            return;
        }
        // 头部插入
        if (position == 0) {
            headInsert(value);
        }
        // 尾部插入
        else if (position == length()) {
            insert(value);
        }
        // 中间插入
        else {
            Node index = head;
            Node pre = null;
            int count = 0;
            Node node = new Node(value);
            while (index != null) {
                if (count == position) {
                    node.next = index;
                    pre.next = node;
                    return;
                }
                pre = index;
                index = index.next;
                count++;
            }
        }
    }

    // 根据值查找节点
    public Node search(int value) {
        Node index = head;
        while (index != null) {
            if (index.value == value) {
                return index;
            }
            index = index.next;
        }
        return null;
    }

    // 获取链表总长度
    public int length() {
        int len = 0;
        Node index = head;
        while (index != null) {
            len++;
            index = index.next;
        }
        return len;
    }

    // 根据下标删除节点
    public void delete(int position) {
        if (position < 0 || position >= length()) {
            System.out.println("删除位置非法");
            return;
        }
        // 删除头节点
        if (position == 0) {
            head = head.next;
        } else {
            Node index = head;
            Node pre = null;
            int count = 0;
            while (index != null) {
                if (count == position) {
                    pre.next = index.next;
                    return;
                }
                pre = index;
                index = index.next;
                count++;
            }
        }
    }

    // 格式化打印链表
    @Override
    public String toString() {
        String res = "[";
        Node index = head;
        while (index != null) {
            res = res + index.value + " ";
            index = index.next;
        }
        res = res + "]";
        return res;
    }
}

2.3 Test.java 测试类

package com.qcby.链表;

public class Test {
    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.insert(5);
        linkList.insert(7);
        linkList.insert(4);
        linkList.insert(3);
        System.out.println(linkList);

        linkList.headInsert(1);
        linkList.add(9, 2);
        System.out.println("插入后：" + linkList);

        link.delete(3);
        System.out.println("删除下标3：" + linkList);
    }
}

3 链表核心原理解析

1. 节点结构：每个节点包含数据域 + 后继指针，内存不连续
2. 头插 headInsert ()：无需遍历，直接修改头指针，O (1)
3. 尾插 insert ()：必须遍历到最后一个节点，O (n)
4. 指定位置插入 / 删除：需要遍历找到前驱节点，定位过程 O (n)，真正插入仅修改指针 O (1)
5. 查找：只能从头遍历，无二分查找能力，固定 O (n)

4 单向链表优缺点

✅ 优点

1. 内存不要求连续，无扩容、空间浪费问题
2. 已知前驱节点时，插入删除仅修改指针，无数据移位
3. 容量动态增减，不需要提前分配空间

❌ 缺点

1. 不支持随机下标访问，查找、定位必须遍历 O (n)
2. 每个节点额外存储指针，内存开销更大
3. 无法二分查找，海量查询性能极差

三、有序数组 VS 单向链表 全面对比表

表格

操作	有序动态数组（顺序表）	单向链表
随机按下标访问	O(1)	O(n)
根据值查找	二分 O (logn)	遍历 O (n)
头部插入	O (n)（全体移位）	O (1)（头插）
尾部插入	O(1)	O (n)（需遍历尾节点）
中间插入	O (n)（移位）	O (n)（定位）
中间删除	O (n)（移位）	O (n)（定位）
内存占用	仅存储数据，紧凑	数据 + 指针，额外开销
内存要求	需要连续内存块	零散内存即可
典型适用场景	查询多、增删少，需要排序 / 二分	频繁头尾增删，数据规模波动大

PS：面试高频问题

1.给定一个链表不知道长度，只遍历一遍，找到单链表中间节点

// 快慢指针寻找链表中间节点
public Node findMid() {
    // 快慢指针均从头节点出发
    Node fast = head;
    Node slow = head;
    // 循环条件：fast与fast.next都不能为null，防止空指针
    while (fast != null && fast.next != null) {
        // 快指针一次走2步
        fast = fast.next.next;
        // 慢指针一次走1步
        slow = slow.next;
    }
    // 循环结束时，slow停在中间节点
    return slow;
}

2.寻找链表倒数第K个节点

// 截取单链表中后k个节点，返回倒数第k个节点
public Node NthFromEnd(int k) {
    Node fast = head;
    Node slow = head;
    // 快指针先走k步，拉开快慢指针间距k
    for(int i=0;i<k;i++) {
        fast=fast.next;
    }
    // 快慢指针同步向后走，直到fast走到末尾null
    while(fast!=null) {
        fast=fast.next;
        slow=slow.next;
    }
    return slow;
}

3.判断链表有没有环

// 判断链表是否有环
public boolean hasCycle() {
    Node fast = head;
    Node slow = head;
    // 循环条件防止fast.next.next空指针
    while(fast != null && fast.next != null) {
        // 快指针一次走2步
        fast = fast.next.next;
        // 慢指针一次走1步
        slow = slow.next;
        // 两指针相遇，说明存在环
        if(fast == slow) {
            return true;
        }
    }
    // 循环正常走完，无环
    return false;
}