java數據結構基礎:單鏈表與雙向鏈表

Posted on by

單鏈表：

每個數據是以節點的形式存在的

每個節點分為數據域和指針域

數據域中保存該節點的數據

指針域中保存指向下一個節點的指針

實現思路：

節點類SingleNode中保存數據和指向下一個節點的指針

單鏈表類SingleLinkedList中保存鏈表的頭節點，實現相關鏈表方法

對於鏈表方法，涉及到位置查找，如在指定位置增加、刪除節點，需要使用一個臨時變量temp從頭節點開始遍歷，直至找到對應的位置。

對於節點的增加刪除，隻需要修改相關結點的指針指向即可

代碼實現：

節點類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);
    //獲取頭結點
	public SingleNode getHead(){
		return head;
	}
	//添加節點
	public void add(SingleNode singleNode) {
		SingleNode temp = head;
		//找到鏈表最後一個節點
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = singleNode;
	}
	//按順序添加節點
	public void addByOrder(SingleNode singleNode) {
		SingleNode temp = head;
		while (true) {
			if (temp.next == null) {
				//已經遍歷到鏈表最後瞭
				break;
			} else if (temp.next.data > singleNode.data) {
				//找到應插入的位置
				break;
			}
			temp = temp.next;
		}
		singleNode.next = temp.next;
		temp.next = singleNode;
	}
	//刪除節點
	public void delete(int data) {
		SingleNode temp = head;
		boolean flag = false;    //標志是否找到待刪除節點的前一個節點
		while (true) {
			if (temp.next == null) {
				//已經遍歷到鏈表最後瞭
				break;
			} else if (temp.next.data == data) {
				//找到待刪除節點的前一個節點
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.next = temp.next.next;
		} else {
			System.out.println("要刪除的節點不存在");
		}
	}
	//輸出鏈表
	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;
		}
	}
}

雙向鏈表：

每個節點中除瞭保存瞭指向後一個節點的指針外，還保存瞭指向前一個節點的指針

實現思路：

相關方法實現與單鏈表類似，不同點在於需要增加對指向前一個節點的指針的更改

代碼實現：

節點類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);
	//獲取頭結點
	public DoubleNode getHead() {
		return head;
	}
	//添加節點
	public void add(DoubleNode doubleNode) {
		DoubleNode temp = head;
		//找到鏈表最後一個節點
		while (temp.next != null) {
			temp = temp.next;
		}
		temp.next = doubleNode;
		doubleNode.pre = temp;
	}
	//刪除節點
	public void delete(int data) {
		DoubleNode temp = head.next;
		boolean flag = false;    //標志是否找到待刪除節點的前一個節點
		while (true) {
			if (temp == null) {
				//已經遍歷到鏈表最後瞭
				break;
			} else if (temp.data == data) {
				//找到待刪除節點
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.pre.next = temp.next;
			if (temp.next != null) {
				//若刪除節點不為最後一個節點
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.println("要刪除的節點不存在");
		}
	}
	//輸出鏈表
	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;
		}
	}
}

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：