鏈表本身也是線性表捎迫，只不過物理存儲(chǔ)上不連續(xù)
//線性表接口
public interface List {
//獲得線性表長度
public int size();
//判斷線性表是否為空
public boolean isEmpty();
//插入元素
public void insert(int index, Object obj) throws Exception;
//刪除元素
public void delete(int index) throws Exception;
//獲取指定位置的元素
public Object get(int index) throws Exception;
}
Node.java:結(jié)點(diǎn)類
//結(jié)點(diǎn)類
public class Node {
Object element; //數(shù)據(jù)域
Node next; //指針域
//頭結(jié)點(diǎn)的構(gòu)造方法
public Node(Node nextval) {
this.next = nextval;
}
//非頭結(jié)點(diǎn)的構(gòu)造方法
public Node(Object obj, Node nextval) {
this.element = obj;
this.next = nextval;
}
//獲得當(dāng)前結(jié)點(diǎn)的指針域
public Node getNext() {
return this.next;
}
//獲得當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值
public Object getElement() {
return this.element;
}
//設(shè)置當(dāng)前結(jié)點(diǎn)的指針域
public void setNext(Node nextval) {
this.next = nextval;
}
//設(shè)置當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值
public void setElement(Object obj) {
this.element = obj;
}
public String toString() {
return this.element.toString();
}
}
LinkList.java:單向鏈表類(核心代碼)
//單向鏈表類
public class LinkList implements List {
Node head; //頭指針
Node current;//當(dāng)前結(jié)點(diǎn)對(duì)象
int size;//結(jié)點(diǎn)個(gè)數(shù)
//初始化一個(gè)空鏈表
public LinkList()
{
//初始化頭結(jié)點(diǎn)，讓頭指針指向頭結(jié)點(diǎn)倔既。并且讓當(dāng)前結(jié)點(diǎn)對(duì)象等于頭結(jié)點(diǎn)。
this.head = current = new Node(null);
this.size =0;//單向鏈表，初始長度為零醇滥。
}
//定位函數(shù)黎比，實(shí)現(xiàn)當(dāng)前操作對(duì)象的前一個(gè)結(jié)點(diǎn)，也就是讓當(dāng)前結(jié)點(diǎn)對(duì)象定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)鸳玩。
//比如我們要在a2這個(gè)節(jié)點(diǎn)之前進(jìn)行插入操作阅虫，那就先要把當(dāng)前節(jié)點(diǎn)對(duì)象定位到a1這個(gè)節(jié)點(diǎn)，然后修改a1節(jié)點(diǎn)的指針域
public void index(int index) throws Exception
{
if(index <-1 || index > size -1)
{
throw new Exception("參數(shù)錯(cuò)誤不跟！");
}
//說明在頭結(jié)點(diǎn)之后操作颓帝。
if(index==-1) //因?yàn)榈谝粋€(gè)數(shù)據(jù)元素結(jié)點(diǎn)的下標(biāo)是0，那么頭結(jié)點(diǎn)的下標(biāo)自然就是-1了窝革。
return;
current = head.next;
int j=0;//循環(huán)變量
while(current != null&&j<index)
{
current = current.next;
j++;
}
}
@Override
public void delete(int index) throws Exception {
// TODO Auto-generated method stub
//判斷鏈表是否為空
if(isEmpty())
{
throw new Exception("鏈表為空购城，無法刪除！");
}
if(index <0 ||index >size)
{
throw new Exception("參數(shù)錯(cuò)誤虐译！");
}
index(index-1);//定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)對(duì)象工猜。
current.setNext(current.next.next);
size--;
}
@Override
public Object get(int index) throws Exception {
// TODO Auto-generated method stub
if(index <-1 || index >size-1)
{
throw new Exception("參數(shù)非法！");
}
index(index);
return current.getElement();
}
@Override
public void insert(int index, Object obj) throws Exception {
// TODO Auto-generated method stub
if(index <0 ||index >size)
{
throw new Exception("參數(shù)錯(cuò)誤菱蔬！");
}
index(index-1);//定位到要操作結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)對(duì)象。
current.setNext(new Node(obj,current.next));
size++;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size==0;
}
@Override
public int size() {
// TODO Auto-generated method stub
return this.size;
}
}
測試代碼
public class LinkListTest {
public static void main(String[] args) throws Exception {
LinkList list = new LinkList();
for (int i = 0; i < 10; i++) {
int temp = ((int) (Math.random() * 100)) % 100;
list.insert(i, temp);
System.out.print(temp + " ");
}
list.delete(4);
System.out.println("\n------刪除第五個(gè)元素之后-------");
for (int i = 0; i < list.size; i++) {
System.out.print(list.get(i) + " ");
}
}
}
測試代碼輸出
31 98 25 18 10 34 1 20 57 81
------刪除第五個(gè)元素之后-------
31 98 25 18 34 1 20 57 81
另外一種實(shí)現(xiàn)史侣，將節(jié)點(diǎn)類Node改為內(nèi)部類
/**
* 單向鏈表另外一種實(shí)現(xiàn)拴泌，將節(jié)點(diǎn)類Node改為內(nèi)部類
*
* @author adminjack
*
*/
public class LinkList2 {
private int size;
private Node root; // 定義一個(gè)根節(jié)點(diǎn)
private int foot = 0; // 操作返回?cái)?shù)組的腳標(biāo)
private String[] retData; // 返回?cái)?shù)組
private boolean changeFlag = true;
// changeFlag == true：數(shù)據(jù)被更改了，則需要重新遍歷
// changeFlag == false：數(shù)據(jù)沒有更改惊橱，不需要重新遍歷
// 添加數(shù)據(jù)
public boolean add(String data) {
if (data == null) { // 如果添加的是一個(gè)空數(shù)據(jù)蚪腐，那增加失敗
return false;
}
// 將數(shù)據(jù)封裝為節(jié)點(diǎn)，目的：節(jié)點(diǎn)有next可以處理關(guān)系
Node newNode = new Node(data);
// 鏈表的關(guān)鍵就在于根節(jié)點(diǎn)
if (root == null) { // 如果根節(jié)點(diǎn)是空的税朴，那么新添加的節(jié)點(diǎn)就是根節(jié)點(diǎn)回季。(第一次調(diào)用add方法時(shí)，根節(jié)點(diǎn)當(dāng)然是空的了)
root = newNode;
} else {
root.addNode(newNode);
}
this.size++;
return true;
}
// 方法：增加一組數(shù)據(jù)
public boolean addAll(String data[]) { // 一組數(shù)據(jù)
for (int x = 0; x < data.length; x++) {
if (!this.add(data[x])) { // 只要有一次添加不成功正林，那就是添加失敗
return false;
}
}
return true;
}
// 方法：刪除數(shù)據(jù)
public boolean remove(String data) { // 要?jiǎng)h除的節(jié)點(diǎn)泡一，假設(shè)每個(gè)節(jié)點(diǎn)的data都不一樣
if (!this.contains(data)) { // 要?jiǎng)h除的數(shù)據(jù)不存在
return false;
}
if (root != null) {
if (root.data.equals(data)) { // 說明根節(jié)點(diǎn)就是需要?jiǎng)h除的節(jié)點(diǎn)
root = root.next; // 讓根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)成為根節(jié)點(diǎn)，自然就把根節(jié)點(diǎn)頂?shù)袅寺铮ú幌駭?shù)組那樣觅廓，要將后面的數(shù)據(jù)在內(nèi)存中整體挪一位）
} else { // 否則
root.removeNode(data);
}
}
size--;
return true;
}
// 輸出所有節(jié)點(diǎn)
public void print() {
if (root != null) {
System.out.print(root.data);
root.printNode();
System.out.println();
}
}
// 方法：獲取全部數(shù)據(jù)
public String[] toArray() {
if (this.size == 0) {
return null; // 沒有數(shù)據(jù)
}
this.foot = 0; // 清零
this.retData = new String[this.size]; // 開辟數(shù)組大小
this.root.toArrayNode();
return this.retData;
}
// 獲取數(shù)據(jù)的長度
public int size() {
return this.size;
}
// 判斷是否為空鏈表
public boolean isEmpty() {
return this.size == 0;
}
// 清空鏈表
public void clear() {
this.root = null;
this.size = 0;
}
// 查詢數(shù)據(jù)是否存在
public boolean contains(String data) { // 查找數(shù)據(jù)
// 根節(jié)點(diǎn)沒有數(shù)據(jù)鼻忠，查找的也沒有數(shù)據(jù)
if (this.root == null || data == null) {
return false; // 不需要進(jìn)行查找了
}
return this.root.containsNode(data); // 交給Node類處理
}
// 方法：根據(jù)索引取得數(shù)據(jù)
public String get(int index) {
if (index > this.size) { // 超過個(gè)數(shù)
return null; // 返回null
}
this.foot = 0; // 操作foot來定義腳標(biāo)
return this.root.getNode(index);
}
// 定義一個(gè)節(jié)點(diǎn)內(nèi)部類（假設(shè)要保存的數(shù)據(jù)類型是字符串）
// 比較好的做法是，將Node定義為內(nèi)部類杈绸，在這里面去完成增刪帖蔓、等功能，然后由LinkList去調(diào)用增瞳脓、刪的功能
class Node {
private String data;
private Node next; // next表示：下一個(gè)節(jié)點(diǎn)對(duì)象（單鏈表中）
public Node(String data) {
this.data = data;
}
// 添加節(jié)點(diǎn)
public void addNode(Node newNode) {
// 下面這段用到了遞歸塑娇，需要反復(fù)理解
if (this.next == null) { // 遞歸的出口：如果當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)，說明我可以在這個(gè)節(jié)點(diǎn)后面添加新節(jié)點(diǎn)
this.next = newNode; // 添加新節(jié)點(diǎn)
} else {
this.next.addNode(newNode); // 向下繼續(xù)判斷劫侧，直到當(dāng)前節(jié)點(diǎn)之后沒有節(jié)點(diǎn)為止
}
}
// 判斷節(jié)點(diǎn)是否存在
public boolean containsNode(String data) { // 查找數(shù)據(jù)
if (data.equals(this.data)) { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)吻合
return true;
} else { // 與當(dāng)前節(jié)點(diǎn)數(shù)據(jù)不吻合
if (this.next != null) { // 還有下一個(gè)節(jié)點(diǎn)
return this.next.containsNode(data);
} else { // 沒有后續(xù)節(jié)點(diǎn)
return false; // 查找不到
}
}
}
// 刪除節(jié)點(diǎn)
public void removeNode(String data) {
if (this.next != null) {
if (this.next.data.equals(data)) {
this.next = this.next.next;
} else {
this.next.removeNode(data);
}
}
}
// 輸出所有節(jié)點(diǎn)
public void printNode() {
if (this.next != null) {
System.out.print("-->" + this.next.data);
this.next.printNode();
}
}
// 獲取全部數(shù)據(jù)
public void toArrayNode() {
LinkList2.this.retData[LinkList2.this.foot++] = this.data;
if (this.next != null) {
this.next.toArrayNode();
}
}
// 根據(jù)索引位置獲取數(shù)據(jù)
public String getNode(int index) {
if (LinkList2.this.foot++ == index) { // 當(dāng)前索引為查找數(shù)值
return this.data;
} else {
return this.next.getNode(index);
}
}
}
}
