Java链表的使用与比较

### Java 链表的使用与比较 #### 1. Java 文件组织 在 Java 编程中，对于多个类的存储和组织有一定的规则。之前我们处理过四个类：`LinkedList`、`Node`、`NodeData` 和 `LinkedListTest`。若要将它们存储在一个文件中（如程序 P3.4），除了 `LinkedListTest` 外，其他类都要去掉 `public` 关键字。为了让这些类能被其他类使用，我们可以按以下方式组织文件： - **`LinkedListTest` 类**：必须存储在名为 `LinkedListTest.java` 的文件中，因为 `public` 类 `x` 要存于 `x.java` 文件。 - **`NodeData` 类**：声明为 `public` 类，存储在 `NodeData.java` 文件中，代码如下： ```java public class NodeData { int num; public NodeData(int n) { num = n; } public int compareTo(NodeData nd) { if (this.num == nd.num) return 0; if (this.num < nd.num) return -1; return 1; } public String toString() { return num + " "; //" " needed to convert num to a string; may also use "" (empty string) } } //end class NodeData ``` - **`LinkedList` 类和 `Node` 类**：`LinkedList` 类声明为 `public` 类，存于 `LinkedList.java` 文件。由于 `Node` 类仅被 `LinkedList` 类使用，可省略 `public` 关键字，和 `LinkedList` 类存于同一文件，代码如下： ```java public class LinkedList { Node head = null; public boolean empty() { return head == null; } public void addHead(NodeData nd) { Node p = new Node(nd); p.next = head; head = p; } public void addInPlace(NodeData nd) { Node np, curr, prev; np = new Node(nd); prev = null; curr = head; while (curr != null && nd.compareTo(curr.data) > 0) { //nd is bigger prev = curr; curr = curr.next; } np.next = curr; if (prev == null) head = np; else prev.next = np; } //end addInPlace public void printList() { Node curr = head; while (curr != null) { System.out.printf("%s", curr.data); //invokes curr.data.toString() curr = curr.next; } System.out.printf("\n"); } //end printList } //end class LinkedList class Node { NodeData data; Node next; public Node(NodeData d) { data = d; next = null; } } //end class Node ``` 若 `Node` 类被其他类需要，最好将其声明为 `public` 类并放在 `Node.java` 文件中。 #### 2. 扩展 `LinkedList` 类 为了后续示例，我们给 `LinkedList` 类添加以下方法： - **`getHeadData` 方法**：返回列表中第一个节点的数据字段（若存在）。 ```java public NodeData getHeadData() { if (head == null) return null; return head.data; } ``` - **`deleteHead` 方法**：移除列表中的第一个节点（若存在）。 ```java public void deleteHead() { if (head != null) head = head.next; } ``` - **`addTail` 方法**：在列表末尾添加新节点。 ```java public void addTail(NodeData nd) { Node p = new Node(nd); if (head == null) head = p; else { Node curr = head; while (curr.next != null) curr = curr.next; curr.next = p; } } //end addTail ``` - **`copyList` 方法**：复制调用该方法的列表并返回副本。 ```java public LinkedList copyList() { LinkedList temp = new LinkedList(); Node curr = this.head; while (curr != null) { temp.addTail(curr.data); curr = curr.next; } return temp; } //end copyList ``` - **`reverseList` 方法**：反转给定列表中节点的顺序，直接在原列表上操作。 ```java public void reverseList() { Node p1, p2, p3; if (head == null || head.next == null) return; p1 = head; p2 = p1.n ```