Java单链表的增删改查怎么实现

发布时间：2022-09-26 09:56:20 作者：iii
来源：亿速云阅读：130

Java单链表的增删改查怎么实现

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的增删改查操作是数据结构中最基础的操作之一。本文将详细介绍如何在Java中实现单链表的增删改查操作。

1. 单链表的基本结构

在Java中，单链表可以通过定义一个节点类和一个链表类来实现。节点类包含数据和指向下一个节点的指针，链表类则包含对链表进行操作的方法。

1.1 节点类的定义

class Node {
    int data; // 节点存储的数据
    Node next; // 指向下一个节点的指针

    // 构造函数
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

1.2 链表类的定义

class LinkedList {
    private Node head; // 链表的头节点

    // 构造函数
    public LinkedList() {
        this.head = null;
    }

    // 其他操作方法将在后续章节中介绍
}

2. 单链表的插入操作

单链表的插入操作可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。

2.1 在链表头部插入节点

在链表头部插入节点是最简单的插入操作，只需要将新节点的next指针指向当前的头节点，然后将头节点更新为新节点。

public void insertAtHead(int data) {
    Node newNode = new Node(data); // 创建新节点
    newNode.next = head; // 新节点的next指向当前的头节点
    head = newNode; // 更新头节点为新节点
}

2.2 在链表尾部插入节点

在链表尾部插入节点需要遍历链表，找到最后一个节点，然后将最后一个节点的next指针指向新节点。

public void insertAtTail(int data) {
    Node newNode = new Node(data); // 创建新节点

    if (head == null) {
        head = newNode; // 如果链表为空，新节点即为头节点
        return;
    }

    Node current = head;
    while (current.next != null) {
        current = current.next; // 遍历链表，找到最后一个节点
    }
    current.next = newNode; // 最后一个节点的next指向新节点
}

2.3 在链表中间插入节点

在链表中间插入节点需要先找到插入位置的前一个节点，然后将新节点的next指针指向插入位置的后一个节点，最后将前一个节点的next指针指向新节点。

public void insertAtPosition(int data, int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }

    Node newNode = new Node(data); // 创建新节点

    if (position == 0) {
        insertAtHead(data); // 如果插入位置为0，相当于在头部插入
        return;
    }

    Node current = head;
    for (int i = 0; i < position - 1; i++) {
        if (current == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next; // 遍历链表，找到插入位置的前一个节点
    }

    newNode.next = current.next; // 新节点的next指向插入位置的后一个节点
    current.next = newNode; // 前一个节点的next指向新节点
}

3. 单链表的删除操作

单链表的删除操作可以分为删除头节点、删除尾节点和删除中间节点三种情况。

3.1 删除头节点

删除头节点只需要将头节点更新为当前头节点的下一个节点。

public void deleteAtHead() {
    if (head == null) {
        throw new IllegalStateException("List is empty");
    }
    head = head.next; // 更新头节点为下一个节点
}

3.2 删除尾节点

删除尾节点需要遍历链表，找到倒数第二个节点，然后将其next指针置为null。

public void deleteAtTail() {
    if (head == null) {
        throw new IllegalStateException("List is empty");
    }

    if (head.next == null) {
        head = null; // 如果链表只有一个节点，直接删除头节点
        return;
    }

    Node current = head;
    while (current.next.next != null) {
        current = current.next; // 遍历链表，找到倒数第二个节点
    }
    current.next = null; // 倒数第二个节点的next置为null
}

3.3 删除中间节点

删除中间节点需要先找到要删除节点的前一个节点，然后将其next指针指向要删除节点的下一个节点。

public void deleteAtPosition(int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }

    if (head == null) {
        throw new IllegalStateException("List is empty");
    }

    if (position == 0) {
        deleteAtHead(); // 如果删除位置为0，相当于删除头节点
        return;
    }

    Node current = head;
    for (int i = 0; i < position - 1; i++) {
        if (current.next == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next; // 遍历链表，找到要删除节点的前一个节点
    }

    if (current.next == null) {
        throw new IndexOutOfBoundsException("Position out of bounds");
    }

    current.next = current.next.next; // 前一个节点的next指向要删除节点的下一个节点
}

4. 单链表的查找操作

单链表的查找操作可以分为按值查找和按位置查找两种情况。

4.1 按值查找

按值查找需要遍历链表，找到第一个与目标值相等的节点。

public Node searchByValue(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) {
            return current; // 找到目标节点
        }
        current = current.next; // 继续遍历
    }
    return null; // 未找到目标节点
}

4.2 按位置查找

按位置查找需要遍历链表，找到指定位置的节点。

public Node searchByPosition(int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }

    Node current = head;
    for (int i = 0; i < position; i++) {
        if (current == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next; // 遍历链表，找到指定位置的节点
    }
    return current;
}

5. 单链表的修改操作

单链表的修改操作可以分为按值修改和按位置修改两种情况。

5.1 按值修改

