（九）链表—单链表

一、链表说明：

1. 链表是继数组之后的又一个使用很广泛的数据结构。链表包括有单链表、双端链表、有序链表、双向链表和有迭代器的链表等。

2. 在链表中，每个数据项在“链结点”（Link）中。每个Link对象都包含一个对下一个链结点的引用字段（通常叫做next），链表本身有一个字段指向对第一个链结点的引用。链表的结构如图所示：

二、单链表的操作：

1. 单链表包含的操作：在链表头插入一个数据项；在链表头删除一个数据项；遍历链表显示他的内容。

三、Java语言描述单链表：

package com.solid.link;

public class Link {

//链结点的引用

Link next;

//链表中存放的数据

int iDate;

/**

* 构造方法

* @param iDate

*/

public Link(int iDate) {

this.iDate = iDate;

}

/**

* 显示链结点元素

*/

public void display() {

System.out.print("{" + iDate + "}");

}

}

package com.solid.link;

public class LinkList {

//对第一个链结点的引用

Link first;

/**

* 链表的构造方法

*/

public LinkList() {

first = null;

}

/**

* 链表首部插入一个元素

* @param iDate

*/

public void insertFirst(int iDate) {

Link link = new Link(iDate);

link.next = first;

first = link;

}

/**

* 删除链表首部元素

* @return

*/

public Link deleteFirst() {

Link temp = first;

first = first.next;

return temp;

}

/**

* 显示某个链表的所有元素

*/

public void display() {

Link current = first;

while(!(current==null)) {

current.display();

current = current.next;

}

System.out.println();

}

/**

* 查找链表中某个特定的元素

* @param key

* @return

*/

public Link find(int key) {

Link current = first;

while(current.iDate != key) {

if(current.next == null) {

return null;

}

current = current.next;

}

return current;

}

/**

* 删除链表中某个特定的元素

* @param key

* @return

*/

public Link delete(int key) {

Link current = first;

Link previous = first;

while(current.iDate != key) {

if(current.next == null) {

return null;

} else {

previous = current;

current = current.next;

}

}

if(current == first) {

first = first.next;

} else {

previous.next = current.next;

}

return current;

}

}