博客

带头单链表

带头单链表是一种基础的数据结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。带头单链表的头节点不存储数据，只用于指向第一个节点，方便对链表进行操作。下面我们使用JAVA语言来实现一个带头单链表。

定义节点类

我们首先需要定义一个节点类，它包含以下属性：

• data：存储节点数据
• next：指向下一个节点的指针

public class Node {
    private int data;
    private Node next;
}

定义带头单链表类

在定义节点类后，我们需要定义一个带头单链表类，它包含以下属性：

• head：头节点
• length：链表长度

public class LinkedList {
    private Node head;
    private int length;
}

实现带头单链表的初始化方法

初始化方法将创建一个头节点，并将链表长度设置为0。

public LinkedList() {
    this.head = new Node();
    this.length = 0;
}

实现带头单链表的插入方法

带头单链表的插入操作需要先找到插入位置的前一个节点，然后将新节点插入到该节点后面。下面是实现带头单链表插入操作的代码：

public void insert(int index, int value) {
    if (index < 0 || index > length) {
        throw new IndexOutOfBoundsException("Index out of range.");
    }
    Node node = new Node();
    node.setData(value);
    Node prev = head;
    for (int i = 0; i < index; i++) {
        prev = prev.getNext();
    }
    node.setNext(prev.getNext());
    prev.setNext(node);
    length++;
}

实现带头单链表的删除方法

带头单链表的删除操作需要先找到要删除的节点的前一个节点，然后将该节点从链表中删除。下面是实现带头单链表删除操作的代码：

public void delete(int index) {
    if (index < 0 || index >= length) {
        throw new IndexOutOfBoundsException("Index out of range.");
    }
    Node prev = head;
    for (int i = 0; i < index; i++) {
        prev = prev.getNext();
    }
    Node node = prev.getNext();
    prev.setNext(node.getNext());
    node.setNext(null);
    length--;
}

实现带头单链表的查找方法

带头单链表的查找操作需要遍历整个链表，查找指定元素的位置。下面是实现带头单链表查找操作的代码：

public int search(int value) {
    Node node = head.getNext();
    int index = 0;
    while (node != null) {
        if (node.getData() == value) {
            return index;
        }
        node = node.getNext();
        index++;
    }
    return -1;
}

实现带头单链表的打印方法

最后，我们需要实现一个打印方法，用于打印带头单链表中的所有元素。

public void print() {
    System.out.print("[");
    Node node = head.getNext();
    while (node != null) {
        System.out.print(node.getData());
        node = node.getNext();
        if (node != null) {
            System.out.print(", ");
        }
    }
    System.out.println("]");
}

使用以上代码，我们就可以实现一个基本的带头单链表。带头单链表是一种常用的数据结构，它可以用于解决许多实际问题。同时，带头单链表也是其他数据结构的基础，例如双向链表和循环链表等。