當前位置:首頁 » 編程語言 » java鏈表遍歷

java鏈表遍歷

發布時間: 2022-09-27 01:33:38

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寫的:輸入N個整數,按照輸入的順序建立單鏈表存儲,並遍歷所建立的單鏈表,輸出這些數據。

importjava.util.Scanner;


publicclassNode{
publicintvalue;
publicNodenext;

publicNode(intvalue){
this.value=value;
this.next=null;
}

publicvoidadd(Nodenode){
this.next=node;
}

publicbooleanhasNext(){
returnthis.next==null?false:true;
}

publicstaticvoidmain(String[]args){
Nodefirst=null;//記錄第一個節點,在後面遍歷的時候使用
Nodenode=null;//保存當前輸入的節點使用

Scannerin=newScanner(System.in);//用於控制台輸入,Ctrk+Z結束輸入
while(in.hasNext()){
intv=in.nextInt();
Noden=newNode(v);
if(first==null){
first=n;
node=n;
}else{
node.add(n);
node=n;
}
}

if(first==null){
System.out.println("沒有數字輸入");
}else{
node=first;
System.out.println(node.value+"");
while(node.hasNext()){
node=node.next;
System.out.println(node.value+"");
}
}
}
}

模擬最簡單的單鏈表,臨時手打,僅供做題等參考,望採納。

❸ Java:遍歷時數組和鏈表哪個效率高呢

這個還真有可能,數組是根據基地址和偏移量來算出地址(有乘法和加法運算),然後訪問。鏈接表呢,如:p = p->next;然後用*p訪問。按這個說的話,它就一個賦值語句。所以有可能。其實嘛,這個你可以寫個演算法測一下就好了嘛,不用非得要答案。自己動手寫下證明一下就好了。

❹ 有一個單項鏈表,從第一個節點開始遍歷,只允許遍歷一遍,用Java程序實現倒序列印所有節點

// 需要藉助一個容器
String[] cont = new String[list.size()];
Iterator ite = list.iterator();
int j = list.size() - 1;
while(ite.hasNext() && j > -1){
cont[j] = ite.next();
j--;
}
for(String str: cont){
log.info(str);
}

❺ java單鏈表遍歷,最後會輸出一個0,這個零是什麼,頭指針的引用嗎

0是鏈表最後一個節點的值,也就是你第一個addFirst()時的first的值

❻ 關於java鏈表的問題,鏈表的創建,遍歷

1. position.link 當前指向節點的下一個節點地址
2. new ListNode(newData, position.link); 下一個節點地址給了新數據,也就是說,將新數據裡面存得下一個節點的地址改成當前節點的下一個節點地址。
3. position.link = new什麼什麼 新數據的地址給了當前地址的記錄下一個節點地址變數。

鏈表存得不應該是自己得地址吧 否則還怎麼鏈。

❼ java單鏈表遍歷,最後會輸出一個0,這個零是什麼,頭指針的引用嗎

單鏈表帶頭結點的遍歷,如果把temp!=null改成temp.next!=null遍歷就正常了,但是去掉.next就會多出一個0。這個0是一個未經初始化的內存中「殘存」的數字,這一次是零,可能在,下一次運行的時候,裡面出現的數字就可能不是0,而是其他不規則的數字。

❽ JAVA 鏈表問題

while (current != null);
{
【在這里提示current只能為空指針】b.add(current.data);
current = current.next;
}
你的while循環後面多了一個分號,導致while循環是一個空實現,而後面的是一個代碼塊而已

❾ Java單鏈表的問題

