链表增删改查（Java）基础

java数据结构中链表的基本操作方法（增删改查）

public class LinkedList <E>{
    // 头节点，不存储实际数据，仅作为链表的起始点
    private Node<E> head=new Node<>(null);
    // 链表中元素的数量
    private int size;

    public void add(E element, int index) {
        // 检查插入位置是否合法
        if(index<0 || index>size)
            throw new IndexOutOfBoundsException("插入位置非法，0~"+size);
        
        // 从头节点开始遍历，找到插入位置的前一个节点
        Node<E> prev = head;
        for (int i = 0; i < index; i++)
            prev = prev.next;
        
        // 创建新节点并插入到链表中
        Node<E> node = new Node<>(element);
        node.next = prev.next;  // 新节点的下一个节点指向prev的下一个节点
        prev.next = node;       // prev的下一个节点指向新节点
        size++;                 // 链表大小加1
    }

    public E remove(int index) {
        // 检查删除位置是否合法
        if(index<0 || index>size-1)
            throw new IndexOutOfBoundsException("删除位置非法，0~"+(size-1));
        
        // 从头节点开始遍历，找到删除位置的前一个节点
        Node<E> prev = head;
        for(int i = 0; i < index; i++)
            prev = prev.next;
        
        // 删除节点并返回被删除的元素
        E e = prev.next.element;      // 保存要删除节点的元素
        prev.next = prev.next.next;  // 跳过要删除的节点
        size--;                       // 链表大小减1
        return e;                     // 返回被删除的元素
    }

    public E get(int index) {
        // 检查获取位置是否合法
        if(index<0 || index>size-1)
            throw new IndexOutOfBoundsException("获取位置非法，0~"+(size-1));
        
        // 从头节点的下一个节点开始遍历，找到指定位置的节点
        Node<E> node = head;
        while(index >= 0) {
            node = node.next;
            index--;
        }
        return node.element;  // 返回找到的节点的元素
    }

    public void set(int index, E element) {
        // 检查修改位置是否合法
        if(index < 0 || index >= size)
            throw new IndexOutOfBoundsException("修改位置非法，0~" + (size-1));
        
        // 从头节点的下一个节点开始遍历，找到指定位置的节点
        Node<E> node = head;
        while (index >= 0) {
            node = node.next;
            index--;
        }
        node.element = element;  // 修改节点的元素值
    }
    
    /**
     * 重写toString方法，返回链表中所有元素的字符串表示
     * @return 链表元素的字符串表示
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node<E> node = head.next;  // 从头节点的下一个节点开始遍历
        while(node != null) {
            builder.append(node.element).append(" ");  // 将元素添加到字符串构建器中
            node = node.next;  // 移动到下一个节点
        }
        return builder.toString();  // 返回构建好的字符串
    }
    
    // 链表节点的静态内部类
    private static class Node<E> {
        private E element;  // 节点存储的元素
        private Node<E> next;  // 指向下一个节点的引用

        public Node(E e) {
            this.element = e;  // 初始化节点元素
        }
    }
}

在 Java 中，顺序表（如ArrayList）和链表（如LinkedList）是两种常用的数据结构，它们各有优缺点，适用于不同的场景。以下是选择使用顺序表或链表的主要依据：

1. 需要频繁随机访问元素时，优先使用顺序表
顺序表（如ArrayList）通过数组实现，支持O (1) 时间复杂度的随机访问。通过索引可以直接定位到元素，适合需要快速查找的场景。
链表（如LinkedList）需要从头节点开始遍历，随机访问的时间复杂度为O(n)，效率较低。

2. 需要频繁插入或删除元素时，优先使用链表
链表在插入或删除操作时，只需修改指针，时间复杂度为O(1)（前提是已知节点位置）。
顺序表在插入或删除元素时，可能需要移动大量元素，时间复杂度为O(n)。