線性表接口LList：
package com.clarck.datastructure.linked;
/**
* 線性表接口LList，描述線性表抽象數據類型，泛型參數T表示數據元素的數據類型
*
* @author clarck
*
*/
public interface LList {
/**
* 判斷線性表是否空
* @return
*/
boolean isEmpty();
/**
* 返回線性表長度
* @return
*/
int length();
/**
* 返回第i(i≥0)個元素
* @param i
* @return
*/
T get(int i);
/**
* 設置第i個元素值為x
* @param i
* @param x
*/
void set(int i, T x);
/**
* 插入x作為第i個元素
* @param i
* @param x
*/
void insert(int i, T x);
/**
* 在線性表最后插入x元素
* @param x
*/
void append(T x);
/**
* 刪除第i個元素并返回被刪除對象
* @param i
* @return
*/
T remove(int i);
/**
* 刪除線性表所有元素
*/
void removeAll();
/**
* 查找，返回首次出現的關鍵字為key元素
* @param key
* @return
*/
T search(T key);
}
單鏈表結點類：
package com.clarck.datastructure.linked;
/**
* 單鏈表結點類，T指定結點的元素類型
*
* @author clarck
*
* @param
*/
public class Node {
/**
* 數據域，保存數據元素
*/
public T data;
/**
* 地址域，引用后繼結點
*/
public Node next;
/**
* 構造結點，data指定數據元素，next指定后繼結點
*
* @param data
* @param next
*/
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
/**
* 構造節點
*/
public Node() {
this(null, null);
}
/**
* 返回結點元素值對應的字符串
*/
@Override
public String toString() {
return this.data.toString();
}
/**
* 比較兩個結點值是否相等，覆蓋Object類的equals(obj)方法
*/
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object obj) {
return obj == this || obj instanceof Node && this.data.equals(((Node)obj).data);
}
}
線性表的鏈式表示和實現：
package com.clarck.datastructure.linked;
/**
* 線性表的鏈式表示和實現 帶頭結點的單鏈表類，實現線性表接口
*
* @author clarck
*
* @param
*/
public class SinglyLinkedList implements LList {
/**
* 頭指針，指向單鏈表的頭結點
*/
public Node head;
/**
* 默認構造方法，構造空單鏈表
*/
public SinglyLinkedList() {
// 創建頭結點，data和next值均為null
this.head = new Node();
}
/**
* 由指定數組中的多個對象構造單鏈表。采用尾插入構造單鏈表
* 若element==null，Java將拋出空對象異常；若element.length==0，構造空鏈表
*
* @param element
*/
public SinglyLinkedList(T[] element) {
// 創建空單鏈表，只有頭結點
this();
// rear指向單鏈表最后一個結點
Node rear = this.head;
for (int i = 0; i < element.length; i++) {
rear.next = new Node(element[i], null);
rear = rear.next;
}
}
/**
* 判斷單鏈表是否空，O(1)
*/
@Override
public boolean isEmpty() {
return this.head.next == null;
}
/**
* 返回單鏈表長度，O(n), 基于單鏈表遍歷算法
*/
@Override
public int length() {
int i = 0;
// p從單鏈表第一個結點開始
Node p = this.head.next;
// 若單鏈表未結束
while (p != null) {
i++;
// p到達后繼結點
p = p.next;
}
return i;
}
/**
* 返回第i(≥0)個元素，若i<0或大于表長則返回null，O(n)
*/
@Override
public T get(int i) {
if (i >= 0) {
Node p = this.head.next;
for (int j = 0; p != null && j < i; j++) {
p = p.next;
}
// p指向第i個結點
if (p != null) {
return p.data;
}
}
return null;
}
/**
* 設置第i(≥0)個元素值為x。若i<0或大于表長則拋出序號越界異常；若x==null，不操作。O(n)
*/
@Override
public void set(int i, T x) {
if (x == null)
return;
Node p = this.head.next;
for (int j = 0; p != null && j < i; j++) {
p = p.next;
}
if (i >= 0 && p != null) {
p.data = x;
} else {
throw new IndexOutOfBoundsException(i + "");
}
}
/**
* 插入第i(≥0)個元素值為x。若x==null，不插入。 若i<0，插入x作為第0個元素；若i大于表長，插入x作為最后一個元素。O(n)
*/
@Override
public void insert(int i, T x) {
// 不能插入空對象
if (x == null) {
return;
}
// p指向頭結點
Node p = this.head;
// 尋找插入位置
for (int j = 0; p.next != null && j < i; j++) {
// 循環停止時，p指向第i-1結點或最后一個結點
p = p.next;
}
// 插入x作為p結點的后繼結點，包括頭插入(i<=0)、中間/尾插入(i>0)
p.next = new Node(x, p.next);
}
/**
* 在單鏈表最后添加x對象，O(n)
*/
@Override
public void append(T x) {
insert(Integer.MAX_VALUE, x);
}
/**
* 刪除第i(≥0)個元素，返回被刪除對象。若i<0或i大于表長，不刪除，返回null。O(n)
*/
@Override
public T remove(int i) {
if (i >= 0) {
Node p = this.head;
for (int j = 0; p.next != null && j < i; j++) {
p = p.next;
}
if (p != null) {
// 獲得原對象
T old = p.next.data;
// 刪除p的后繼結點
p.next = p.next.next;
return old;
}
}
return null;
}
/**
* 刪除單鏈表所有元素 Java將自動收回各結點所占用的內存空間
*/
@Override
public void removeAll() {
this.head.next = null;
}
/**
* 順序查找關鍵字為key元素，返回首次出現的元素，若查找不成功返回null
* key可以只包含關鍵字數據項，由T類的equals()方法提供比較對象相等的依據
*/
@Override
public T search(T key) {
if (key == null)
return null;
for (Node p = this.head.next; p != null; p = p.next)
if (p.data.equals(key))
return p.data;
return null;
}
/**
* 返回單鏈表所有元素的描述字符串，形式為“(,)”，覆蓋Object類的toString()方法，O(n)
*/
@Override
public String toString() {
String str = "(";
for (Node p = this.head.next; p != null; p = p.next) {
str += p.data.toString();
if (p.next != null)
str += ","; // 不是最后一個結點時后加分隔符
}
return str + ")"; // 空表返回()
}
/**
* 比較兩條單鏈表是否相等
*/
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object obj) {
if (obj == this)
return true;
if (obj instanceof SinglyLinkedList) {
SinglyLinkedList list = (SinglyLinkedList) obj;
return equals(this.head.next, list.head.next);
}
return false;
}
/**
* 比較兩條單鏈表是否相等，遞歸方法
*
* @param p
* @param q
* @return
*/
private boolean equals(Node p, Node q) {
return p == null && q == null || p != null && q != null
&& p.data.equals(q.data) && equals(p.next, q.next);
}
}
測試類：
package com.clarck.datastructure.linked;
/**
* 單鏈表的測試
*
* @author clarck
*
*/
public class SinglyLinkedList_test {
public static void main(String args[]) {
SinglyLinkedList lista = new SinglyLinkedList();
for (int i = 0; i <= 5; i++)
lista.insert(i, new String((char) ('A' + i) + ""));
System.out.println("lista: " + lista.toString() + "，length()="
+ lista.length());
lista.set(3, new String((char) (lista.get(0).charAt(0) + 32) + ""));
lista.remove(0);
lista.remove(3);
System.out.println("lista: " + lista.toString());
}
}
測試結果：
lista: (A,B,C,D,E,F)，length()=6lista: (B,C,a,F)
