链表java源代码 java 链表使用

java 中如何实现链表操作？

class Node {

创新互联从2013年成立，先为榕江等服务建站，榕江等地企业，进行企业商务咨询服务。为榕江企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

Object data;

Node next;//申明类Node类的对象叫Next

public Node(Object data) { //类Node的构造函数

setData(data);

}

public void setData(Object data) {

this.data = data;

}

public Object getData() {

return data;

}

}

class Link {

Node head;//申明一个Node类的一个对象 head

int size = 0;

public void add(Object data) {

Node n = new Node(data); //调用Node类的构造函数

链表是一种重要的数据结构，在程序设计中占有很重要的地位。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的源代码如下：

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();

//确保用户看清程序运行结果

}

catch(IOException e)

{}

}

}

class Node

/*构成链表的结点定义*/

{

Object data;

Node next;

Node(Object d)

{

data=d;

next=null;

}

}

读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用

类似的方法实现只是结点的类增加了一个指向前趋结点的指针。

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

class Node

{

Object data;

Node next;

Node previous;

Node(Object d)

{

data=d;

next=null;

previous=null;

}

}

当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也

可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类

的代码稍加改动即可。

用Java语言实现单向链表

1.先定义一个节点类

package com.buren;

public class IntNode {

//定义一个节点类

int

info;

//定义属性，节点中的值

IntNode next;

//定义指向下一个节点的属性

public IntNode(int

i){ //构造一个next为空的节点

this(i,null);

}

public IntNode(int i,IntNode

n){ //构造值为i指向n的节点

info=i;

next=n;

}

}

2.再定义一个链表类，这是主要部分

package com.buren;

public class IntSLList {

private IntNode head,tail;

//定义指向头结点和尾结点的指针，

//如果大家看着这个不像指针的话，那就需要对指针有更深刻的了解

public

IntSLList(){

//定义一个空节点

head=tail=null;

}

public boolean

isEmpty(){

//判断节点是否为空

return

head==null;

//这行代码看起来似乎很神奇，其实真的很神奇，偶是服了

}

public void addToHead(int el){

//将el插入到头结点前

head=new

IntNode(el,head);

//将节点插入到头结点前，作为新的投节点

if(head==tail){

//给空链表插入节点时

tail=head;

//头结点和尾结点指向同一个节点

}

}

public void addToTail(int

el){

//向链表的尾部增加结点

if(!isEmpty()){

//判断链表是否为空

tail.next=new

IntNode(el);

//新建立一个值为el的节点，将链表的尾结点指向新节点

tail=tail.next;

//更新尾指针的指向

}else{

head=tail=new

IntNode(el);

//如果链表为空，新建立一个节点，将头尾指针同时指向这个节点

}

}

public int

deleteFromHead(){

//删除头结点，将节点信息返回

int

el=head.info;

//取出节点信息

if(head==tail){

//如果链表中只有一个节点

head=tail=null;

//删除这一个节点

}else{

head=head.next;

//如果链表中不止一个节点，将头结点的胡敬下一个节点作为头结点

}

return

el;

//返回原头结点的值

}

public int

deleteFromTail(){

//删除尾结点，返回尾结点的信息

int

el=tail.info;

//取出尾结点的值

if(head==tail){

// 如果链表中只有一个节点

head=tail=null;

//删除这个节点

}else{

IntNode

temp;

//定义中间变量

for(temp=head;temp.next!=tail;temp=temp.next);

//找出尾结点的前一个节点，注意最后的分号，

//这个for循环是没有循环体的，目渗枣的在于找出尾结点的前一个节点

//在整个程序中用了很多次这样的写裤喊慎法，相当经典啊

tail=temp;

//将找出来的节点作为尾结点，删除原来的尾结点

tail.next=null;

//将新尾结点的指向设为空

}

return

el;

//返回原尾结点的信息

}

public void

printAll(){

//打印链表中所有节点的信息

if(isEmpty()){

//如果链表为空

System.out.println("This

list is

empty!");

//输出提示信息

return;

//返回到调用的地方

}

if(head==tail){

//当链表中只有一个节点时

System.out.println(head.info);

//输出这个节点的信息，就是头结点的信息

return;

}

IntNode

temp;

//定义一个中间变量

for(temp=head;temp!=null;temp=temp.next){

//遍历整个链表

System.out.print(temp.info+"

");

//输出每个节点的信息

}

System.out.println();

//输出一个换行，可以没有这一行

}

public boolean isInList(int

el){

//判断el是否存在于链表中

IntNode

temp;

//定义一个中间变量

for(temp=head;temp!=null

temp.info!=el;temp=temp.next);

//将el找出来，注意最后的分

return

temp!=null;

// 如果存在返回true，否则返回flase，这两行代码很有思想

}

public void delete(int

el){

//删除链表中值为el的节点

if(head.info==el

head==tail){

//如果只有一个节点，并且节点的值为el

head=tail=null;

//删除这个节点

}else

if(head.info==el){

// 不止一个节点，而头结点的值就是el

head=head.next;

//删除头结点

}else{

IntNode

pred,temp;

//定义两个中间变量

for(pred=head,temp=head.next;temp.info!=el

temp.next!=null;pred=pred.next,temp=temp.next);

//跟上面的类似，自己琢磨吧，也是要注意最后的分号

pred.next=temp.next;

//将temp指向的节点删除，最好画一个链表的图，有助于理解

if(temp==tail){

//如果temp指向的节点是尾结点

tail=pred;

//将pred指向的节点设为尾结点，

}

}

}

//下面这个方法是在链表中值为el1的节点前面插入一个值为el2的节点，

//用类似的思想可以再写一个在链表中值为el1的节点后面插入一个值为el2的节点

public boolean insertToList(int el1,int

el2){

//定义一个插入节点的方法，插入成功返回true，否则返回false

IntNode

pred,temp; //定义两个中间变量

if(isEmpty()){

//判断链表是否为空

return

false;

//如果链表为空就直接返回false

}

if(head.info==el1

head==tail){

//如果链表中只有一个节点，并且这个节点的值是el1

head=new

IntNode(el2,head);

//新建立一个节点

return

true;

}else if(head.info==el1){

IntNode t=new

IntNode(el2);

t.next=head;

head=t;

return

true;

}else{

for(pred=head,temp=head.next;temp!=null

temp.info!=el1;pred=pred.next,temp=temp.next);

if(temp!=null){

IntNode

a=new IntNode(el2);

pred.next=a;

a.next=temp;

return

true;

}else{

System.out.println(el1+"

NOT EXEISTS!");

return

false;

}

}

}

3.下面是测试代码

public static void main(String[] args){

IntSLList test=new

IntSLList();

//test.addToHead(7);

test.addToTail(7);

System.out.println(test.insertToList(7,5));

test.printAll();

System.out.println(test.isInList(123));

}

}

Java语言没有指针，怎样实现链表?

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;

}

}

当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的现实中。