链表是一种重要的数据结构,在程序设计中占有很重要的地位。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 "); System.in.println("You can press return to quit"); 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实现链表_双向链表
本篇文章主要介绍了JAVA实现双向链表的增删功能的方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
主要介绍了java 实现双向链表实例详解的相关资料,需要的朋友可以参考下
通过java实现的双向链表,及反转功能,可能对面试有用哦
操作包括: 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
使用 Eclipse、Maven、JUnit、SonarQube 和 JaCoCo 使用 Java 实现双向链表。 嵌套类摘要 private class DLNode 现场总结 - DLNode<T> first - DLNode<T> last 构造函数总结 + DLList() 方法总结 + boolean ...
Java 有序 非循环 双向 链表 算法 实例
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
使用java语言实现双向链表,提供测试用例说明功能
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
自定义的双向链表 博文链接:https://hiliangliang1130-126-com.iteye.com/blog/1144023
JAVA实现链表,双向链表.pdf
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
双端链表和双向链表Java代码
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
已知N个人(以编号1,2,3...n分别表示)围成一个圈。 从编号为K的人开始报数,数到M的那个人出列,他的下一个人又从1开始报数,依照此规律重复下去,直到圆圈中的人全部出列。 问题:请打印出这N个的...双向链表实现的