Linked List

链表定义

链表是一种线性数据元素的集合，其顺序并不由它们在内存中的物理位置决定。相反，每个元素指向下一个元素。链表是一种数据结构，由一组节点组成，这些节点共同表示一个序列。在其最基本的形式中，每个节点包含数据，以及对序列中下一个节点的引用（换句话说，即链接）。

VisualizeLinkedList

链表特点

链表是一种线性数据结构
链表中的元素在内存中不一定是连续存储的
链表中的每个元素都包含一个指向下一个元素的指针
链表的插入和删除操作非常高效，时间复杂度为 O(1)
链表的查找操作效率较低，时间复杂度为 O(n)

链表代码实现

Java 实现

public class LinkedList<T> {
    // 定义节点类
    private class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;  // 头节点
    private Node tail;  // 尾节点
    private int size;   // 链表大小

    // 构造函数
    public LinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    // 获取链表大小
    public int size() {
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表头部添加元素
    public void addFirst(T data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        size++;
    }

    // 在链表尾部添加元素
    public void addLast(T data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    // 在指定位置添加元素
    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        if (index == 0) {
            addFirst(data);
            return;
        }

        if (index == size) {
            addLast(data);
            return;
        }

        Node prev = getNode(index - 1);
        Node newNode = new Node(data);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    // 删除第一个元素
    public T removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("List is empty");
        }

        T data = head.data;
        head = head.next;
        size--;

        if (isEmpty()) {
            tail = null;
        }

        return data;
    }

    // 删除最后一个元素
    public T removeLast() {
        if (isEmpty()) {
            throw new IllegalStateException("List is empty");
        }

        if (size == 1) {
            return removeFirst();
        }

        Node prev = getNode(size - 2);
        T data = tail.data;
        prev.next = null;
        tail = prev;
        size--;
        return data;
    }

    // 删除指定位置的元素
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        if (index == 0) {
            return removeFirst();
        }

        if (index == size - 1) {
            return removeLast();
        }

        Node prev = getNode(index - 1);
        T data = prev.next.data;
        prev.next = prev.next.next;
        size--;
        return data;
    }

    // 获取指定位置的元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return getNode(index).data;
    }

    // 修改指定位置的元素
    public void set(int index, T data) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        getNode(index).data = data;
    }

    // 查找元素，返回第一次出现的位置
    public int indexOf(T data) {
        Node current = head;
        int index = 0;
        while (current != null) {
            if (current.data.equals(data)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    // 清空链表
    public void clear() {
        head = tail = null;
        size = 0;
    }

    // 获取指定位置的节点
    private Node getNode(int index) {
        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    // 打印链表
    public void print() {
        Node current = head;
        System.out.print("List: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

use example

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // 测试添加元素
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.print(); // List: 1 2 3

        // 测试在指定位置添加元素
        list.add(1, 4);
        list.print(); // List: 1 4 2 3

        // 测试删除元素
        System.out.println("Removed: " + list.remove(2)); // Removed: 2
        list.print(); // List: 1 4 3

        // 测试获取元素
        System.out.println("Element at index 1: " + list.get(1)); // Element at index 1: 4

        // 测试修改元素
        list.set(1, 5);
        list.print(); // List: 1 5 3

        // 测试查找元素
        System.out.println("Index of 5: " + list.indexOf(5)); // Index of 5: 1

        // 测试大小
        System.out.println("Size: " + list.size()); // Size: 3

        // 测试清空
        list.clear();
        System.out.println("Is empty? " + list.isEmpty()); // Is empty? true
    }
}

链表定义

链表特点

链表代码实现

Java 实现

Read Next

Stack

Queue