class Node{ private Object data; private Node next; Node (){} Node (Object data) { this.setData(data); this.setNext(null); } public void setData(Object data){ this.data = data; } public void setNext(Node next){ this.next = next; } public Object getData(){ return this.data; } public Node getNext(){ return this.next; } public String printNode(){ return "節點內的內容為:"+this.getData(); } public boolean equals(Node node){ if(this.getData().equals(node.getData())) return true; else return false; } } class SingleLink{ private Node root; private int size; SingleLink() { this.setSize(); } public void setSize(){ if(this.root==null) { size = 0; } Node temp; temp = this.root; while(temp!=null){ size++; temp = temp.getNext(); } } public int getSize(){ return this.size; } public Node addNode(Node newNode){ if(this.root == null){ this.root = newNode; size++; return this.root; } Node temp = this.root; while(temp.getNext()!=null){ temp = temp.getNext(); } temp.setNext(newNode); size++; return this.root; } public void print(){ if(this.root == null ){ System.out.println("鏈表不存在!"); } int count=0; Node temp; temp = this.root; while(temp!=null) { System.out.print("第"+(++count)+"個"+temp.printNode()+"->"); temp=temp.getNext(); } System.out.println(); } public boolean search(Object data){ if(this.root == null ){ System.out.println("鏈表不存在!"); return false; } boolean flag = false; Node temp; temp=this.root; while(temp!=null){ if(temp.getData().equals(data)){ flag = true; break; } temp = temp.getNext(); } return flag; } public void deleteNode(Object data){ if(this.root == null ){ System.out.println("鏈表不存在!"); } Node temp; temp=this.root; while(temp!=null){ if(temp.getNext().getData().equals(data)){ break; } temp = temp.getNext(); } if(temp==null){ System.out.println("未找到節點!"); } else { temp.setNext(temp.getNext().getNext()); } } } public class LinkDemo{ public static void main(String args[]){ Node node依 = new Node("第依個節點"); Node node貳 = new Node("第貳個節點"); Node node三 = new Node("第三個節點"); Node node四 = new Node("第四個節點"); Node node5 = new Node("第5個節點"); Node node陸 = new Node("第陸個節點"); SingleLink singleLink = new SingleLink(); //System.out.println(singleLink.getSize()); singleLink.addNode(node依); singleLink.addNode(node貳); singleLink.addNode(node三); singleLink.addNode(node四); singleLink.addNode(node5); singleLink.addNode(node陸); //System.out.println(singleLink.getSize()); //singleLink.print(); if(singleLink.search("第漆個節點")) { System.out.println("節點存在!"); } else{ System.out.println("節點不存在!"); } singleLink.deleteNode("第貳個節點"); singleLink.print();

❿ 遍歷java集合或數組的幾種方式

list集合的遍歷3種方法:

[java] view plain
package com.sort;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
* list的三種遍歷
* @author Owner
*
*/
public class ListTest {

public static void main(String[] args) {

List<String> list = new ArrayList<String>();

list.add("a");
list.add("b");
list.add("c");
list.add("c");//可添加重復數據

//遍歷方法一
for(Iterator<String> iterator = list.iterator();iterator.hasNext();){
String value = iterator.next();

System.out.println(value);
}

//遍歷方法二
for(String value : list){
System.out.println(value);
}

//遍歷方法三
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
}

}
}

三種遍歷的比較分析:

方法一遍歷:
執行過程中會進行數據鎖定, 性能稍差, 同時,如果你想在循環過程中去掉某個元素,只能調用it.remove方法。

方法二遍歷:
內部調用第一種

方法三遍歷:
內部不鎖定, 效率最高, 但是當寫多線程時要考慮並發操作的問題

List介面的兩種主要實現類ArrayList和LinkedList都可以採用這樣的方法遍歷

關於ArrayList與LinkedList的比較分析
a) ArrayList底層採用數組實現,LinkedList底層採用雙向鏈表實現。
b) 當執行插入或者刪除操作時,採用LinkedList比較好。
c) 當執行搜索操作時,採用ArrayList比較好。

熱點內容
腳本動畫分鏡頭 發布:2022-12-07 01:11:13 瀏覽:137
買特斯拉最晚什麼時候選配置 發布:2022-12-07 01:10:35 瀏覽:861
重慶貓編程 發布:2022-12-07 01:09:31 瀏覽:998
我的世界手機版0131伺服器ip大全 發布:2022-12-07 01:08:47 瀏覽:824
五菱宏光s最高配都有什麼配置 發布:2022-12-07 01:08:37 瀏覽:265
安卓沙星是管什麼的 發布:2022-12-07 01:07:08 瀏覽:645
c語言冪次方 發布:2022-12-07 01:06:06 瀏覽:418
lol台服伺服器地址 發布:2022-12-07 01:01:30 瀏覽:115
hashmd5演算法 發布:2022-12-07 01:00:35 瀏覽:572
matlab腳本程序 發布:2022-12-07 01:00:31 瀏覽:875