Java 数据结构链表操作实现代码

下面是关于“Java 数据结构链表操作实现代码”的完整攻略。

1.链表实现原理

链表是一种经典的数据结构，其主要原理是通过指针将一系列节点连接起来。链表中的节点包含两个部分，一个是数据域，用于存放数据；另一个是指针域，用于指向下一个节点的位置。链表的头结点指向链表的第一个节点，最后一个节点的指针指向空。

2.链表的基本操作

链表的基本操作包括创建链表、插入节点、删除节点、遍历链表等。下面逐一介绍它们的实现。

2.1 创建链表

创建链表的基本方法就是依次创建每个节点，并将节点指针连接起来，最后返回头结点。以下是一个创建链表的示例代码：

public static Node createLinkedList(int[] array) {
    if (array == null || array.length == 0) {
        return null;
    }
    Node head = new Node(array[0]);
    Node p = head;
    for (int i = 1; i < array.length; i++) {
        Node node = new Node(array[i]);
        p.next = node;
        p = node;
    }
    return head;
}

其中，Node 是链表的节点类，包含值和指向下一个节点的指针。这个函数的输入是一个整型数组，输出为创建的链表的头节点。

2.2 插入节点

插入节点需要分为两个阶段，首先需要找到需要插入的位置，然后创建插入的节点并将指针连接起来。以下是一个插入节点的示例代码：

public static Node insertNode(Node head, int position, int value) {
    if (head == null || position < 1) {
        return null;
    }
    // 插入到第一个节点之前
    if (position == 1) {
        Node node = new Node(value);
        node.next = head;
        return node;
    }
    Node p = head;
    // 找到第position-1个节点
    for (int i = 1; i < position - 1 && p != null; i++) {
        p = p.next;
    }
    if (p == null) {
        return null;
    }
    Node node = new Node(value);
    node.next = p.next;
    p.next = node;
    return head;
}

这个函数的输入是头结点、插入位置和插入值，输出为新链表的头节点。

2.3 删除节点

删除节点也需要分为两个阶段，首先需要找到需要删除的位置，然后将指针连接起来。以下是一个删除节点的示例代码：

public static Node deleteNode(Node head, int position) {
    if (head == null || position < 1) {
        return null;
    }
    // 删除第一个节点
    if (position == 1) {
        return head.next;
    }
    Node p = head;
    // 找到第position-1个节点
    for (int i = 1; i < position - 1 && p != null; i++) {
        p = p.next;
    }
    if (p == null || p.next == null) {
        return null;
    }
    p.next = p.next.next;
    return head;
}

这个函数的输入是头结点和需要删除的位置，输出为新链表的头节点。

2.4 遍历链表

遍历链表就是依次输出每个节点的值，以下是一个遍历链表的示例代码：

public static void printLinkedList(Node head) {
    Node p = head;
    while (p != null) {
        System.out.print(p.value + " ");
        p = p.next;
    }
    System.out.println();
}

这个函数的输入是头结点，输出是依次输出节点值。

3.示例说明

3.1 示例 1：创建链表并遍历

下面介绍如何使用以上的代码创建链表并遍历。首先创建一个数组作为链表的元素，然后使用 createLinkedList 函数创建链表，最后使用 printLinkedList 函数遍历链表。

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    Node head = createLinkedList(array);
    printLinkedList(head);
}

输出结果：

1 2 3 4 5 

3.2 示例 2：插入节点并遍历

下面介绍如何使用以上的代码插入节点并遍历链表。首先创建一个数组作为链表的元素，然后使用 createLinkedList 函数创建链表，接着使用 insertNode 函数在第三个位置插入元素 6，最后使用 printLinkedList 函数遍历链表。

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    Node head = createLinkedList(array);
    head = insertNode(head, 3, 6);
    printLinkedList(head);
}

输出结果：

1 2 6 3 4 5 

以上就是关于“Java 数据结构链表操作实现代码”的完整攻略，希望能够对你有所帮助。