主頁 > 知識庫 > Java語言中鏈表和雙向鏈表

Java語言中鏈表和雙向鏈表

熱門標(biāo)簽:怎樣把地圖標(biāo)注出來 黃石智能營銷電銷機(jī)器人效果 地圖標(biāo)注人員兼職 漯河辦理400電話 騰訊地圖標(biāo)注商戶改名注冊入駐 電話機(jī)器人的特色和創(chuàng)新 淮南騰訊地圖標(biāo)注 開封便宜外呼系統(tǒng)報價 商丘百應(yīng)電話機(jī)器人有沒有效果

  鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu),在程序設(shè)計(jì)中占有很重要的地位。C語言和C++語言中是用指針來實(shí)現(xiàn)鏈表結(jié)構(gòu)的,由于Java語言不提供指針,所以有人認(rèn)為在Java語言中不能實(shí)現(xiàn)鏈表,其實(shí)不然,Java語言比C和C++更容易實(shí)現(xiàn)鏈表結(jié)構(gòu)。Java語言中的對象引用實(shí)際上是一個指針(本文中的指針均為概念上的意義,而非語言提供的數(shù)據(jù)類型),所以我們可以編寫這樣的類來實(shí)現(xiàn)鏈表中的結(jié)點(diǎn)。

  class Node
  {
  Object data;
  Node next;//指向下一個結(jié)點(diǎn)
  }

  將數(shù)據(jù)域定義成Object類是因?yàn)镺bject類是廣義超類,任何類對象都可以給其賦值,增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭,表頭必須包含指向第一個結(jié)點(diǎn)的指針和指向當(dāng)前結(jié)點(diǎn)的指針。為了便于在鏈表尾部增加結(jié)點(diǎn),還可以增加一指向鏈表尾部的指針,另外還可以用一個域來表示鏈表的大小,當(dāng)調(diào)用者想得到鏈表的大小時,不必遍歷整個鏈表。下圖是這種鏈表的示意圖:

  鏈表的數(shù)據(jù)結(jié)構(gòu)

  我們可以用類List來實(shí)現(xiàn)鏈表結(jié)構(gòu),用變量Head、Tail、Length、Pointer來實(shí)現(xiàn)表頭。存儲當(dāng)前結(jié)點(diǎn)的指針時有一定的技巧,Pointer并非存儲指向當(dāng)前結(jié)點(diǎn)的指針,而是存儲指向它的前趨結(jié)點(diǎn)的指針,當(dāng)其值為null時表示當(dāng)前結(jié)點(diǎn)是第一個結(jié)點(diǎn)。那么為什么要這樣做呢?這是因?yàn)楫?dāng)刪除當(dāng)前結(jié)點(diǎn)后仍需保證剩下的結(jié)點(diǎn)構(gòu)成鏈表,如果Pointer指向當(dāng)前結(jié)點(diǎn),則會給操作帶來很大困難。那么如何得到當(dāng)前結(jié)點(diǎn)呢,我們定義了一個方法cursor(),返回值是指向當(dāng)前結(jié)點(diǎn)的指針。類List還定義了一些方法來實(shí)現(xiàn)對鏈表的基本操作,通過運(yùn)用這些基本操作我們可以對鏈表進(jìn)行各種操作。例如reset()方法使第一個結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)。insert(Object d)方法在當(dāng)前結(jié)點(diǎn)前插入一個結(jié)點(diǎn),并使其成為當(dāng)前結(jié)點(diǎn)。remove()方法刪除當(dāng)前結(jié)點(diǎn)同時返回其內(nèi)容,并使其后繼結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn),如果刪除的是最后一個結(jié)點(diǎn),則第一個結(jié)點(diǎn)變?yōu)楫?dāng)前結(jié)點(diǎn)。

  鏈表類List的源代碼如下:

  import java.io.*;
  public class List
  {
  /*用變量來實(shí)現(xiàn)表頭*/
  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()
  /*鏈表復(fù)位,使第一個結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/
  {
  Pointer=null;
  }
  public boolean isEmpty()
  /*判斷鏈表是否為空*/
  {
  return(Length==0);
  }
  public boolean isEnd()
  /*判斷當(dāng)前結(jié)點(diǎn)是否為最后一個結(jié)點(diǎn)*/
  {
  if(Length==0)
   throw new java.lang.NullPointerException();
  else if(Length==1)
   return true;
  else
   return(cursor()==Tail);
  }
  public Object nextNode()
  /*返回當(dāng)前結(jié)點(diǎn)的下一個結(jié)點(diǎn)的值,并使其成為當(dāng)前結(jié)點(diǎn)*/
  {
  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()
  /*返回當(dāng)前結(jié)點(diǎn)的值*/
  {
  Node temp=cursor();
  return temp.data;
  }
  
  public void insert(Object d)
  /*在當(dāng)前結(jié)點(diǎn)前插入一個結(jié)點(diǎn),并使其成為當(dāng)前結(jié)點(diǎn)*/
  {
  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()
  /*將當(dāng)前結(jié)點(diǎn)移出鏈表,下一個結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn),如果移出的結(jié)點(diǎn)是最后一個結(jié)點(diǎn),則第一個結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)*/
  {
  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()
  /*返回當(dāng)前結(jié)點(diǎn)的指針*/
  {
  if(Head==null)
   throw new java.lang.NullPointerException();
  else if(Pointer==null)
   return Head;
  else
   return Pointer.next;
  }
  public static void main(String[] args)
  /*鏈表的簡單應(yīng)用舉例*/
  {
  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();
     //確保用戶看清程序運(yùn)行結(jié)果
    }
    catch(IOException e)
    {}
   }
  }
  class Node
  /*構(gòu)成鏈表的結(jié)點(diǎn)定義*/
  {
   Object data;
   Node next;
   Node(Object d)
   {
    data=d;
    next=null;
   }
  }

  讀者還可以根據(jù)實(shí)際需要定義新的方法來對鏈表進(jìn)行操作。雙向鏈表可以用類似的方法實(shí)現(xiàn)只是結(jié)點(diǎn)的類增加了一個指向前趨結(jié)點(diǎn)的指針。

  可以用這樣的代碼來實(shí)現(xiàn):

  class Node
  {
  Object data;
  Node next;
  Node previous;
  Node(Object d)
  {
  data=d;
  next=null;
  previous=null;
  }
  }

  當(dāng)然,雙向鏈表基本操作的實(shí)現(xiàn)略有不同。鏈表和雙向鏈表的實(shí)現(xiàn)方法,也可以用在堆棧和隊(duì)列的實(shí)現(xiàn)中,這里就不再多寫了,有興趣的讀者可以將List類的代碼稍加改動即可。

您可能感興趣的文章:
  • java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)雙向鏈表的示例
  • Java中雙向鏈表詳解及實(shí)例
  • Java實(shí)現(xiàn)雙向鏈表(兩個版本)
  • java 實(shí)現(xiàn)雙向鏈表實(shí)例詳解
  • JAVA實(shí)現(xiàn)雙向鏈表的增刪功能的方法
  • java中使用雙向鏈表實(shí)現(xiàn)貪吃蛇程序源碼分享
  • java實(shí)現(xiàn)單鏈表、雙向鏈表
  • Java雙向鏈表倒置功能實(shí)現(xiàn)過程解析
  • Java雙向鏈表按照順序添加節(jié)點(diǎn)的方法實(shí)例

標(biāo)簽:亳州 岳陽 武威 紅河 鄭州 拉薩 馬鞍山 大興安嶺

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《Java語言中鏈表和雙向鏈表》,本文關(guān)鍵詞  Java,語,言中,鏈表,和,雙向,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Java語言中鏈表和雙向鏈表》相關(guān)的同類信息!
  • 本頁收集關(guān)于Java語言中鏈表和雙向鏈表的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章