Java链表：原理、操作与示例

### Java 链表：原理、操作与示例 #### 1. 链表基础 链表由一系列 `Link` 对象组成，每个 `Link` 对象包含数据和指向下一个 `Link` 对象的引用（通常称为 `next`）。链表本身有一个字段指向第一个 `Link` 对象。以下是 `Link` 类的部分定义： ```java class Link { public int iData; // data public double dData; // data public Link next; // reference to next link } ``` 这种类定义有时被称为自引用，因为它包含一个与自身类型相同的字段（这里是 `next`）。在实际应用中，`Link` 可能包含更多的数据项，例如人员记录可能包含姓名、地址、社保号码等。也可以使用一个包含这些数据的对象来替代： ```java class Link { public inventoryItem iI; // object holding data public Link next; // reference to next link } ``` #### 2. 引用与基本类型 在链表的上下文中，引用很容易让人混淆。在 Java 中，`Link` 对象的 `next` 字段只是一个引用，而不是另一个 `Link` 对象。引用是一个指向对象的数字，它代表对象在计算机内存中的地址。在给定的计算机/操作系统中，所有引用的大小都是相同的，因此编译器可以轻松确定 `next` 字段的大小。 基本类型（如 `int` 和 `double`）的存储方式与对象不同。基本类型的字段存储的是实际的数值，而不是引用。例如： ```java double salary = 65000.00; ``` 这行代码在内存中创建一个空间，并将数字 `65000.00` 放入该空间。而引用对象的变量定义如下： ```java Link aLink = someLink; ``` 这行代码将 `someLink` 对象的引用放入 `aLink` 中，`someLink` 对象本身位于其他地方。要创建一个对象，必须使用 `new` 关键字： ```java Link someLink = new Link(); ``` 其他语言（如 C++）处理对象的方式与 Java 不同。在 C++ 中，`Link next;` 实际上包含一个 `Link` 类型的对象，不能编写自引用的类定义（虽然可以在 `Link` 类中放置一个指向 `Link` 的指针）。 #### 3. 链表与数组的区别 数组中的每个元素占据一个特定的位置，可以使用索引直接访问。而在链表中，要找到特定元素，必须沿着元素链进行查找。这就像人际关系一样，不能直接访问数据项，必须利用项之间的关系来定位它。 #### 4. LinkList Workshop 小程序 `LinkList Workshop` 小程序提供了三种列表操作：插入新数据项、搜索具有指定键的数据项和删除具有指定键的数据项。这些操作适用于通用数据库应用程序。 - **插入按钮**：按下 `Ins` 按钮，会提示输入一个 0 到 999 之间的键值。后续按下该按钮将生成一个包含此数据的链接。新链接总是插入到列表的开头。 - **查找按钮**：按下 `Find` 按钮，输入现有链接的键值，红色箭头将沿着列表移动查找该链接。如果找到，会给出提示；如果输入不存在的键值，箭头将搜索到列表末尾并报告未找到。 - **删除按钮**：按下 `Del` 按钮，输入现有链接的键值，箭头将沿着列表移动查找该链接。找到后，将移除该链接，并将前一个链接的引用指向后续链接。 #### 5. 简单链表示例 `linkList.java` 程序演示了一个简单的链表，该链表只允许以下操作： - 在列表开头插入项 - 删除列表开头的项 - 遍历列表以显示其内容 ##### 5.1 Link 类 ```java class Link { public int iData; // data item public double dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(int id, double dd) // constructor { iData = id; // initialize data dData = dd; // (‘next’ is automatically } // set to null) // ------------------------------------------------------------- public void displayLink() // display ourself { System.out.print("{" + iData + ", " + dData + "} "); } } // end class Link ``` `Link` 类包含数据项、构造函数和一个显示链接数据的方法 `displayLink()`。构造函数初始化数据，`next` 字段会自动设置为 `null`。 ##### 5.2 LinkList 类 ```java class LinkList { private Link first; // ref to first link on list // ------------------------------------------------------------- public LinkList() // constructor { first = null; // no items on list yet } // ------------------------------------------------------------- public boolean isEmpty() // true if list is empty { return (first==null); } // ------------------------------------------------------------- // insert at start of list public void insertFirst(int id, double dd) { // make new link Link newLink = new Link(id, dd); newLink.next = first; // newLink --> old first first = newLink; // first --> newLink } // ------------------------------------------------------------- public Link deleteFirst() // delete first item { // (assumes list not empty) Link temp = first; // save reference to link first = first.next; // delete it: first-->old next return temp; // return deleted link } // --------------------------------------- ```