按值修改需要遍历链表，找到第一个与目标值相等的节点，然后修改其数据。

public void updateByValue(int oldData, int newData) {
    Node current = head;
    while (current != null) {
        if (current.data == oldData) {
            current.data = newData; // 找到目标节点并修改其数据
            return;
        }
        current = current.next; // 继续遍历
    }
    throw new IllegalArgumentException("Value not found");
}

5.2 按位置修改

按位置修改需要遍历链表，找到指定位置的节点，然后修改其数据。

public void updateByPosition(int position, int newData) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }

    Node current = head;
    for (int i = 0; i < position; i++) {
        if (current == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next; // 遍历链表，找到指定位置的节点
    }
    current.data = newData; // 修改节点数据
}

6. 单链表的遍历操作

单链表的遍历操作可以通过从头节点开始，依次访问每个节点的数据。

public void traverse() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " "); // 输出节点数据
        current = current.next; // 继续遍历
    }
    System.out.println();
}

7. 完整代码示例

class Node {
    int data;
    Node next;

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

class LinkedList {
    private Node head;

    public LinkedList() {
        this.head = null;
    }

    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void insertAtTail(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    public void insertAtPosition(int data, int position) {
        if (position < 0) {
            throw new IllegalArgumentException("Position cannot be negative");
        }

        Node newNode = new Node(data);

        if (position == 0) {
            insertAtHead(data);
            return;
        }

        Node current = head;
        for (int i = 0; i < position - 1; i++) {
            if (current == null) {
                throw new IndexOutOfBoundsException("Position out of bounds");
            }
            current = current.next;
        }

        newNode.next = current.next;
        current.next = newNode;
    }

    public void deleteAtHead() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }
        head = head.next;
    }

    public void deleteAtTail() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }

        if (head.next == null) {
            head = null;
            return;
        }

        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }

    public void deleteAtPosition(int position) {
        if (position < 0) {
            throw new IllegalArgumentException("Position cannot be negative");
        }

        if (head == null) {
            throw new IllegalStateException("List is empty");
        }

        if (position == 0) {
            deleteAtHead();
            return;
        }

        Node current = head;
        for (int i = 0; i < position - 1; i++) {
            if (current.next == null) {
                throw new IndexOutOfBoundsException("Position out of bounds");
            }
            current = current.next;
        }

        if (current.next == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }

        current.next = current.next.next;
    }

    public Node searchByValue(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    public Node searchByPosition(int position) {
        if (position < 0) {
            throw new IllegalArgumentException("Position cannot be negative");
        }

        Node current = head;
        for (int i = 0; i < position; i++) {
            if (current == null) {
                throw new IndexOutOfBoundsException("Position out of bounds");
            }
            current = current.next;
        }
        return current;
    }

    public void updateByValue(int oldData, int newData) {
        Node current = head;
        while (current != null) {
            if (current.data == oldData) {
                current.data = newData;
                return;
            }
            current = current.next;
        }
        throw new IllegalArgumentException("Value not found");
    }

    public void updateByPosition(int position, int newData) {
        if (position < 0) {
            throw new IllegalArgumentException("Position cannot be negative");
        }

        Node current = head;
        for (int i = 0; i < position; i++) {
            if (current == null) {
                throw new IndexOutOfBoundsException("Position out of bounds");
            }
            current = current.next;
        }
        current.data = newData;
    }

    public void traverse() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

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

        list.insertAtHead(10);
        list.insertAtHead(20);
        list.insertAtTail(30);
        list.insertAtPosition(15, 1);

        list.traverse(); // 输出: 20 15 10 30

        list.deleteAtHead();
        list.deleteAtTail();
        list.deleteAtPosition(1);

        list.traverse(); // 输出: 15

        Node node = list.searchByValue(15);
        if (node != null) {
            System.out.println("Found: " + node.data); // 输出: Found: 15
        }

        list.updateByValue(15, 25);
        list.updateByPosition(0, 35);

        list.traverse(); // 输出: 35
    }
}

8. 总结

本文详细介绍了如何在Java中实现单链表的增删改查操作。通过定义节点类和链表类，我们可以轻松地实现单链表的各种操作。单链表虽然结构简单，但在实际应用中非常广泛，掌握其基本操作对于理解更复杂的数据结构和算法具有重要意义。希望本文能帮助你更好地理解和应用单链表。

Java单链表的增删改查怎么实现

Java单链表的增删改查怎么实现

1. 单链表的基本结构

1.1 节点类的定义

1.2 链表类的定义

2. 单链表的插入操作

2.1 在链表头部插入节点

2.2 在链表尾部插入节点

2.3 在链表中间插入节点

3. 单链表的删除操作

3.1 删除头节点

3.2 删除尾节点

3.3 删除中间节点

4. 单链表的查找操作

4.1 按值查找

4.2 按位置查找

5. 单链表的修改操作

5.1 按值修改

5.2 按位置修改

6. 单链表的遍历操作

7. 完整代码示例

8. 总结

相关阅读