⑴ 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語言，編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作。新手，要俗易懂些，最好自己調適通過。急
定義介面：
//Deque.java
package dsa; //根據自己的程序位置不同
public interface Deque {
public int getSize();//返回隊列中元素數目
public boolean isEmpty();//判斷隊列是否為空
public Object first() throws ExceptionQueueEmpty;//取首元素（但不刪除）
public Object last() throws ExceptionQueueEmpty;//取末元素（但不刪除）
public void insertFirst(Object obj);//將新元素作為首元素插入
public void insertLast(Object obj);//將新元素作為末元素插入
public Object removeFirst() throws ExceptionQueueEmpty;//刪除首元素
public Object removeLast() throws ExceptionQueueEmpty;//刪除末元素
public void Traversal();//遍歷
}
雙向鏈表實現：
//Deque_DLNode.java
/*
* 基於雙向鏈表實現雙端隊列結構
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向頭節點（哨兵）
protected DLNode trailer;//指向尾節點（哨兵）
protected int size;//隊列中元素的數目
//構造函數
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
//返回隊列中元素數目
public int getSize()
{ return size; }
//判斷隊列是否為空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不刪除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
return header.getNext().getElem();
}
//取末元素（但不刪除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
return trailer.getPrev().getElem();
}
//在隊列前端插入新節點
public void insertFirst(Object obj) {
DLNode second = header.getNext();
DLNode first = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
//在隊列後端插入新節點
public void insertLast(Object obj) {
DLNode second = trailer.getPrev();
DLNode first = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
//刪除首節點
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
DLNode first = header.getNext();
DLNode second = first.getNext();
Object obj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
}
//刪除末節點
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊列為空");
DLNode first = trailer.getPrev();
DLNode second = first.getPrev();
Object obj = first.getElem();
trailer.setPrev(second);
second.setNext(trailer);
size--;
return(obj);
}
//遍歷
public void Traversal() {
DLNode p = header.getNext();
while (p != trailer) {
System.out.print(p.getElem()+" ");
p = p.getNext();
}
System.out.println();
}
}
⑶ 雙向循環鏈表java
我們也做這個，，你是是吧
package KeCheng1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Scanner;
//定義節點類
class Node<AnyType> {
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
data=d;
prev=p;
next=n;}}
public class MyLinkedList<AnyType> {
private int theSize;
private Node<AnyType> beginMarker; //頭標記或頭節點
private Node<AnyType> endMarker; //尾標記或尾節點
public MyLinkedList(){
beginMarker=new Node<AnyType>(null,endMarker,endMarker);
endMarker = new Node<AnyType>(null,beginMarker,beginMarker);
beginMarker.next = endMarker;
theSize = 0;}
public int size(){
return theSize;}
public boolean add(AnyType x){
add(size(),x);
return true;}
public void add(int idx,AnyType x){
Node<AnyType> p;
p=getNode(idx);
addBefore(p,x);}
private Node<AnyType> getNode(int idx) {
Node<AnyType> p;
if( idx < 0 || idx > size( ) )
throw new IndexOutOfBoundsException( );
if( idx < size( ) / 2 ) {
p = beginMarker.next;
for( int i = 0; i < idx; i++ )
p = p.next;}
else
{ p = endMarker;
for( int i = size( ); i > idx; i-- )
p = p.prev; }
return p;}
private void addBefore( Node<AnyType> p, AnyType x ) {
Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;}
public AnyType remove( int idx ){
return remove( getNode(idx));}
private AnyType remove(Node<AnyType> p){
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;}
public void print(){//輸出鏈表
for(Node<AnyType>x=beginMarker.next;x.next!=beginMarker;x=x.next)
System.out.print(x.data+" ");
System.out.print("\n");}
public AnyType get( int idx ){
return getNode( idx ).data; }
public static void main(String[] args){
MyLinkedList<Integer> La = new MyLinkedList<Integer>();
int Length;
Scanner sc = new Scanner(System.in);
System.out.println("請輸入要創建的雙向鏈表的長度：(大於6)");
Length = sc.nextInt();
System.out.println("請輸入"+Length+"個元素創建La雙向鏈表：");
for(int i=0;i<Length;i++)
{La.add(sc.nextInt());}
System.out.println("輸入的原La雙向鏈表：");
La.print();
System.out.println("在雙向鏈表的第3個位置插入20:");
La.add(3,20);
La.print();
System.out.println("刪除第五位置上的數:");
La.remove(5);
La.print();
System.out.println("插入最後一個節點:99");
La.add(Length,99);
La.print();
System.out.println("插入第一個節點0:");
La.add(0,0);
La.print();
System.out.println("就地逆置:");
int M=Length+2;
int b=0;
for(Length=Length+1;Length>=0;Length--){
int a=La.get(M-1);
La.add(b,a);
b=b+1;
La.remove(M);
}
La.print();
}
}
⑷ java數據結構--實現雙鏈表
調換了出了什麼問題了嗎？調換後應該結果不變的。你的循環有問題的p.next != null第一個節點卻是ew Node(e,null,null); 明顯下個的節點就是null啊，這樣寫永遠都只有一個節點的。
⑸ 如何實現Java中一個簡單的LinkedList
與實現ArrayList的名字一樣，為SimpleLinkedList。源碼地址，歡迎star,fork
構建一個雙向鏈表
構建的代碼如下：
?
1
2
3
4
5
6
7
8
9
10
private static class Node<E>{
E item;
Node<E> next;
Node<E> prev;
public Node(E item, Node<E> next, Node<E> prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
常規的雙向鏈表的構建方法，一個數字域存放數組，一個前指針指向一個Node類型的元素，一個後指針指向一個Node類型的元素。
對於LinkedList的實現而言，還需要以下三個成員變數
?
⑹ 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單向鏈表改成雙向鏈表
一、JAVA單向鏈表的操作（增加節點、查找節點、刪除節點）
classLink{//鏈表類
classNode{//保存每一個節點，此處為了方便直接定義成內部類
privateStringdata;//節點的內容
privateNodenext;//保存下一個節點
publicNode(Stringdata){//通過構造方法設置節點內容
this.data=data;
}
publicvoidadd(Nodenode){//增加節點
if(this.next==null){//如果下一個節點為空，則把新節點加入到next的位置上
this.next=node;
}else{//如果下一個節點不為空，則繼續找next
this.next.add(node);
}
}
publicvoidprint(){//列印節點
if(this.next!=null){
System.out.print(this.data+"-->");
this.next.print();
}else{
System.out.print(this.data+"
");
}
}
publicbooleansearch(Stringdata){//內部搜索節點的方法
if(this.data.equals(data)){
returntrue;
}
if(this.next!=null){
returnthis.next.search(data);
}else{
returnfalse;
}
}
publicvoiddelete(Nodeprevious,Stringdata){//內部刪除節點的方法
if(this.data.equals(data)){
previous.next=this.next;
}else{
if(this.next!=null){
this.next.delete(this,data);
}
}
}
}
privateNoderoot;//定義頭節點
publicvoidaddNode(Stringdata){//根據內容添加節點
NodenewNode=newNode(data);//要插入的節點
if(this.root==null){//沒有頭節點，則要插入的節點為頭節點
this.root=newNode;
}else{//如果有頭節點，則調用節點類的方法自動增加
this.root.add(newNode);
}
}
publicvoidprint(){//展示列表的方法
if(root!=null){//當鏈表存在節點的時候進行展示
this.root.print();
}
}
publicbooleansearchNode(Stringdata){//在鏈表中尋找指定內容的節點
returnroot.search(data);//調用內部搜索節點的方法
}
publicvoiddeleteNode(Stringdata){//在鏈表中刪除指定內容的節點
if(root.data.equals(data)){//如果是頭節點
if(root.next!=null){
root=root.next;
}else{
root=null;
}
}else{
root.next.delete(this.root,data);
}
}
}二、雙向鏈表的簡單實現
publicclassDoubleLink<T>{
/**
*Node<AnyType>類定義了雙向鏈表中節點的結構，它是一個私有類，而其屬性和構造函數都是公有的，這樣，其父類可以直接訪問其屬性
*而外部類根本不知道Node類的存在。
*
*@authorZHB
*
*@param<T>
*類型
*@paramData
*是節點中的數據
*@parampre
*指向前一個Node節點
*@paramnext
*指向後一個Node節點
*/
privateclassNode<T>{
publicNode<T>pre;
publicNode<T>next;
publicTdata;
publicNode(Tdata,Node<T>pre,Node<T>next){
this.data=data;
this.pre=pre;
this.next=next;
}
publicNode(){
this.data=null;
this.pre=null;
this.next=null;
}
}
//下面是DoubleLinkedList類的數據成員和方法
privateinttheSize;
privateNode<T>Header;
privateNode<T>Tail;
/*
*構造函數我們構造了一個帶有頭、尾節點的雙向鏈表頭節點的Next指向尾節點為節點的pre指向頭節點鏈表長度起始為0。
*/
publicDoubleLink(){
theSize=0;
Header=newNode<T>(null,null,null);
Tail=newNode<T>(null,Header,null);
Header.next=Tail;
}
publicvoidadd(Titem){
Node<T>aNode=newNode<T>(item,null,null);
Tail.pre.next=aNode;
aNode.pre=Tail.pre;
aNode.next=Tail;
Tail.pre=aNode;
theSize++;
}
publicbooleanisEmpty(){
return(this.theSize==0);
}
publicintsize(){
returnthis.theSize;
}
publicTgetInt(intindex){
if(index>this.theSize-1||index<0)
();
Node<T>current=Header.next;
for(inti=0;i<index;i++){
current=current.next;
}
returncurrent.data;
}
publicvoidprint(){
Node<T>current=Header.next;
while(current.next!=null){
System.out.println(current.data.toString());
current=current.next;
}
}
publicstaticvoidmain(String[]args){
DoubleLink<String>dLink=newDoubleLink<String>();
dLink.add("zhb");
dLink.add("zzb");
dLink.add("zmy");
dLink.add("zzj");
System.out.println("size:"+dLink.size());
System.out.println("isEmpty?:"+dLink.isEmpty());
System.out.println("3:"+dLink.getInt(2));
dLink.print();
}
}
⑻ java怎麼用鏈表實現
在數據結構中經常看見的一個基本概念-鏈表。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
在Java中，對於鏈表的實現都是基於引用數據類型操作的。實現大致如下：
定義節點類Node，節點的概念很重要，一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用，再增加一個添加節點的方法即可完成鏈表實現。
鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。在執行效率上，相比數組而言，鏈表插入快查找慢，開發中得根據實際業務使用。