数据结构进阶：链表原理与 Java 实现

接下来定义 MySingleList 类来实现这些方法。这里我们采用'头结点直接指向第一个数据节点'的方式。

public class MySingleList implements IList {
    // 定义单链表节点
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    // 定义头结点
    public ListNode head;

    // 创建单链表
    @Override
    public void create() {
        ListNode listNode1 = new ListNode(11);
        ListNode listNode5 = new ListNode(22);
        ListNode listNode4 = new ListNode(33);
        ListNode listNode3 = new ListNode(44);
        ListNode listNode2 = new ListNode(55);
        
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        
        this.head = listNode1; // 将第一个节点定义为头节点
    }

    // 遍历单链表
    @Override
    public void display() {
        ListNode cur = head; // 从 head 开始遍历
        while (cur != null) {
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
    }

核心操作解析

头插法 时间复杂度为 O(1)。需要注意指针的指向顺序，先让新节点的 next 指向当前头节点，再更新头节点。

@Override
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
}

尾插法 时间复杂度为 O(n)，因为需要从头遍历找到最后一个节点。

@Override
public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (this.head == null) {
        this.head = node;
    } else {
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

任意位置插入 在指定索引 index 处插入，需要考虑边界情况：索引小于 0 抛出异常，等于 0 调用头插法，等于 size 调用尾插法。中间位置则需要找到前驱节点。

@Override
public void addIndex(int index, int data) {
    if (index < 0 || index > size()) {
        throw new IllegalArgumentException("插入元素下标异常" + data);
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    
    ListNode prev = searchPrev(index - 1); // 找到前驱节点
    ListNode node = new ListNode(data);
    node.next = prev.next;
    prev.next = node;
}

// 辅助方法：查找指定索引的前一个节点
private ListNode searchPrev(int index) {
    ListNode cur = this.head;
    int count = 0;
    while (count != index) {
        cur = cur.next;
        count++;
    }
    return cur;
}

查找与删除 查找时注意返回值的逻辑修正；删除节点时，关键在于修改前驱节点的 next 指针，使其跳过待删除节点。

@Override
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            return true; // 找到则返回 true
        }
        cur = cur.next;
    }
    return false;
}

@Override
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    // 如果头节点就是要删除的节点
    if (this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    
    ListNode prev = searchPrev(key); // 假设 searchPrev 能根据值查找前驱
    if (prev != null && prev.next != null && prev.next.val == key) {
        prev.next = prev.next.next;
    }
}

// 辅助方法：根据值查找前驱节点
private ListNode searchPrev(int key) {
    ListNode cur = this.head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

清空链表 遍历链表，将每个节点的 next 置空，最后将 head 置空。

@Override
public void clear() {
    ListNode cur = this.head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    this.head = null;
}

链表面试题

链表是算法面试中的高频考点，常见的题目包括：

1. 删除链表中等于给定值 val 的所有节点。
2. 反转一个单链表。
3. 给定一个带有头结点的非空单链表，返回链表的中间结点。
4. 输入一个链表，输出该链表中倒数第 k 个结点。
5. 将两个有序链表合并为一个新的有序链表并返回。
6. 以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前。

LinkedList 的使用

什么是 LinkedList

LinkedList 的底层是双向链表结构。由于链表没有将元素存储在连续的空间中，而是存储在单独的节点中并通过引用连接，因此在任意位置插入或删除元素时，不需要搬移元素，效率较高。

在 Java 集合框架中，LinkedList 实现了 List 接口，但并未实现 RandomAccess 接口，这意味着它不支持高效的随机访问。

常用方法

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // 尾插
    list.add(2);
    list.add(3);
    
    // 在起始位置插入
    list.add(0, 0);
    
    // 删除操作
    list.remove();       // 删除第一个元素
    list.removeFirst();  // 显式删除第一个
    list.removeLast();   // 删除最后元素
    list.remove(1);      // 删除指定索引元素
    
    // 查询与定位
    if (!list.contains(1)) {
        list.add(0, 1);
    }
    System.out.println(list.indexOf(1));     // 正向查找
    System.out.println(list.lastIndexOf(1)); // 反向查找
    
    // 修改与截取
    int elem = list.get(0);
    list.set(0, 100);
    List<Integer> copy = list.subList(0, 3);
    
    // 清空
    list.clear();
}

遍历方式

除了增强 for 循环，还可以使用迭代器进行正向或反向遍历。

// 正向遍历
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
    System.out.print(it.next() + " ");
}

// 反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()) {
    System.out.print(rit.previous() + " ");
}

ArrayList 和 LinkedList 的区别

在实际开发中，如果不确定选哪个，通常首选 ArrayList，除非明确知道会有大量的中间插入删除操作。