java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單鏈表與雙向鏈表

更新時間：2021年08月01日 10:58:51 作者：去吧貓頭夜鷹

這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)單鏈表、雙向鏈表的相關(guān)資料，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

單鏈表：

每個數(shù)據(jù)是以節(jié)點(diǎn)的形式存在的

每個節(jié)點(diǎn)分為數(shù)據(jù)域和指針域

數(shù)據(jù)域中保存該節(jié)點(diǎn)的數(shù)據(jù)

指針域中保存指向下一個節(jié)點(diǎn)的指針

實(shí)現(xiàn)思路：

節(jié)點(diǎn)類SingleNode中保存數(shù)據(jù)和指向下一個節(jié)點(diǎn)的指針

單鏈表類SingleLinkedList中保存鏈表的頭節(jié)點(diǎn)，實(shí)現(xiàn)相關(guān)鏈表方法

對于鏈表方法，涉及到位置查找，如在指定位置增加、刪除節(jié)點(diǎn)，需要使用一個臨時變量temp從頭節(jié)點(diǎn)開始遍歷，直至找到對應(yīng)的位置。

對于節(jié)點(diǎn)的增加刪除，只需要修改相關(guān)結(jié)點(diǎn)的指針指向即可

代碼實(shí)現(xiàn)：

節(jié)點(diǎn)類SingleNode：

public class SingleNode {
	public int data;
	public SingleNode next;
	public SingleNode(int data) {
		this.data = data;
	}
	@Override
	public String toString() {
		return "SingleNode{" + "data=" + data + '}';
	}
}

單鏈表類SingleLinkedList：

public class SingleLinkedList {
	private SingleNode head = new SingleNode(0);
    //獲取頭結(jié)點(diǎn)
	public SingleNode getHead(){
		return head;
	}
	//添加節(jié)點(diǎn)
	public void add(SingleNode singleNode) {
		SingleNode temp = head;
		//找到鏈表最后一個節(jié)點(diǎn)
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = singleNode;
	}
	//按順序添加節(jié)點(diǎn)
	public void addByOrder(SingleNode singleNode) {
		SingleNode temp = head;
		while (true) {
			if (temp.next == null) {
				//已經(jīng)遍歷到鏈表最后了
				break;
			} else if (temp.next.data > singleNode.data) {
				//找到應(yīng)插入的位置
				break;
			}
			temp = temp.next;
		}
		singleNode.next = temp.next;
		temp.next = singleNode;
	}
	//刪除節(jié)點(diǎn)
	public void delete(int data) {
		SingleNode temp = head;
		boolean flag = false;    //標(biāo)志是否找到待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
		while (true) {
			if (temp.next == null) {
				//已經(jīng)遍歷到鏈表最后了
				break;
			} else if (temp.next.data == data) {
				//找到待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.next = temp.next.next;
		} else {
			System.out.println("要刪除的節(jié)點(diǎn)不存在");
		}
	}
	//輸出鏈表
	public void show() {
		//判斷鏈表是否為空
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		SingleNode temp = head.next;
		while (temp != null) {
			System.out.println(temp);
			temp = temp.next;
		}
	}
}

雙向鏈表：

每個節(jié)點(diǎn)中除了保存了指向后一個節(jié)點(diǎn)的指針外，還保存了指向前一個節(jié)點(diǎn)的指針

實(shí)現(xiàn)思路：

相關(guān)方法實(shí)現(xiàn)與單鏈表類似，不同點(diǎn)在于需要增加對指向前一個節(jié)點(diǎn)的指針的更改

代碼實(shí)現(xiàn)：

節(jié)點(diǎn)類DoubleNode：

public class DoubleNode {
	public int data;
	public DoubleNode next;
	public DoubleNode pre;
	public DoubleNode(int data) {
		this.data = data;
	}
	@Override
	public String toString() {
		return "DoubleNode{" + "data=" + data + '}';
	}
}

雙向鏈表類DoubleLinkedList：

public class DoubleLinkedList {
	public DoubleNode head = new DoubleNode(0);
	//獲取頭結(jié)點(diǎn)
	public DoubleNode getHead() {
		return head;
	}
	//添加節(jié)點(diǎn)
	public void add(DoubleNode doubleNode) {
		DoubleNode temp = head;
		//找到鏈表最后一個節(jié)點(diǎn)
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = doubleNode;
		doubleNode.pre = temp;
	}
	//刪除節(jié)點(diǎn)
	public void delete(int data) {
		DoubleNode temp = head.next;
		boolean flag = false;    //標(biāo)志是否找到待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
		while (true) {
			if (temp == null) {
				//已經(jīng)遍歷到鏈表最后了
				break;
			} else if (temp.data == data) {
				//找到待刪除節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.pre.next = temp.next;
			if (temp.next != null) {
				//若刪除節(jié)點(diǎn)不為最后一個節(jié)點(diǎn)
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.println("要刪除的節(jié)點(diǎn)不存在");
		}
	}
	//輸出鏈表
	public void show() {
		//判斷鏈表是否為空
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		DoubleNode temp = head.next;
		while (temp != null) {
			System.out.println(temp);
			temp = temp.next;
		}
	}
}