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