當前位置:首頁 » 編程語言 » java有鏈表嗎

java有鏈表嗎

發布時間: 2022-08-09 17:21:51

java如何實現鏈表

鏈表是一種重要的數據結構,在程序設計中佔有很重要的地位。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 \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中Hash底層中的數組保存的一張鏈表嗎

Hash沒有底層,它是演算法。你說的是HashMap吧。這個要看Java版本。
Java7的HashMap底層是數組保存的鏈表。
Java8後面對HashMap做了優化,數組保存的鏈表長度為8,鏈表轉為紅黑樹。紅黑樹只有6個元素時,又會轉回鏈表。

③ java 鏈表

class Node {
Object data;
Node next;//申明類Node類的對象叫Next

public Node(Object data) { //類Node的構造函數
setData(data);
}
public void setData(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
}

class Link {
Node head;//申明一個Node類的一個對象 head
int size = 0;

public void add(Object data) {
Node n = new Node(data); //調用Node類的構造函數

鏈表是一種重要的數據結構,在程序設計中佔有很重要的地位。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 \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中數組與鏈表有什麼區別

一、主體不同

1、數組:是有序的元素序列。將有限個類型相同的變數的集合命名。

2、鏈表:是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。


二、組成不同

1、數組:是在程序設計中,為了處理方便, 把具有相同類型的若干元素按無序的形式組織起來的一種形式。

2、鏈表:由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態生成。

三、特點不同

1、數組:所有元素都具有相同類型。數組中的元素存儲在一個連續性的內存塊中,並通過索引來訪問。

2、鏈表:可以克服數組鏈表需要預先知道數據大小的缺點,鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。


⑤ java 有循環鏈表嗎

網頁鏈接

java可以實現鏈表的,不管是單鏈表、雙鏈表還是循環鏈表。

⑥ 鏈表在c++或java中有嗎

鏈表
分為
動態鏈表

靜態鏈表
,動態鏈表要藉助指針來實現。C++有指針,所以兩種鏈表都能實現,但JAVA只能實現靜態鏈表

⑦ 在java中可以用鏈表么

可以.如果你翻開 java語言程序設計 (進階版) 就會看到 第24章講的就是

⑧ Java鏈表

鏈表是一種重要的數據結構,在程序設計中佔有很重要的地位。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 \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類的代碼稍加改動即可。

如果對您有幫助,請記得採納為滿意答案,謝謝!祝您生活愉快!

vaela

⑨ Java中的鏈表

鏈表就好比我們手錶或者手鏈,沒有開頭和結尾,到處都可以插入和去除,所以增刪速度快查詢速度慢,更多java知識可以來群,前面是二九六,中間是五九一,最後是二九零。

⑩ java怎麼用鏈表實現

在數據結構中經常看見的一個基本概念-鏈表。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態生成。每個結點包括兩個部分:一個是存儲數據元素的數據域,另一個是存儲下一個結點地址的指針域。
在Java中,對於鏈表的實現都是基於引用數據類型操作的。實現大致如下:
定義節點類Node,節點的概念很重要,一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用,再增加一個添加節點的方法即可完成鏈表實現。
鏈表有很多種不同的類型:單向鏈表,雙向鏈表以及循環鏈表。在執行效率上,相比數組而言,鏈表插入快查找慢,開發中得根據實際業務使用。

熱點內容
如何用密碼鎖住並隱藏工作表 發布:2024-03-29 07:03:28 瀏覽:326
按鍵精靈滑鼠腳本 發布:2024-03-29 06:47:41 瀏覽:19
pythonhome 發布:2024-03-29 06:47:36 瀏覽:169
dns配置錯誤怎麼修理 發布:2024-03-29 06:36:15 瀏覽:980
電信客戶6位密碼是什麼 發布:2024-03-29 06:35:42 瀏覽:565
b星演算法找門 發布:2024-03-29 06:27:13 瀏覽:774
小數化分數c語言 發布:2024-03-29 06:20:16 瀏覽:561
如何搭建ai伺服器 發布:2024-03-29 06:20:10 瀏覽:493
用低配置手機玩游戲掉幀怎麼辦 發布:2024-03-29 06:20:06 瀏覽:588
安卓系統的微信如何安裝 發布:2024-03-29 05:48:45 瀏覽:993