Java数据结构之链表的增删查改详解

简介

链表是非常常用的数据结构之一，它将数据储存在一个个结点中，每个结点存储了它所代表的数据和它下一个结点的指针，通过这些指针链接在一起，形成了一条链。

新建链表

// 定义链表中元素的结构
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 新建一条链表
ListNode head = new ListNode(0);

在Java中，通过定义一个链表中“元素”的结构体ListNode，来定义每一个结点的数据和指针。新建一条链表时，需要新建一个虚拟的头结点head，它的val可以是任意值，next指针指向null。

插入结点

ListNode p = head;
ListNode newNode = new ListNode(1);
while (p.next != null) {
    p = p.next;
}
p.next = newNode;

新插入一个节点时，需要依次遍历链表，找到尾部结点，然后将新结点插入到尾部结点的next指针处。

删除结点

ListNode p = head;
while (p.next != null && p.next.val != val) {
    p = p.next;
}
if (p.next != null) {
    p.next = p.next.next;
}

删除一个节点时，需要依次遍历链表，找到要删除的结点的前一个结点，然后将前一个结点的next指向要删除结点的next，即可将要删除的结点删除。

查找结点

ListNode p = head;
while (p.next != null && p.next.val != val) {
    p = p.next;
}
if (p.next != null) {
    return p.next;
} else {
    return null;
}

查找一个节点时，需要依次遍历链表，查找与给定值相等的结点，然后返回该结点。

修改结点

ListNode p = head;
while (p.next != null && p.next.val != val) {
    p = p.next;
}
if (p.next != null) {
    p.next.val = newVal;
}

修改一个结点时，需要依次遍历链表，查找到需要修改的结点，然后将该结点的val值修改为新值。

示例

// 新建一条链表
ListNode head = new ListNode(0);

// 插入三个结点
ListNode p = head;
for (int i = 1; i <= 3; i++) {
    ListNode newNode = new ListNode(i);
    while (p.next != null) {
        p = p.next;
    }
    p.next = newNode;
}

// 修改第二个结点的值为4
p = head;
while (p.next != null && p.next.val != 2) {
    p = p.next;
}
if (p.next != null) {
    p.next.val = 4;
}

// 删除第三个结点
p = head;
while (p.next != null && p.next.val != 3) {
    p = p.next;
}
if (p.next != null) {
    p.next = p.next.next;
}

// 查找第二个结点
p = head;
while (p.next != null && p.next.val != 2) {
    p = p.next;
}
if (p.next != null) {
    System.out.println(p.next.val); // 输出4
}

以上示例代码新建一条链表并且插入三个结点，然后修改第二个结点的值为4，删除第三个结点，最后查找第二个结点并输出它的值。