我們要使用單鏈表這個數(shù)據(jù)結(jié)構(gòu)來解決問題的前提是首先得創(chuàng)建一個單鏈表數(shù)據(jù)結(jié)構(gòu)。創(chuàng)建單鏈表數(shù)據(jù)結(jié)構(gòu)，就得自定義個單鏈表的抽象數(shù)據(jù)類型，抽象數(shù)據(jù)類型只是對數(shù)據(jù)結(jié)構(gòu)定義一組邏輯操作，沒有具體的實(shí)現(xiàn)。在實(shí)際應(yīng)用中，必須實(shí)現(xiàn)這個抽象數(shù)據(jù)類型，才能使用它們，而實(shí)現(xiàn)抽象數(shù)據(jù)類型依賴于數(shù)據(jù)存儲結(jié)構(gòu)。
1.為單鏈表的數(shù)據(jù)元素自定義結(jié)點(diǎn)類 Node.java
/**
*為單鏈表自定義的結(jié)點(diǎn)類
*單鏈表結(jié)點(diǎn)類，泛型參數(shù)T指定結(jié)點(diǎn)的元素類型
*/
public class Node<T>
{
public T data; //數(shù)據(jù)域，保存數(shù)據(jù)元素
public Node<T> next; //地址域，引用后繼結(jié)點(diǎn)
public Node(T data, Node<T> next)//構(gòu)造結(jié)點(diǎn)，data指定數(shù)據(jù)元素，next指定后繼結(jié)點(diǎn)
{
this.data = data;
this.next = next;
}
public Node()//無參構(gòu)造函數(shù)
{
this(null, null);
}
//4、Node類可聲明以下方法：
public String toString() //返回結(jié)點(diǎn)元素值對應(yīng)的字符串
{
return this.data.toString();
}
public boolean equals(Object obj) //比較兩個結(jié)點(diǎn)值是否相等，覆蓋Object類的equals(obj)方法
{
return obj==this || obj instanceof Node && this.data.equals(((Node<T>)obj).data);
}
}
2.使用Java接口為線性表自定義的抽象數(shù)據(jù)類型? ?：LList.java
/**
* 為數(shù)據(jù)結(jié)構(gòu)線性表自定義的抽象數(shù)據(jù)類型
* 在Java中，抽象數(shù)據(jù)類可以使用接口來描述
* 線性表接口LList，描泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型
*/
public interface LList<T> //線性表接口，泛型參數(shù)T表示線性表中的數(shù)據(jù)元素的數(shù)據(jù)類型
{
boolean isEmpty(); //判斷線性表是否空
int length(); //返回線性表長度
T get(int i); //返回第i（i≥0）個元素
void set(int i, T x); //設(shè)置第i個元素值為x
void insert(int i, T x); //插入x作為第i個元素
void append(T x); //在線性表插入x元素
T remove(int i); //刪除第i個元素并返回被刪除對象
void removeAll(); //刪除線性表所有元素
T search(T key); //查找，返回出現(xiàn)的關(guān)鍵字為key元素
String toString(); //返回顯示線性表所有元素值對應(yīng)的字符串
}
3.實(shí)現(xiàn)線性表接口---抽象數(shù)據(jù)類型的實(shí)現(xiàn)類-LinkedList.java（鏈表類，提供Llist接口中抽象方法的具體實(shí)現(xiàn)）
/**
*線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
*帶頭結(jié)點(diǎn)的單鏈表類
*實(shí)現(xiàn)線性表接口
*/
public class LinkedList<T>implements LList<T>//帶頭結(jié)點(diǎn)的單鏈表類，實(shí)現(xiàn)線性表接口
{
protected Node<T> head;//頭指針，指向單鏈表的頭結(jié)點(diǎn)
//默認(rèn)構(gòu)造方法，構(gòu)造空單鏈表。創(chuàng)建頭結(jié)點(diǎn)，data和next值均為null
public LinkedList()
{
this.head=new Node<T>();
}
由指定數(shù)組中的多個對象構(gòu)造單鏈表，采用尾插入構(gòu)造單鏈表
public LinkedList(T[] element){
this(); //創(chuàng)建空單鏈表，只有頭結(jié)點(diǎn)
Node<T> rear = this.head;//rear指向單鏈表的一個結(jié)點(diǎn)
/*
*若element==null，拋出空對象異常
*element.length==0時，構(gòu)造空鏈表
*/
for(int i=0;i<element.length;i++){
rear.next=new Node<T>(element[i],null);//尾插入，創(chuàng)建結(jié)點(diǎn)鏈入rear結(jié)點(diǎn)之后
rear=rear.next;//rear指向新的鏈尾結(jié)點(diǎn)
}
}
//判斷單鏈表是否為空，O(1)
public boolean isEmpty(){
return this.head.next==null;
}
//求鏈表的長度
public int length(){
int i=0;
Node<T> p = this.head.next;//p從單鏈表個結(jié)點(diǎn)開始
while(p!=null){ //若單鏈表未結(jié)束
i++;
p=p.next;//p到達(dá)后繼結(jié)點(diǎn)
}
return i;
}
//返回單鏈表所有元素的描述字符串，形式為“（，）”，覆蓋Object類的toString()方法，O(n)
public String toString(){
String str="(";
Node<T> p =this.head.next;
while(p!=null){
str+=p.data.toString();
if(p.next!=null){
str +="，"; //不是一個結(jié)點(diǎn)時后加分隔符
}
p=p.next;
}
return str+=")";
}
//返回第i(i>=0)個元素，若i無效，則返回null
public T get(int i){
if(i>=0){
Node<T> p=this.head.next;
for(int j=0; p!=null&&j<i;j++)
p=p.next;
if(p!=null)
return p.data;//p指向第i個結(jié)點(diǎn)
}
return null;
}
//設(shè)置第i(i>=0)個元素值為x，若i指定序號無效則拋出序號越界異常
public void set(int i,T x){
if(x==null)
return;//不能設(shè)置空對象
if(i>=0){
Node<T> p =this.head.next;
for(int j =0;p!=null&&j<i;j++){
p=p.next;
}
if(p!=null)
p.data=x;
}else throw new IndexOutOfBoundsException(i+"");//拋出序號越界異常
}
//將x對象出插入在序號為i結(jié)點(diǎn)前，O(n)
public void insert(int i,T x){
if(x==null)
return;
Node<T> p =this.head;
for(int j =0;p.next!=null&&j<i;j++){
p=p.next;
}
p.next=new Node<T>(x,p.next);
}
//在單鏈表的添加對象，O(n)
public void append(T x){
insert(Integer.MAX_VALUE,x);
}
//刪除序號為i的結(jié)點(diǎn)
public T remove(int i){
if(i>0){
Node<T> p=this.head;
for(int j =0;p.next!=null&&j<i;j++)
p=p.next;
if(p.next!=null){
T old=p.next.data;
p.next=p.next.next;
return old;
}
}
return null;
}
//刪除鏈表所有元素，Java自動收回各結(jié)點(diǎn)所占用的內(nèi)存空間
public void removeAll(){
this.head.next=null;
}
/*
public T search(T key){
if(key==null)
return null;
Node<T> p=this.head.next;
while(p!=null&&p.data.compareTo(key)<=0){
if(p.data.compareTo(key)==0)
return p.data;
p=p.next;
}
return null;
}
*/
//查找，返回出現(xiàn)的關(guān)鍵字為key的元素
public T search(T key)
{
if (key==null)
return null;
for (Node<T> p=this.head.next; p!=null; p=p.next)
if (p.data.equals(key))
return p.data;
return null;
}
}
4.利用前面新創(chuàng)建的單鏈表數(shù)據(jù)類型，實(shí)現(xiàn)單鏈表逆轉(zhuǎn)?SinglyLinkedList_reverse.java
注：LinkedList<T>聲明為泛型類，類型形式參數(shù)T表示鏈表元素的數(shù)據(jù)類型。當(dāng)聲明LinkedList類的對象并創(chuàng)建實(shí)例時，再指定泛型參數(shù)T的實(shí)際類型參數(shù)為一個確定的類，例如：LinkedList<String> list = new LinkedList<String>(); ?LinkedList<Integer> list = new LinkedList<Integer>(); ? 這樣可保證一個鏈表中的所有數(shù)據(jù)元素是相同類及其子類的對象。如果向鏈表添加指定泛型以外的對象，則會出現(xiàn)編譯錯誤。T 的實(shí)際類型參數(shù)必須是類，不能使int 、char等基本數(shù)據(jù)類型。如果需要表示基本數(shù)據(jù)類型，則必須使用對應(yīng)數(shù)據(jù)類型的包裝類，如Integer 、Character等。
/**
*利用前面新創(chuàng)建的單鏈表數(shù)據(jù)類型，實(shí)現(xiàn)單鏈表逆轉(zhuǎn)
*/
public class SinglyLinkedList_reverse
{
//將單鏈表逆轉(zhuǎn)，泛型方法，返回值類型前聲明類型參數(shù)T
//public static <T> void reverse(SinglyLinkedList<T> list)
public static <T> void reverse(LinkedList<T> list)
{
Node<T> p=list.head.next, succ=null, front=null; //head必須聲明為public
while (p!=null)
{
succ = p.next; //設(shè)置succ是p結(jié)點(diǎn)的后繼結(jié)點(diǎn)
p.next = front; //使p.next指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
front = p;
p = succ; //p向后走一步
}
list.head.next = front;
}
public static void main(String args[])
{
String value[]={"A","B","C","D","E","F"};
//SinglyLinkedList<String> list = new SinglyLinkedList<String>(value);
LinkedList<String> list = new LinkedList<String>(value);
System.out.println("list: "+list.toString());
reverse(list);
System.out.println("逆轉(zhuǎn)后 "+list.toString());
}
}
/*
程序運(yùn)行結(jié)果如下：
list: (A, B, C, D, E, F)
逆轉(zhuǎn)后 (F, E, D, C, B, A)
*/
想要了解更多的java應(yīng)用技術(shù)那就加入我們吧！