链表是一种重要的数据结构，在程序设计中占有很重要的地位。c语言和c＋＋语言中是用指针来实现链表结构的，由于java语言不提供指针，所以有人认为在java语言中不能实现链表，其实不然，java语言比c和c＋＋更容易实现链表结构。java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
程序代码：
class node
{
object data;
node next;//指向下一个结点
}
|
将数据域定义成object类是因为object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
链表的数据结构
我们可以用类list来实现链表结构，用变量head、tail、length、pointer来实现表头。存储当前结点的指针时有一定的技巧，pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类list还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类list的源代码如下：
package cn.javatx;
import java.io.ioexception;
/**
* @author ljfan
*
*/
public class list {
private node head = null;
private node tail = null;
private node pointer = null;
private int length = 0;
public void deleteall() {
head = null;
tail = null;
pointer = null;
length = 0;
}
public void reset() {
pointer = null;
}
public boolean isempty() {
return (length == 0);
}
public boolean isend() {
if (length == 0)
throw new java.lang.nullpointerexception();
else if (length == 1)
return true;
else
return (cursor() == tail);
}
public object nextnode() {
if (length == 1)
throw new java.util.nosuchelementexception();
else if (length == 0)
throw new java.lang.nullpointerexception();
else {
node temp = cursor();
pointer = temp;
if (temp != tail)
return (temp.next.data);
else
throw new java.util.nosuchelementexception();
}
}
public object currentnode() {
node temp = cursor();
return temp.data;
}
public void insert(object d) {
node e = new node(d);
if (length == 0) {
tail = e;
head = e;
} else {
node temp = cursor();
e.next = temp;
if (pointer == null)
head = e;
else
pointer.next = e;
}
length++;
}
public int size() {
return (length);
}
public object remove() {
object temp;
if (length == 0)
throw new java.util.nosuchelementexception();
else if (length == 1) {
temp = head.data;
deleteall();
} else {
node cur = cursor();
temp = cur.data;
if (cur == head)
head = cur.next;
else if (cur == tail) {
pointer.next = null;
tail = pointer;
reset();
} else
pointer.next = cur.next;
length--;
}
return temp;
}
private node cursor() {
if (head == null)
throw new java.lang.nullpointerexception();
else if (pointer == null)
return head;
else
return pointer.next;
}
public static void main(string[] args) {
list a = new list();
for (int i = 1; i <= 10; i++)
a.insert(new integer(i));
system.out.println(a.currentnode());
while (!a.isend())
system.out.println(a.nextnode());
a.reset();
while (!a.isend()) {
a.remove();
}
a.remove();
a.reset();
if (a.isempty())
system.out.println("there is no node in list n");
system.out.println("you can press return to quitn");
try {
system.in.read();
} catch (ioexception e) {
}
}
}
class node {
object data;
node next;
node(object d) {
data = d;
next = null;
}
}
|
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将list类的代码稍加改动即可。
闽公网安备 35060202000074号