数据结构单向 循环 双向 链表的插入 删除 查询
单向链表、双向链表、单向循环链表的建立、插入和删除操作。
建立一个单向链表，输入一串随机指定位数的整数并排序（升序或者降序），同时可以实现插入节点、删除节点、节点显示等操作，用编写一个菜单，由用户选择执行哪一种操作(插入/删除/按值查询)，并输出链表。
import java.util.Scanner;
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
private Node head;
// 插入节点（升序）
public void insert(int data) {
Node newNode = new Node(data);
if (head == null || head.data >= newNode.data) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
// 删除节点
public void delete(int data) {
if (head == null) {
System.out.println("链表为空");
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next;
}
if (current.next == null) {
System.out.println("未找到节点：" + data);
} else {
current.next = current.next.next;
}
}
// 显示链表
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// 查找节点
public boolean search(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
}
public class Solution16 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
SinglyLinkedList list = new SinglyLinkedList();
while (true) {
System.out.println("选择操作：");
System.out.println("1. 插入节点");
System.out.println("2. 删除节点");
System.out.println("3. 显示链表");
System.out.println("4. 查找节点");
System.out.println("5. 退出");
int choice = scanner.nextInt();
switch (choice) {
case 1:
System.out.print("输入要插入的整数：");
int insertData = scanner.nextInt();
list.insert(insertData);
break;
case 2:
System.out.print("输入要删除的整数：");
int deleteData = scanner.nextInt();
list.delete(deleteData);
break;
case 3:
System.out.println("链表内容：");
list.display();
break;
case 4:
System.out.print("输入要查找的整数：");
int searchData = scanner.nextInt();
if (list.search(searchData)) {
System.out.println("找到节点：" + searchData);
} else {
System.out.println("未找到节点：" + searchData);
}
break;
case 5:
System.out.println("退出");
scanner.close();
return;
default:
System.out.println("无效选择");
}
}
}
}
// 双向链表
class DNode {
int data;
DNode next;
DNode prev;
public DNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
private DNode head;
// 插入节点（升序）
public void insert(int data) {
DNode newNode = new DNode(data);
if (head == null || head.data >= newNode.data) {
newNode.next = head;
if (head != null) head.prev = newNode;
head = newNode;
} else {
DNode current = head;
while (current.next != null && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
if (current.next != null) current.next.prev = newNode;
current.next = newNode;
newNode.prev = current;
}
}
// 删除节点
public void delete(int data) {
if (head == null) {
System.out.println("链表为空");
return;
}
if (head.data == data) {
head = head.next;
if (head != null) head.prev = null;
return;
}
DNode current = head;
while (current != null && current.data != data) {
current = current.next;
}
if (current == null) {
System.out.println("未找到节点：" + data);
} else {
if (current.next != null) current.next.prev = current.prev;
if (current.prev != null) current.prev.next = current.next;
}
}
// 显示链表
public void display() {
DNode current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// 查找节点
public boolean search(int data) {
DNode current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
}
//单向循环链表
class CircularLinkedList {
private Node head;
// 插入节点（升序）
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
newNode.next = head;
} else if (head.data >= newNode.data) {
Node tail = head;
while (tail.next != head) {
tail = tail.next;
}
newNode.next = head;
head = newNode;
tail.next = head;
} else {
Node current = head;
while (current.next != head && current.next.data < newNode.data) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
// 删除节点
public void delete(int data) {
if (head == null) {
System.out.println("链表为空");
return;
}
if (head.data == data) {
if (head.next == head) {
head = null;
} else {
Node tail = head;
while (tail.next != head) {
tail = tail.next;
}
head = head.next;
tail.next = head;
}
return;
}
Node current = head;
while (current.next != head && current.next.data != data) {
current = current.next;
}
if (current.next == head) {
System.out.println("未找到节点：" + data);
} else {
current.next = current.next.next;
}
}
// 显示链表
public void display() {
if (head == null) {
System.out.println("链表为空");
return;
}
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
// 查找节点
public boolean search(int data) {
if (head == null) return false;
Node current = head;
do {
if (current.data == data) {
return true;
}
current = current.next;
} while (current != head);
return false;
}
}-
双向链表:
- 每个节点有两个指针：
next和prev。 - 在插入和删除操作中需更新
prev指针。
- 每个节点有两个指针：
-
循环链表:
- 最后一个节点的
next指针指向头节点。 - 插入和删除时需要考虑循环结构，尤其是在头节点的操作。
- 最后一个节点的