线性表——单链表

Java中的单链表是一种常见的数据结构，用于以线性方式存储元素集合，但与数组不同，单链表中的元素不是连续存储在内存中的。

每个元素（或称为节点）包含两个部分：一部分是存储的数据（data），另一部分是指向列表中下一个元素的引用（或链接，link）。

这种结构使得单链表在插入和删除元素时更加灵活，因为不需要移动其他元素来腾出空间或填补空白。

1. 节点（Node）的定义

在Java中，单链表中的每个节点通常通过一个内部类来定义，这个内部类包含两个成员：一个是存储的数据（可以是任意类型），另一个是指向下一个节点的引用。

class ListNode<T> {  
    T data; // 节点存储的数据  
    ListNode<T> next; // 指向下一个节点的引用  
  
    // 构造函数  
    public ListNode(T data) {  
        this.data = data;  
        this.next = null; // 默认下一个节点为空  
    }  
}

2. 单链表的定义

单链表本身可以看作是一个指向链表第一个节点的引用（或称为头节点），以及可能包含的一些方法，如添加、删除、查找节点等。

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

// 输入一个数组，转换为一条单链表
ListNode createLinkedList(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    ListNode head = new ListNode(arr[0]);
    ListNode cur = head;
    for (int i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return head;
}

// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 遍历单链表
for (ListNode p = head; p != null; p = p.next) {
    System.out.println(p.val);
}



// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 在单链表头部插入一个新节点 0 
ListNode newHead = new ListNode(0);
newHead.next = head;
head = newHead;
// 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5


// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 在单链表尾部插入一个新节点 6
ListNode p = head;
// 先走到链表的最后一个节点
while (p.next != null) {
    p = p.next;
}
// 现在 p 就是链表的最后一个节点
// 在 p 后面插入新节点
p.next = new ListNode(6);

// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6


// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 在第 3 个节点后面插入一个新节点 66
// 先要找到前驱节点，即第 3 个节点
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}
// 此时 p 指向第 3 个节点
// 组装新节点的后驱指针
ListNode newNode = new ListNode(66);
newNode.next = p.next;

// 插入新节点
p.next = newNode;

// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5


// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除第 4 个节点，要操作前驱节点
ListNode p = head;
for (int i = 0; i < 2; i++) {
    p = p.next;
}

// 此时 p 指向第 3 个节点，即要删除节点的前驱节点
// 把第 4 个节点从链表中摘除
p.next = p.next.next;

// 现在链表变成了 1 -> 2 -> 3 -> 5


// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除尾节点
ListNode p = head;
// 找到倒数第二个节点
while (p.next.next != null) {
    p = p.next;
}

// 此时 p 指向倒数第二个节点
// 把尾节点从链表中摘除
p.next = null;

// 现在链表变成了 1 -> 2 -> 3 -> 4


// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});

// 删除头结点
head = head.next;

// 现在链表变成了 2 -> 3 -> 4 -> 5

3. 单链表的基本操作

• 添加（Append）：向链表末尾添加一个新节点。
• 插入（Insert）：在链表中的指定位置插入一个新节点。
• 删除（Delete）：删除链表中的指定节点或具有特定值的节点。
• 查找（Search）：查找链表中是否存在具有特定值的节点，并返回该节点（或节点的数据）。
• 遍历（Traverse）：遍历链表中的每个节点，并对每个节点执行某些操作（如打印节点的数据）。

4. 优点和缺点

优点：

• 插入和删除操作效率高，因为不需要移动其他元素。
• 动态数据结构，大小不固定。

缺点：

• 访问链表中的元素不如数组快，因为需要从头节点开始遍历。
• 额外的空间开销，因为每个节点都需要存储指向下一个节点的引用。