package core;
/*
* 我们可以用类ListLinked来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。
* 存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,
* 当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？
* 这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。
* 那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。
* 类ListLinked还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。
* 例如reset()方法使第一个结点成为当前结点。
* insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。
* remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，
* 如果删除的是最后一个结点，则第一个结点变为当前结点。
*/
public class ListLinked {
/* 用变量来实现表头 */
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)
/* 链表的简单应用举例 */
{
ListLinked a = new ListLinked();
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");
}
}
class Node {
/* 构成链表的结点定义 */
Object data;
Node next;
Node(Object d) {
data = d;
next = null;
}
}
[此贴子已经被作者于2007-6-2 17:03:50编辑过]
