java循環鏈表
A. java怎麼用鏈表實現
在數據結構中經常看見的一個基本概念-鏈表。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
在Java中，對於鏈表的實現都是基於引用數據類型操作的。實現大致如下：
定義節點類Node，節點的概念很重要，一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用，再增加一個添加節點的方法即可完成鏈表實現。
鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。在執行效率上，相比數組而言，鏈表插入快查找慢，開發中得根據實際業務使用。
B. 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類的代碼稍加改動即可。
希望對你有幫助。
C. java 有循環鏈表嗎
網頁鏈接
java可以實現鏈表的，不管是單鏈表、雙鏈表還是循環鏈表。
D. 用java語言編寫單循環鏈表約瑟夫生死游戲
LinkList p;; /link,int k;*循環地刪除隊列結點*，m為出列者喊到的數
{
/
}
p-;n最後被刪除的元素是;
for(int i=0;data);link;
for(i=0;*使鏈表循環起來*,int m) /m-1,P-；
p=p-;；i++)
{
p=(LinkList)malloc(sizeof(LNode)); /link,p-;ilt;
}
r-;n為總人數;link;
p=p-;;
p=list;
p=r-;
}
，k為第一個開始報數的人;i++)
{
r=p;* p為當前結點 r為輔助結點；
⒊不斷地從鏈表中刪除鏈結點;
else
r-;link=p;
free(p),r;
p-;data);，無頭結點的循環鏈表;*建立循環鏈表*：%4dquot；ilt;*使p指向頭節點*!=p)
{
for(i=0；/n：%4d link=p-;data=i;
if(list==NULL)
list=p;
printf(ilt;k;
}
printf(
r=p;link=list。
void JOSEPHUS(int n;*把當前指針移動到第一個報數的人*/
/i++)
{
r=p，指向p的前驅結點 list為頭節點*/link解決問題的核心步驟,list：（程序的基本演算法）
⒈建立一個具有n個鏈結點；
⒉確定第1個報數人的位置;
while(p-，直到鏈表為空;被刪除的元素
E. Java循環雙鏈表如何深拷貝子表
雙鏈結構的話，在拷貝的過程中是直接可以用用復制粘貼就可以完成了的。
F. java循環單鏈表實現約瑟夫環
看了你的代碼，不是很明白，給你提幾個建議吧：
1、不需要tail節點
2、remove方法應該對刪除節點前面的節點操作，而不是使用數字找
給你我修改的LinkList類，你參考一下：
publicclassLinkList{
privateNodehead;
intcurlen=0;
//創建鏈表
publicvoidcreatelist(intcode)throwsException{
insert(curlen,code);
}
publicvoidinsert(inti,intcode)throwsException{
Nodes=newNode(code);
if(i==0){
s.setNext(head);
head=s;
}
Nodep=head;
intj=0;
while(p!=null&&j<i-1){
p=p.getNext();
j++;
}
if(j>i||p==null){
thrownewException("插入位置不合理");
}
s.setNext(p.getNext());
p.setNext(s);
// tail=s;
// tail.setNext(head);
curlen=curlen+1;
}
publicvoidremove(inti)throwsException{
Nodep=head,q=null;
intj=0;
i=i-1;
while(j<i){
q=p;
p=p.getNext();
j++;
}
if(j>i||p==null)
thrownewException("刪除位置不合法");
if(q==null){
// tail.setNext(p.getNext());
head=head.getNext();
}else
q.setNext(p.getNext());
curlen=curlen-1;
}
/**
*按照節點刪除
*@parami
*@throwsException
*/
publicvoidremove(Nodep)throwsException{
if(p.getNext()==p){
p=null;
head=null;
}
else{
Nodeq=p.getNext();
p.setNext(q.getNext());
}
curlen=curlen-1;
}
publicvoidout(intm)throwsException{
Nodep=head;
if(m==1){
System.out.print("按照順序出列");
return;
}
intcount=1;
intn=m-1;
while(curlen>0){
if(count==n){
System.out.print(p.getNext().getData()+"");
remove(p);
count=1;
}else{
count++;
}
p=p.getNext();
}
}
publicvoiddisplay(){
Nodenode=head;
for(inti=0;i<2*curlen;i++){
System.out.print(node.getData()+"");
node=node.getNext();
}
System.out.println();
}
}
G. 一個關於Java鏈表循環遍歷，排序的問題。高手上了！！！
package com.neusoft.main;
import java.util.ArrayList;import java.util.List;
public class TestCoordinate {
/**
* <p>Discription:[方法功能中文描述]</p>
* @param args
* @author:[滕一漢]
* @update:[日期YYYY-MM-DD] [更改人姓名][變更描述]
*/
public static void main(String[] args) {
List list = new ArrayList();
list.add( new CoordinateObj(10,10));
list.add( new CoordinateObj(20,20));
list.add( new CoordinateObj(30,30));
list.add( new CoordinateObj(40,40));
list.add( new CoordinateObj(50,50));
list.add( new CoordinateObj(60,60));
list.add( new CoordinateObj(70,70));
list.add( new CoordinateObj(80,80));
list.add( new CoordinateObj(90,90));
list.add( new CoordinateObj(100,100));
getNearestCoor(list, new CoordinateObj(0, 0));
}
public static CoordinateObj getNearestCoor(List list, CoordinateObj nowCoor) {
double dis = 0d;
CoordinateObj newcoo = null;
for (int i = 0; i < list.size(); i++) {
CoordinateObj coo = (CoordinateObj) list.get(i);
double x = coo.getX() - nowCoor.getX();
double y = coo.getY() - nowCoor.getY();
double newDis = Math.hypot(x, y);
if (dis == 0) {
dis = newDis;
newcoo = coo;
}
else {
if (newDis < dis) {
newcoo = coo;
dis = newDis;
}
}
}
list.remove(newcoo);
System.out.println("x:" + newcoo.getX() + "---y:" + newcoo.getY());
if(list.size()>0)
getNearestCoor(list,newcoo);
return newcoo;
}
}
package com.neusoft.main;
public class CoordinateObj {
public CoordinateObj(){}
CoordinateObj(double x,double y){
this.x = x;
this.y = y;
}
double x;//x 坐標
double y;//y 坐標
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
H. java中的循環鏈表怎麼寫
設置 last.next = head
head.pre=last
I. Java約瑟夫循環單循環鏈表
importjava.util.List;
importjava.util.ArrayList;
publicclassProgram{
/**
*為參與約瑟夫循環的<code>人數</code>。
*/
publicfinalstaticintGAME_PEOPLE_NUMBER=10;
publicstaticvoidmain(String...args){
List<GameObject>gameObjects=newArrayList<>();
//初始化參與約瑟夫角色的信息,必要時可以更改為從鍵盤輸入。但此處只為演示,so，省略...
for(inti=0;i<Program.GAME_PEOPLE_NUMBER;i++){
gameObjects.add(newGameObject(i+1,i+1,"nn-"+i));
}
inti=0,c=0,m=2;
while(gameObjects.size()>0){
c++;
if(c==m){
System.out.println(gameObjects.get(i));
m=gameObjects.get(i).getPassword();
gameObjects.remove(i);
c=0;
}
i++;
if(i>=gameObjects.size())i=0;
}
}
}
classGameObject{
privateintid;
privateintpassword;
privateStringnickName;
publicintgetId(){
returnid;
}
publicvoidsetId(intid){
this.id=id;
}
publicintgetPassword(){
returnpassword;
}
publicvoidsetPassword(intpassword){
this.password=password;
}
publicStringgetNickName(){
returnnickName;
}
publicvoidsetNickName(StringnickName){
this.nickName=nickName;
}
publicGameObject(){
}
publicGameObject(intid,intpassword,StringnickName){
this.id=id;
this.password=password;
this.nickName=nickName;
}
@Override
publicStringtoString(){
return"出隊[id="+id+",password="+password+",nickName="+nickName+"]";
}
}
J. java循環雙鏈表類添加求平均值的方法
public class DoubleLinkedList
{
// 節點類Node
private static class Node
{
Object value;
Node prev = this;
Node next = this;
Node(Object v)
{
value = v;
}
public String toString()
{
return value.toString();
}
}
private Node head = new Node(null); // 頭節點
private int size; // 鏈表大小
// 以下是介面方法
public boolean addFirst(Object o)
{
addAfter(new Node(o), head);
return true;
}
public boolean addLast(Object o)
{
addBefore(new Node(o), head);
return true;
}
public boolean add(Object o)
{
return addLast(o);
}
public boolean add(int index, Object o)
{
addBefore(new Node(o), getNode(index));
return true;
}
public boolean remove(int index)
{
removeNode(getNode(index));
return true;
}
public boolean removeFirst()
{
removeNode(head.next);
return true;
}
public boolean removeLast()
{
removeNode(head.prev);
return true;
}
public Object get(int index)
{
return getNode(index).value;
}
public int size()
{
return size;
}
public String toString()
{
StringBuffer s = new StringBuffer("[");
Node node = head;
for (int i = 0; i < size; i++)
{
node = node.next;
if (i > 0)
s.append(", ");
s.append(node.value);
}
s.append("]");
return s.toString();
}
private Node getNode(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
Node node = head.next;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
private void addBefore(Node newNode, Node node)
{
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void addAfter(Node newNode, Node node)
{
newNode.prev = node;
newNode.next = node.next;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void removeNode(Node node)
{
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
size--;
}
}
//測試類：
public class Test
{
public static void main(String[] args)
{
DoubleLinkedList dll = new DoubleLinkedList();
//添加
dll.add("張三");
dll.add("李四");
dll.add("王五");
System.out.println(dll);
//添加到最前
dll.addFirst("孫七");
System.out.println(dll);
//添加到最後，同添加
dll.addLast("趙六");
System.out.println(dll);
//添加到指定位置
dll.add(4, "王祖賢");
System.out.println(dll);
//移除最前的
dll.removeFirst();
System.out.println(dll);
//移除最後的
dll.removeLast();
System.out.println(dll);
//移除指定位置上的
dll.remove(2);
System.out.println(dll);
//返回指定位置上的元素
System.out.println(dll.get(1));
}
}