分步解析 連結串列結構

語言: CN / TW / HK

分步解析

  1. 該類Node表示連結串列中的單個節點。它有兩個欄位:data,它儲存儲存在節點中的資料,和next,它是對列表中下一個節點的引用。

public class Node { int data; Node next; }

  1. 該類LinkedList表示連結串列資料結構。它有一個欄位 ,head它是對列表中第一個節點的引用。該類LinkedList還有幾個用於插入、刪除和顯示列表元素的方法。

``` public class LinkedList { Node head;

public void insertAtBeginning(int data) { // ... }

public void insertAtEnd(int data) { // ... }

public void insertAfter(Node prevNode, int data) { // ... }

public void deleteNode(int key) { // ... }

public void display() { // ... } } ```

  1. insertAtBeginning()方法在列表的開頭插入一個新節點。它建立一個新節點,將其data欄位設定為給定資料,並將其next欄位設定為列表的當前頭部。最後,它更新指向新節點的head欄位。LinkedList

public void insertAtBeginning(int data) { Node newNode = new Node(); newNode.data = data; newNode.next = head; head = newNode; }

  1. insertAtEnd()方法在列表末尾插入一個新節點。它建立一個新節點並將其data欄位設定為給定資料。如果列表為空,它會將 的head欄位設定LinkedList為新節點。否則,它遍歷列表找到最後一個節點並將其next欄位設定為新節點。

``` public void insertAtEnd(int data) { Node newNode = new Node(); newNode.data = data;

if (head == null) { head = newNode; return; }

Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; } ```

  1. insertAfter()方法在列表中的給定節點之後插入一個新節點。它檢查給定的前一個節點是否是null,如果是則返回。否則,它建立一個新節點,將其data欄位設定為給定資料,並將其next欄位設定next為前一個節點的欄位。然後它將next前一個節點的欄位設定為新節點。

``` public void insertAfter(Node prevNode, int data) { if (prevNode == null) { System.out.println("The given previous node cannot be null."); return; }

Node newNode = new Node(); newNode.data = data; newNode.next = prevNode.next; prevNode ```

  1. deleteNode()方法從列表中刪除一個節點。它首先將一個current節點設定head為列表的 ,將一個prev節點設定為null。如果該current節點不是null並且其data欄位與給定鍵匹配,則將其設定為該head節點的LinkedList節點並返回。否則,它將遍歷列表,直到找到具有與給定鍵匹配的欄位的節點,或者直到它到達列表的末尾。如果節點是,則表示在列表中未找到該鍵,因此它簡單地返回。否則,它將節點的欄位設定為節點的欄位,有效地從列表中刪除該節點。next``current``data``current``null``next``prev``next``current``current

``` public void deleteNode(int key) { Node current = head; Node prev = null;

if (current != null && current.data == key) { head = current.next; return; }

while (current != null && current.data != key) { prev = current; current = current.next; }

if (current == null) { return; }

prev.next = current.next; } ```

  1. display()方法顯示列表的元素。它只是遍歷列表並列印data每個節點的欄位。

public void display() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } }

  1. main()方法建立一個LinkedList物件並使用其方法插入、刪除和顯示列表的元素。

``` public static void main(String[] args) { LinkedList list = new LinkedList(); list.insertAtEnd(1); list.insertAtEnd(2); list.insertAtEnd(3); list.insertAtBeginning(0); list.insertAfter(list.head.next, 1.5); list.deleteNode(2);

list.display(); // 0 1 1.5 3 } ```

這是 Java 中連結串列的基本實現。這些方法可以進一步擴充套件以包括其他操作,例如使用給定鍵搜尋節點、反轉列表等。

  1. 使用連結串列的一個優點是它可以動態增長和收縮,這與具有固定大小的陣列不同。這意味著我們可以在列表中插入和刪除元素,而不用擔心空間不足或有未使用的空間。

  2. 使用連結串列的另一個優點是我們可以在常數時間 (O(1)) 內插入和刪除連結串列中間的元素,因為我們只需要更新節點之間的連結。相反,在陣列中間插入或刪除一個元素需要移動所有後續元素,這需要線性時間 (O(n))。

  3. 使用連結串列的缺點是節點之間的連結需要額外的記憶體。相反,陣列在記憶體中連續儲存元素,因此它不需要額外的記憶體來存放指標。

  4. 此外,通過索引訪問連結串列中的元素很慢,因為我們必須從頭遍歷列表到所需的索引。相比之下,陣列元素可以在常數時間 (O(1)) 內通過它們的索引直接訪問。

  5. 儘管有這些缺點,連結串列在某些情況下還是很有用的,比如當我們需要一個具有高效插入和刪除操作的動態資料結構時。

  6. 總之,連結串列是一種由一系列節點組成的資料結構,其中每個節點都包含一個數據欄位和指向列表中下一個節點的連結。連結串列可以動態增長和收縮,並提供高效的插入和刪除操作。然而,它們需要額外的記憶體用於節點之間的連結,並且它們通過索引訪問元素的速度很慢。**

本文正在參加「金石計劃 . 瓜分6萬現金大獎」