精华内容
下载资源
问答
  • 双向链表的实现

    2017-12-20 18:56:33
    双向链表的实现,程序完全可以运行,帮助大家学习和交流
  • JAVA基础:语言中链表和双向链表的实现(转)[@more@]链表是一种重要的数据结构,在程序设计中占有很重要的地位。C语言和C++语言中是用指针来实现链表结构的,由于JAVA语言不提供指针,所以有人认为在JAVA语言中不能...

    JAVA基础:语言中链表和双向链表的实现(转)[@more@]链表是一种重要的数据结构,在程序设计中占有很重要的地位。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 );

    }

    来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10617542/viewspace-959762/,如需转载,请注明出处,否则将追究法律责任。

    展开全文
  • java学习经验总结------双向链表的实现双向链表的建立与单链表类似,只是需要使用pre指针指向前一个结点,并且在删除添加时不仅仅考虑nextpackage datastructure;public class DoubleLinkedList {//双向链表的构造...

    java学习经验总结------双向链表的实现

    双向链表的建立与单链表类似,只是需要使用pre指针指向前一个结点,并且在删除添加时不仅仅考虑next

    package datastructure;

    public class DoubleLinkedList {//双向链表的构造使用

    public static void main(String[] args) {

    // TODO 自动生成的方法存根

    DoubleList dl = new DoubleList();

    dl.empty_add("5");

    dl.empty_add("3");

    dl.empty_add("2");

    dl.empty_add("1");

    dl.insert(2, "8");

    dl.orderprint();

    dl.reverseorderprint();

    }

    }

    class DoubleList{

    public Dlnode first;//头指针

    public Dlnode current;//当前结点

    private int count=0;//结点个数

    public DoubleList() {

    // TODO 自动生成的构造函数存根

    this.first=new Dlnode(null);

    current=first;

    first.next=null;

    }

    public int getCount() {//得到结点个数

    return count;

    }

    public void empty_add(String word) {//由空链表添加结点

    Dlnode newnode = new Dlnode(word);

    //current=first;

    while(current.next!=null)

    current=current.next;

    current.next=newnode;

    newnode.pre=current;

    newnode.next=null;

    current=current.next;

    this.count++;

    }

    public void orderprint() {//按照顺序遍历

    Dlnode now;

    for(now=first.next;now!=null;now=now.next)

    System.out.print(now.getWord());

    if(now==null)

    System.out.println("null");

    System.out.println("结点个数为:"+this.getCount());

    /*System.out.println(current.getWord());*/

    }

    public void reverseorderprint() {//按照逆序遍历

    while(current!=null)

    {

    System.out.print(current.getWord());

    current=current.pre;

    }

    System.out.println("结点个数为:"+this.getCount());

    }

    public void insert(int location,String word) {//在指定地点插入

    if(location>count)

    System.out.println("已超过结点个数,无法插入!!!");

    else {

    Dlnode now=first;

    while(true) {

    if(location==0)

    break;

    else {

    now=now.next;

    location--;

    }

    }

    Dlnode temp = new Dlnode(word);

    now.pre.next=temp;

    temp.pre=now.pre;

    now.pre=temp;

    temp.next=now;

    this.count++;

    }

    }

    /*public void delete(int location) {//删除功能留置,与添加类似

    if(location>count)

    }*/

    }

    class Dlnode{//链表结点

    private String word;

    public Dlnode pre;

    public Dlnode next;

    public Dlnode(String word) {

    // TODO 自动生成的构造函数存根

    this.word=word;

    }

    public String getWord() {

    return word;

    }

    public void setWord(String word) {

    this.word = word;

    }

    }

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,475
精华内容 4,990
关键字:

双向链表的实现