单向链表（Singly Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含两个部分：数据部分和指向下一个节点的指针。单向链表的特点是每个节点只指向下一个节点，最后一个节点的指针指向 null，表示链表的结束。
单向链表的基本操作
1. 创建链表
创建一个链表，需要一个头节点，头节点不存储数据，只存储指向第一个节点的指针。
2. 添加节点
可以在链表的头部、尾部或中间添加节点。
3. 删除节点
可以删除链表的头部、尾部或中间的节点。
4. 查找节点
可以根据节点的值查找节点。
5. 遍历链表
从头节点开始，依次访问每个节点。
单向链表优缺点
优点
- 链表的长度可以动态增加，不像数组需要提前分配内存空间。
- 插入和删除节点的时间复杂度为 O(1)，不需要移动其他元素，效率高。
缺点
- 链表的随机访问效率低，时间复杂度为 O(n)，每次都需要从头访问。
- 链表需要额外的内存空间存储指针，占用内存较大。
单向链表的实现
SinglyLinkedListDemo.java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + (next != null) +
'}';
}
}
class LinkedList {
Node head;
LinkedList() {
this.head = null;
}
void insert(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;
}
void delete(int data) {
if (head == null) {
return;
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null) {
if (current.next.data == data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
void print() {
Node current = head;
while (current.next != null) {
System.out.print(current + " -> ");
current = current.next;
}
System.out.println(current);
}
}
public class SinglyLinkedListDemo {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.print();
list.delete(3);
list.print();
}
}
打印结果
bash
Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=3, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}
Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}