Java实现单链表SingleLinkedList增删改查及反转 逆序等

Java实现单链表SingleLinkedList增删改查及反转 逆序等

简介

单链表是数据结构中常见的一种，它是由一系列节点（Node）构成的链式结构，每个节点包含两部分：数据部分和指针部分，数据部分用于存储节点的数据，指针部分用于指向下一个节点。单链表的头节点指向第一个有效节点，最后一个节点的指针指向NULL。

SingleLinkedList类

我们首先需要定义一个SingleLinkedList类，用于描述单链表结构。

public class SingleLinkedList<T> {
    // 头结点
    private Node<T> head;

    // 结点数
    private int size;

    // 节点定义
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    //构造方法
    public SingleLinkedList() {
        this.head = null;
        this.size = 0;
    }

    //添加节点
    public void add(T data) {
        Node<T> node = new Node<>(data);
        if (head == null) {
            head = node;
        } else {
            Node<T> cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
        size++;
    }

    //删除节点
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            head = head.next;
        } else {
            Node<T> prev = get(index - 1);
            prev.next = prev.next.next;
        }
        size--;
    }

    //修改节点数据
    public void set(int index, T data) {
        Node<T> node = get(index);
        node.data = data;
    }

    //获取节点数据
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.data;
    }

    //获取链表长度
    public int size() {
        return size;
    }

    //反转链表
    public void reverse() {
        Node<T> prev = null;
        Node<T> cur = head;
        while (cur != null) {
            Node<T> next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        head = prev;
    }
}

测试

我们可以通过简单的测试来验证单链表的相关操作是否正确。

public class SingleLinkedListTest {
    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        //添加数据
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //获取数据
        System.out.println(list.get(0)); //输出1
        System.out.println(list.get(1)); //输出2
        System.out.println(list.get(2)); //输出3
        System.out.println(list.get(3)); //输出4
        //修改数据
        list.set(0, 0);
        System.out.println(list.get(0)); //输出0
        //删除数据
        list.remove(2);
        System.out.println(list.get(2)); //输出4
        //反转链表
        list.reverse();
        System.out.println(list.get(0)); //输出4
        System.out.println(list.get(1)); //输出3
        System.out.println(list.get(2)); //输出2
        System.out.println(list.get(3)); //输出0
    }
}

示例说明

假设有如下单链表：

1 -> 2 -> 3 -> 4 -> 5

我们需要删除第3个节点，修改第5个节点的数据，然后反转链表。

SingleLinkedList<Integer> list = new SingleLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

// 删除第3个节点
list.remove(2);

// 修改第5个节点的数据
list.set(3, 6);

// 反转链表
list.reverse();

System.out.println(list.get(0));  // 输出5
System.out.println(list.get(1));  // 输出4
System.out.println(list.get(2));  // 输出6
System.out.println(list.get(3));  // 输出2

另外，假设有如下单链表：

A -> B -> C -> D

我们需要在第2个节点后插入一个节点E。

SingleLinkedList<String> list = new SingleLinkedList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");

Node<String> node = new Node<>("E");
node.next = list.get(2).next;
list.get(2).next = node;

System.out.println(list.get(1));  // 输出B
System.out.println(list.get(2));  // 输出E
System.out.println(list.get(3));  // 输出C

以上就是单链表的常见操作及其实现方式，通过这些例子我们可以更加清晰地了解单链表的使用。