Java中实现链表和双向链表

副标题#e#

链表是一种重要的数据布局，在措施设计中占有很重要的职位。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()要领删除当前结点同时返回其内容，并使其后继结点成为当前结点，假如删除的是最后一个结点，则第一个结点变为当前结点。

#p#副标题#e#

链表类List的源代码如下：

import java.io.*;
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.in.println("You can press return to quit\n");
　　　　 try
　　　　 {
　　　　　 System.in.read();
　　　　　 //确保用户看清措施运行功效---www.bianceng.cn
　　　　 }
　　　　 catch(IOException e)
　　　　 {}
　　　 }
　　 }
　　 class Node
　　 /*组成链表的结点界说*/
　　 {
　　　 Object data;
　　　 Node next;
　　　 Node(Object d)
　　　 {
　　　　 data=d;
　　　　 next=null;
　　　 }
　　 }

读者还可以按照实际需要界说新的要领来对链表举办操纵。双向链表可以用雷同的要领实现只是结点的类增加了一个指向前趋结点的指针。

可以用这样的代码来实现：

#p#分页标题#e#

class Node
{
　 Object data;
　 Node next;
　 Node previous;
　 Node(Object d)
　 {
　　 data=d;
　　 next=null;
　　 previous=null;
　 }
}

虽然，双向链表根基操纵的实现略有差异。链表和双向链表的实现要领，也可以用在仓库和行列的实现中，这里就不再多写了，有乐趣的读者可以将List类的代码稍加窜改即可。