- 浏览: 191156 次
- 性别:
- 来自: 厦门
文章分类
最新评论
-
行者买刀:
qxpidt 写道楼主,我想问下,嵌套这些WEB应用后,如何操 ...
JDIC一个能够用java调用ie内核的包 -
qxpidt:
楼主,我想问下,嵌套这些WEB应用后,如何操作你登录的COOK ...
JDIC一个能够用java调用ie内核的包 -
lookforwarding:
...
java重写JSplitPane的UI,设置分隔条的颜色 -
v韧竹v:
最后那个抽象工厂模式,CarType是不是定义错了,应该abs ...
设计模式之略见一斑(工厂模式Factory) -
l7810:
这与模板模式有什么区别啊?
设计模式之略见一斑(建造模式builder)
链表是一种重要的数据结构,在程序设计中占有很重要的地位。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语言中不能实现链
表,其实不然,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》 孙淑玲、王太权、陈意云
发表评论
-
UtilCommon
2016-08-16 07:23 0aaaaaa -
Java面试题全集(上)
2016-08-14 17:23 0版权声明:本文为博 ... -
设计模式之略见一斑(Visitor访问者模式)
2010-02-25 15:02 3189在开发中,我们可能会经常碰到客户提了一新的需求,那么在现 ... -
设计模式之略见一斑(Mediator中介者模式)
2010-02-25 10:07 1843设计模式 写道 通常,面向对象的软件开发要求尽可能 ... -
设计模式之略见一斑(Chain of Responsibility责任链模式)
2010-02-24 15:00 1461设计模式 写道 面向对 ... -
设计模式之略见一斑(Observer观察者模式)
2010-02-23 17:15 2174用户通常通过调用对象的方法来收集该对象的信息。但是当这 ... -
设计模式之略见一斑(Memento备忘录模式)
2010-02-23 11:46 1433有时候,我们需要 ... -
设计模式之略见一斑(Template Method模板方法模式)
2010-02-22 21:33 1409模板方法模式就是预 ... -
设计模式之略见一斑(策略模式strategy)
2010-02-22 17:56 1934java设计模式 写道 ... -
设计模式之略见一斑(状态模式State)
2010-02-22 15:42 1647设计模式中的状态模式相对比较简单,简单的说就是对某 ... -
设计模式之略见一斑(解释器模式Interpreter)
2010-02-22 10:27 3330解释器模式是 ... -
设计模式之略见一斑(命令模式Command)
2010-02-22 09:49 1519终于把构造模式的几种设计模式写完,接下来开始写的行为模 ... -
设计模式之略见一斑(享元模式flyweight)
2010-02-10 11:39 1402flyweight模式中文解释为轻量极模式,所以顾名 ... -
设计模式之略见一斑(代理模式Proxy)
2010-02-10 11:04 1914普通对象所需要完成的任务就是通过公共接口为外界提供自己所承诺的 ... -
设计模式之略见一斑(装饰模式decorator)
2010-02-09 11:08 1776标头:(引自设计模式 ... -
设计模式之略见一斑(组合模式Composite)
2010-02-08 14:45 1468定义: 将对象以树形结构组织起来,以达成"部 ... -
设计模式之略见一斑(外观模式Facade)
2010-02-07 09:30 1348外观模式又称门面模式,它是为了给子系统中提供一个一致的界面,从 ... -
设计模式之略见一斑(桥梁模式bridge)
2010-02-06 18:04 1518桥梁模式的宗旨就是将 ... -
设计模式之略见一斑(适配器模式Adapter)
2010-02-03 10:39 1569适配器模式就是基于客户提供的接口和功能,再此基础上实 ... -
设计模式之略见一斑(原型模式Prototype)
2010-02-01 17:15 1654原型模式允许一个对象 ...
相关推荐
2022年Java语言中链表和双向链表Java教程.docx
JAVA实现链表_双向链表
操作包括: 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
双端链表和双向链表Java代码
通过java实现的双向链表,及反转功能,可能对面试有用哦
用java实现双向链表的完整操作,主要用到内部类实现。
JAVA实现链表,双向链表.pdf
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点。 class Node { Object data; Node next;//指向下一个结点 } 将数据...
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
Java 有序 非循环 双向 链表 算法 实例
数据结构-链表 JAVA语言实现,包含单向链表、双向链表、循环链表的遍历、删除和插入 详细介绍:http://blog.csdn.net/z740852294/article/details/77369439
自定义的双向链表 博文链接:https://hiliangliang1130-126-com.iteye.com/blog/1144023
主要介绍了Java实现双向链表(两个版本)的相关资料,需要的朋友可以参考下
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
二叉树转换为双向链表 通过随机创建二叉排序树测试二叉树转换为双向链表是否正确 http://blog.csdn.net/ssuchange/article/details/17383625
使用java语言实现双向链表,提供测试用例说明功能
已知N个人(以编号1,2,3...n分别表示)围成一个圈。 从编号为K的人开始报数,数到M的那个人出列,他的下一个人又从1开始报数,依照此规律重复下去,直到圆圈中的人全部出列。 问题:请打印出这N个的...双向链表实现的
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。