`
行者买刀
  • 浏览: 194599 次
  • 性别: Icon_minigender_1
  • 来自: 厦门
社区版块
存档分类
最新评论

JAVA 语言中链表和双向链表的实现(转)

    博客分类:
  • J2SE
阅读更多
链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指
针来实现链表结构的,由于JAVA语言不提供指针,所以有人认为在JAVA语言中不能实现链
表,其实不然,JAVA语言比C和C++更容易实现链表结构。JAVA语言中的对象引用实际上是
一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以
编写这样的类来实现链表中的结点。

class Node

{

Object data;

Node next; // 指向下一个结点

}

   将数据域定义成Object类是因为Object类是广义超类(所有类的祖先),任何类对象
都可以给其赋值,增加了代码的通用性。为了使链表可以被访问还需要定义一个表头,表
头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点
,还可以增加一指向链表尾部的指针,另外还可以用一个域来表示链表的大小,当调用者
想得到链表的大小时,不必遍历整个链表,下图是这种链表的示意图。

 

图一 链表的数据结构

 

我们可以用类List来实现链表结构,用变量Head、Tail、Length、Pointer来实现表头。存
储当前结点的指针时有一定的技巧,Pointer并非存储指向当前结点的指针,而是存储指向
它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么我们为什么要这样
做呢?这是因为当我们删除当前结点后仍需保证剩下的结点构成链表,如果Pointer指向当
前结点,则会给操作带来很大困难。那么如何得到当前结点呢,我们定义了一个方法curso
r(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作,
通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为
当前结点。insert( Object d )方法在当前结点前插入一个结点,并使其成为当前结点。r
emove()方法删除当前结点同时返回其内容,并使其后继结点成为当前结点,如果删除的是
最后一个结点,则第一个结点变为当前结点。

链表类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》 孙淑玲、王太权、陈意云 
分享到:
评论

相关推荐

    java 单链表和双向链表的实现

    本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...

    2022年Java语言中链表和双向链表Java教程.docx

    《2022年Java语言中链表和双向链表Java教程》 链表作为一种基础且重要的数据结构,广泛应用于编程领域,特别是在Java语言中。虽然Java不直接提供指针,但通过对象引用,我们可以轻松地实现链表的构建。在Java中,...

    JAVA实现链表_双向链表

    JAVA实现链表_双向链表

    双端链表和双向链表Java代码

    在Java中,理解和实现双端链表和双向链表对于提升数据结构和算法能力至关重要,它们在很多实际场景中都有应用,如在集合框架(如LinkedList)、缓存系统、以及需要频繁进行插入和删除操作的场合。理解这两种链表的...

    Java实现双向链表

    用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。

    JAVA双向链表反转实现

    与单向链表不同,双向链表中的每个节点都有两个指针,一个指向前一个节点,另一个指向后一个节点。这使得在链表中的导航更加灵活,对于某些特定的操作,比如反转链表,提供了更高效的解决方案。 双向链表的节点通常...

    java实现的单向链表和双向链表

    本篇将深入探讨由Java实现的单向链表和双向链表。 首先,我们来理解单向链表。单向链表中的每个节点包含两部分:数据域(存储实际数据)和指针域(存储指向下一个节点的引用)。这种结构使得链表只能向前遍历,不能...

    单链表双向链表java实现

    在这个话题中,我们将深入探讨两种基本的线性数据结构——单链表和双向链表,并通过Java语言来实现它们。 单链表是一种线性数据结构,其中每个元素(称为节点)包含两个部分:数据域和指针域。数据域存储实际的数据...

    Java双向链表的实现

    在Java编程中,双向链表是一种非常重要的数据结构,它允许我们在列表的任何位置高效地进行插入和删除操作。与单向链表不同,双向链表的每个节点不仅包含指向下一个节点的指针,还包含一个指向前一个节点的指针。这...

    java 数据结构 链表

    在Java中,链表主要分为两种类型:单向链表和双向链表。单向链表的每个节点只能指向下一个节点,而双向链表的节点则可以同时指向前后两个节点,提供了更灵活的遍历方式。 1. 单向链表: - 单向链表的节点定义:...

    用java实现双向链表操作

    用java实现双向链表的完整操作,主要用到内部类实现。

    Java有序非循环双向链表算法实例

    在"PersonToFile"这个例子中,可能包含一系列具有姓名、年龄等属性的Person对象,需要将这些对象存储在有序非循环双向链表中。可以实现一个根据年龄排序的插入方法,每次插入新的Person时,都将其正确地插入到链表的...

    Java算法实例-双向链表操作

    双向链表与单链表相比,其独特之处在于每个节点不仅包含指向下一个节点的指针,还包含指向前一个节点的指针,这使得在链表中的前进和后退操作变得相对高效。 双向链表的操作主要包括创建、插入、删除、遍历等。下面...

    Java语言中链表和双向链表

    Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。 class Node { Object data; Node next;//指向下一个结点 } 将数据...

    JAVA实现链表,双向链表.pdf

    与单向链表相比,双向链表的每个节点多了一个指向前一个节点的指针,因此在双向链表中可以向前或向后遍历,这样为某些操作带来了便利。 #### 三、链表操作方法 在文件描述中,我们看到了几个关键的链表操作方法的...

    双向链表(java实现)

    在Java中实现双向链表,我们通常会创建一个表示链表节点的类(如`Node`),以及一个表示链表本身的类(如`MyLinkedList`)。`Node`类包含数据和两个引用,分别用于指向前一个节点和后一个节点。`MyLinkedList`类则...

    数组、单链表和双链表介绍以及双向链表的CC++Java实现 数组和链表.pdf

    数组、单链表和双链表介绍以及双向链表的C、C++和Java实现 在计算机科学中,数组、单链表和双链表是...双向链表的实现可以使用C、C++和Java三种语言,它们的实现方式也有所不同,但是它们都可以实现双链表的基本操作。

    Java语言编写的数据结构-链表实现

    这种设计允许我们在链表中前后移动更加灵活,增加了插入和删除操作的效率,但同时也增加了存储需求和实现复杂性。在Java中,双链表的Node类需要添加一个previous字段来保存前驱节点的引用。 实现这些链表数据结构时...

Global site tag (gtag.js) - Google Analytics