java实现单链表中的增删改

让我们来讲解一下Java实现单链表中的增删改的完整攻略。

一、单链表概述

单链表是一种线性数据结构，它是由若干个节点组成，每个节点包含两部分，一部分是存储数据的元素，另一部分是指向下一个节点的指针。单链表的头节点没有前驱节点，尾节点没有后继节点。

单链表常用的操作有插入、删除、修改和查询，其中插入和删除操作是单链表的核心操作。

二、Java单链表实现

下面我们来介绍Java中单链表的实现方式。

1. 节点类的定义

单链表的节点类定义包含两个属性：data（存储节点的值），next（存储指向下一个节点的指针）。

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

2. 增加节点

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

2.1 头部插入

在链表头部添加节点。

public void addFirst(int val) {
    ListNode node = new ListNode(val);
    node.next = head;
    head = node;
}

2.2 尾部插入

在链表尾部添加节点。

public void addLast(int val) {
    ListNode node = new ListNode(val);
    if (head == null) {
        head = node;
    } else {
        ListNode p = head;
        while (p.next != null) {
            p = p.next;
        }
        p.next = node;
    }
}

2.3 中间插入

在链表中间添加节点。

public void addAtPosition(int val, int position) {
    ListNode node = new ListNode(val);
    ListNode p = head;
    for (int i = 1; i < position; i++) {
        p = p.next;
        if (p == null) {
            return; // 无法插入
        }
    }
    node.next = p.next;
    p.next = node;
}

3. 删除节点

单链表的删除操作也分为头部删除、尾部删除和中间删除三种情况。

3.1 头部删除

删除链表头部节点。

public void deleteFirst() {
    if (head != null) {
        head = head.next;
    }
}

3.2 尾部删除

删除链表尾部节点。

public void deleteLast() {
    if (head == null) {
        return;
    } else if (head.next == null) {
        head = null;
    } else {
        ListNode p = head;
        while (p.next.next != null) {
            p = p.next;
        }
        p.next = null;
    }
}

3.3 中间删除

删除链表中间节点。

public void deleteAtPosition(int position) {
    if (position == 1) {
        deleteFirst();
        return;
    }
    ListNode p = head;
    ListNode q = null;
    for (int i = 1; i < position; i++) {
        if (p == null) {
            return;
        }
        q = p;
        p = p.next;
    }
    if (p == null) {
        return;
    }
    q.next = p.next;
}

4. 修改节点

修改链表中指定位置节点的值。

public void update(int position, int val) {
    ListNode p = head;
    for (int i = 1; i <= position; i++) {
        if (p == null) {
            return;
        }
        p = p.next;
    }
    if (p == null) {
        return;
    }
    p.val = val;
}

三、示例说明

1. 插入操作

如下面代码所示，我们创建一个单链表，先在链表头部插入一个节点，再在链表尾部插入一个节点，最后在链表特定位置插入一个节点，这个位置是链表第三个节点。

ListNode head = new ListNode(1);
head.addFirst(0);
head.addLast(3);
head.addAtPosition(2, 3);

插入完的单链表如下所示：

0 -> 1 -> 2 -> 3

2. 删除操作

如下面代码所示，我们删除刚才创建的单链表中的节点，先删除链表头部节点，再删除链表尾部节点，最后删除链表第二个节点。

head.deleteFirst();
head.deleteLast();
head.deleteAtPosition(2);

删除完的单链表如下所示：

0 -> 3

3. 修改操作

如下面代码所示，我们修改刚才创建的单链表中的节点值，将链表第二个节点的值修改为“2”。

head.update(2, 2);

修改完的单链表如下所示：

0 -> 2 -> 3

以上就是Java实现单链表中的增删改的完整攻略，希望对您有所帮助！