深入理解链表：操作、排序与类设计

### 深入理解链表：操作、排序与类设计 #### 1. 链表基础操作在处理链表时，插入操作有不同的方式，对应不同的数据结构特性。 - **队列式插入（Program P3.1）**：将传入的数字插入到链表尾部，这是向队列添加元素的示例。队列是一种线性列表，插入操作在一端进行，删除操作在另一端进行。 - **栈式插入（Program P3.2）**：将传入的数字插入到链表头部，这是向栈添加元素的示例。栈是一种线性列表，插入和删除操作都在同一端进行。添加元素时称为“入栈”（push），删除元素时称为“出栈”（pop）。以下是 Program P3.2 的代码示例： ```java import java.util.*; public class BuildList2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); Node top, np, last = null; top = null; System.out.printf("Enter some integers ending with 0\n"); int n = in.nextInt(); while (n != 0) { np = new Node(n); np.next = top; top = np; n = in.nextInt(); } System.out.printf("\nThe items in the list are\n"); printList(top); } //end main public static void printList(Node top) { while (top != null) { //as long as there's a node System.out.printf("%d ", top.num); top = top.next; //go on to the next node } System.out.printf("\n"); } //end printList } //end class BuildList2 class Node { int num; Node next; public Node(int n) { num = n; next = null; } } //end class Node ``` 示例运行结果： ``` Enter some integers ending with 0 9 1 8 2 7 3 6 4 5 0 The items in the list are 5 4 6 3 7 2 8 1 9 ``` #### 2. 链表节点删除操作从链表中删除节点有不同的情况。 - **删除链表顶部节点**：使用 `top = top.next;` 语句，让 `top` 指向原来第一个节点所指向的节点（即第二个节点，如果存在）。在删除之前，需要检查 `top` 是否为 `null`。如果链表中只有一个节点，删除后链表将为空，`top` 变为 `null`。 - **删除任意节点**：假设 `curr` 指向要删除的节点，需要知道前一个节点的指针 `prev`，然后使用 `prev.next = curr.next;` 语句将前一个节点的 `next` 字段指向要删除节点的下一个节点，从而将该节点从链表中删除。 Java 采用自动垃圾回收机制处理被删除的节点。虽然逻辑上节点已被删除，但它们仍占用内存。Java 会定期检查这些“不可达”节点并回收其占用的存储空间，程序员无需担心这些“已删除”节点。 #### 3. 构建有序链表若要构建一个数字按升序排列的链表，当读取一个新数字时，需要将其插入到现有链表的合适位置。 - **插入逻辑**：首先将第一个数字添加到空链表中。对于后续数字，将其与链表中的数字进行比较，只要新数字大于链表中的某个数字，就继续向下遍历链表，直到新数字小于或等于某个现有数字，或者到达链表末尾。 - **代码实现**： ```java import java.util.*; public class BuildList3 { public static void main(String[] args) { Scanner in = new Scanner(System.in); Node top, np, last = null; top = null; System.out.printf("Enter some integers ending with 0\n"); int n = in.nextInt(); while (n != 0) { top = addInPlace(top, n); n = in.nextInt(); } printList(top); } //end main public static Node addInPlace(Node top, int n) { Node np, curr, prev; np = new Node(n); prev = null; curr = top; while (curr != null && n > curr.num) { prev = curr; curr = curr.next; ```