当前位置: 代码迷 >> Java相关 >> 用JAVA实现双链表
  详细解决方案

用JAVA实现双链表

热度:469   发布时间:2007-06-02 16:11:34.0
用JAVA实现双链表

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编辑过]

搜索更多相关的解决方案: 结点  JAVA  双链  Pointer  指针  

----------------解决方案--------------------------------------------------------
回复:(野蛮女人)用JAVA实现双链表
[CODE]

class Node {
/* 构成链表的结点定义 */
Object data;

Node next;

Node(Object d) {
data = d;
next = null;
}
}[/CODE]

这叫双向链表么??

----------------解决方案--------------------------------------------------------
呵呵,这东西当作学数据结构时练练手就OK了,实际用时直接用java.util.LinkedList类吧,这个类是真正的双向链表,而且一般来说不会比你自己的差.
----------------解决方案--------------------------------------------------------
不好意思写错了 是单的
----------------解决方案--------------------------------------------------------
  相关解决方案