本文目錄一覽：
雙向循環鏈表java
我們也做這個，，你是是吧
package KeCheng1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Scanner;
//定義節點類
class NodeAnyType {
public AnyType data;
public NodeAnyType prev;
public NodeAnyType next;
public Node(AnyType d,NodeAnyType p,NodeAnyType n){
data=d;
prev=p;
next=n;}}
public class MyLinkedListAnyType {
private int theSize;
private NodeAnyType beginMarker; //頭標記或頭節點
private NodeAnyType endMarker; //尾標記或尾節點
public MyLinkedList(){
beginMarker=new NodeAnyType(null,endMarker,endMarker);
endMarker = new NodeAnyType(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){
NodeAnyType p;
p=getNode(idx);
addBefore(p,x);}
private NodeAnyType getNode(int idx) {
NodeAnyType 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( NodeAnyType p, AnyType x ) {
NodeAnyType newNode = new NodeAnyType( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;}
public AnyType remove( int idx ){
return remove( getNode(idx));}
private AnyType remove(NodeAnyType p){
p.next.prev = p.prev;
p.prev.next = p.next;
theSize–;
return p.data;}
public void print(){//輸出鏈表
for(NodeAnyTypex=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){
MyLinkedListInteger La = new MyLinkedListInteger();
int Length;
Scanner sc = new Scanner(System.in);
System.out.println(“請輸入要創建的雙向鏈表的長度：(大於6)”);
Length = sc.nextInt();
System.out.println(“請輸入”+Length+”個元素創建La雙向鏈表：”);
for(int i=0;iLength;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中如何實現雙向鏈表?
雙向鏈表：就是有雙向指針，即雙向的鏈域。\x0d\x0a鏈結點的結構：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。\x0d\x0a有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。\x0d\x0a/**\x0d\x0a * 雙向鏈表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首結點\x0d\x0a private Link rear; //尾部指針\x0d\x0a public DoublyLinkedList() { }\x0d\x0a public T peekHead() {\x0d\x0a if (head != null) {\x0d\x0a return head.data;\x0d\x0a }\x0d\x0a return null;\x0d\x0a }\x0d\x0a public boolean isEmpty() {\x0d\x0a return head == null;\x0d\x0a }\x0d\x0a public void insertFirst(T data) {// 插入 到 鏈頭\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {//為空時，第1次插入的新結點為尾結點\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //舊頭結點的上結點等於新結點\x0d\x0a }\x0d\x0a newLink.next = head; //新結點的下結點舊頭結點\x0d\x0a head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null\x0d\x0a }\x0d\x0a public void insertLast(T data) {//在鏈尾 插入\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {\x0d\x0a head = newLink;\x0d\x0a } else {\x0d\x0a rear.next = newLink;\x0d\x0a }\x0d\x0a newLink.previous = rear;\x0d\x0a rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null\x0d\x0a }\x0d\x0a public T deleteHead() {//刪除 鏈頭\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //變更首結點，為下一結點\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a } else {\x0d\x0a rear = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T deleteRear() {//刪除 鏈尾\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = rear;\x0d\x0a rear = rear.previous; //變更尾結點，為上一結點\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a } else {\x0d\x0a head = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T find(T t) {//從頭到尾find\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link find = head;\x0d\x0a while (find != null) {\x0d\x0a if (!find.data.equals(t)) {\x0d\x0a find = find.next;\x0d\x0a } else {\x0d\x0a break;\x0d\x0a }\x0d\x0a }\x0d\x0a if (find == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a return find.data;\x0d\x0a }\x0d\x0a public T delete(T t) {\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(t)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a }\x0d\x0a if (current == head) {\x0d\x0a head = head.next;\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a }\x0d\x0a } else if (current == rear) {\x0d\x0a rear = rear.previous;\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a }\x0d\x0a } else {\x0d\x0a //中間的非兩端的結點，要移除current\x0d\x0a current.next.previous = current.previous;\x0d\x0a current.previous.next = current.next;\x0d\x0a }\x0d\x0a return current.data;\x0d\x0a }\x0d\x0a public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false\x0d\x0a if (isEmpty()) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(key)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a }\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (current == rear) {\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a newLink.next = current.next;\x0d\x0a current.next.previous = newLink;\x0d\x0a }\x0d\x0a current.next = newLink;\x0d\x0a newLink.previous = current;\x0d\x0a return true;\x0d\x0a }\x0d\x0a public void displayList4Head() {//從頭開始遍歷\x0d\x0a System.out.println(“List (first–last):”);\x0d\x0a Link current = head;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.next;\x0d\x0a }\x0d\x0a }\x0d\x0a public void displayList4Rear() {//從尾開始遍歷\x0d\x0a System.out.println(“List (last–first):”);\x0d\x0a Link current = rear;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.previous;\x0d\x0a }\x0d\x0a }\x0d\x0a\x0d\x0a class Link {//鏈結點\x0d\x0a T data; //數據域\x0d\x0a Link next; //後繼指針，結點 鏈域\x0d\x0a Link previous; //前驅指針，結點 鏈域\x0d\x0a Link(T data) {\x0d\x0a this.data = data;\x0d\x0a }\x0d\x0a void displayLink() {\x0d\x0a System.out.println(“the data is ” + data.toString());\x0d\x0a }\x0d\x0a }\x0d\x0a public static void main(String[] args) {\x0d\x0a DoublyLinkedList list = new DoublyLinkedList();\x0d\x0a list.insertLast(1);\x0d\x0a list.insertFirst(2);\x0d\x0a list.insertLast(3);\x0d\x0a list.insertFirst(4);\x0d\x0a list.insertLast(5);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteHead = list.deleteHead();\x0d\x0a System.out.println(“deleteHead:” + deleteHead);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteRear = list.deleteRear();\x0d\x0a System.out.println(“deleteRear:” + deleteRear);\x0d\x0a list.displayList4Rear();\x0d\x0a System.out.println(“find:” + list.find(6));\x0d\x0a System.out.println(“find:” + list.find(3));\x0d\x0a System.out.println(“delete find:” + list.delete(6));\x0d\x0a System.out.println(“delete find:” + list.delete(1));\x0d\x0a list.displayList4Head();\x0d\x0a System.out.println(“—-在指定key後插入—-“);\x0d\x0a list.insertAfter(2, 8);\x0d\x0a list.insertAfter(2, 9);\x0d\x0a list.insertAfter(9, 10);\x0d\x0a list.displayList4Head();\x0d\x0a }\x0d\x0a}
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語言沒有指針，怎樣實現鏈表?
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的源代碼如下：
package cn.javatx; import java.io.IOException;/**
* @author ljfan
*
*/
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.out.println(“You can press return to quitn”);
try {
System.in.read();
} catch (IOException e) {
}
}
}class Node {
Object data;
Node next;Node(Object d) {
data = d;
next = null;
}
}
當然，雙向鏈表基本操作的實現略有不同。鏈表和雙向鏈表的實現方法，也可以用在堆棧和隊列的現實中。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/227605.html
微信掃一掃 
支付寶掃一掃 