本節介紹鏈表

目錄

1.什么是鏈表

1.1鏈表定義

1.2鏈表分類

2.鏈表實現

2.1創建鏈表

1）手動創建

2）創建鏈表類進行管理鏈表的相關操作

2.2添加元素

1）頭插法

2）尾插法

3）任意位置插入

2.3刪除

2.4查找

1）返回節點

2）返回索引

---

1.什么是鏈表

1.1鏈表定義

鏈表是一種數據結構，它由一系列節點組成。每個節點包含至少兩部分信息：數據域（用于存儲數據元素）和指針域（用于存儲指向下一個節點的引用或地址）。鏈表通過節點之間的指針連接，形成一個鏈式結構。

與數組不同：1.數組中的元素在內存中是連續存儲的，而鏈表的節點在內存中的存儲位置不一定是連續的。2.鏈表它在插入和刪除操作上相對數組更加靈活

1.2鏈表分類

• 單向鏈表：也稱為單鏈表，是最基本的鏈表形式。每個節點只包含一個指向下一個節點的指針，只能從鏈表的頭節點開始，沿著指針依次訪問后續節點，無法反向遍歷。
• 雙向鏈表：在雙向鏈表中，每個節點除了有一個指向后繼節點的指針外，還有一個指向前驅節點的指針。這使得雙向鏈表可以在兩個方向上進行遍歷，既可以從頭節點向后遍歷，也可以從尾節點向前遍歷。
• 循環鏈表：循環鏈表又分為單向循環鏈表和雙向循環鏈表。單向循環鏈表的尾節點的指針指向頭節點，形成一個環形結構，這樣可以從任意一個節點出發，遍歷整個鏈表。雙向循環鏈表則是頭節點的前驅指針指向尾節點，尾節點的后繼指針指向頭節點，同樣實現了環形的結構，提供了更靈活的遍歷方式。

2.鏈表實現

2.1創建鏈表

1）手動創建

即自己創建一個node類然后調用

package com.qcby;public class Node {Node next;int value;public static void main(String[] args) {Node node1 = new Node();node1.value = 1;Node node2 = new Node();node2.value = 2;node1.next = node2;System.out.println(node1.value);System.out.println(node1.toString());}public String toString() {return "Node[" +"next=" + next +", value=" + value +']';}
}

2）創建鏈表類進行管理鏈表的相關操作

使用?LinkList list = new LinkList();?創建鏈表

2.2添加元素

1）頭插法

頭插法就是每次有一個新的元素進入鏈表時，將新節點插入到鏈表的頭部，使其成為新的頭節點。

代碼如下：

	public void addHead(int value) {Node node=new Node(value);if(head==null) {head=node;return;}node.next=head;head=node;}

2）尾插法

當每次鏈表接受新的元素時，將新節點插入到鏈表的尾部，使其成為新的尾節點。

代碼如下：

public void add(int data) {Node node = new Node();node.value = data;if (head == null) {head = node;} else {Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}}

3）任意位置插入

在接收到新元素時，給新元素的位置做規定，即任意位置插入是將新節點插入到鏈表的指定位置。

代碼：

public void addIndex(int index, int data) {Node node = new Node();node.value = data;if (index < 0 || index > getLength()) {System.out.println("超出范圍");return;}if (index == 0) {addHead(data);} else {Node temp = head;for (int i = 0; i < index - 1; i++) {temp = temp.next;}node.next = temp.next;temp.next = node;}}

注意：想要實現任意位置插入，需要關注其鏈表長度，防止該插入位置比鏈表長度大出現問題

即實現一個求解長度的類，主要是通過遍歷鏈表節點來記錄長度：

    public int getLength() {int length = 0;Node temp = head;while (temp != null) {length++;temp = temp.next;}return length;}

2.3刪除

public void remove(int data) {if (head == null) {System.out.println("鏈表為空");return;}if (head.value == data) {head = head.next;return;}Node temp = head;while (temp.next != null) {if (temp.next.value == data) {temp.next = temp.next.next;return;}temp = temp.next;}}

2.4查找

1）返回節點

    public Node find(int data) {Node temp = head;while (temp != null) {if (temp.value == data) {return temp;}temp = temp.next;}return null;}

2）返回索引

    public int findIndex(int data) {Node temp = head;int index = 0;while (temp != null) {if (temp.value == data) {return index;}temp = temp.next;index++;}return -1;}