让我们来讲解一下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实现单链表中的增删改的完整攻略,希望对您有所帮助!
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:java实现单链表中的增删改 - Python技术站