如何學linkedList算法

159次閱讀

沒有評論

共計 2130 個字符，預計需要花費 6 分鐘才能閱讀完成。

這篇文章將為大家詳細講解有關如何學 linkedList 算法，文章內容質量較高，因此丸趣 TV 小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

簡介

linkedList 應該是一種非常非常簡單的數據結構了。節點一個一個的連接起來，就成了 linkedList。今天我們使用動畫的方法一起來看看 linkedList 是怎么插入和刪除的。

linkedList 的構建

linkedList 是由一個一個的節點構成的。而每個節點只需要存儲要保存的數據和下一個節點的引用即可。

linkedList 本身需要一個 head 節點，所以我們的 linkedList 可以這樣構建：

public class LinkedList {
 Node head; // head  節點
 //Node 表示的是 Linked list 中的節點，包含一個 data 數據和下一個節點的引用
 class Node {
 int data;
 Node next;
 //Node 的構造函數
 Node(int d) {
 data = d;
 }
 }
}

linkedList 的操作

先看一下 linkedList 怎么插入數據，插入數據有三種方式，頭部插入，尾部插入，中間插入。

頭部插入

先看一個頭部插入的例子：

頭部插入的邏輯是什么呢？

新插入的節點作為 head 節點，然后將原來的 head 節點指向當前 head 節點的 next 引用即可。

// 插入到 linkedList 的頭部
 public void push(int newData) {
 // 構建要插入的節點
 Node newNode = new Node(newData);
 // 新節點的 next 指向現在的 head 節點
 newNode.next = head;
 // 現有的 head 節點指向新的節點
 head = newNode;
 }

尾部插入

再看一下尾部插入的例子：

插入的邏輯是什么呢？

找到最后一個節點，然后將最后一個節點的 next 指向新插入的節點。

// 新節點插入到 list 最后面
 public void append(int newData) {
 // 創建新節點
 Node newNode = new Node(newData);
 // 如果 list 是空，則新節點作為 head 節點
 if (head == null) {
 head = newNode;
 return;
 }
 newNode.next = null;
 // 找到最后一個節點
 Node last = head;
 while (last.next != null) {
 last = last.next;
 }
 // 插入
 last.next = newNode;
 return;
 }

中間插入

再看一下中間插入的例子：

這個例子中，我們在第三個節點的位置插入了一個 93。

插入邏輯就是先找到第二個節點，將第二個節點的 next 指向新節點，然后將新節點的 next 指向原先的第三個節點。

看下 java 代碼如何實現：

// 插入在第幾個元素之后
 public void insertAfter(int index, int newData) {
 Node prevNode = head;
 for (int i = 1; i   index; i++) { if (prevNode == null) {
 System.out.println( 輸入的 index 有誤，請重新輸入 
 return;
 }
 prevNode = prevNode.next;
 }
 // 創建新的節點
 Node newNode = new Node(newData);
 // 新節點的 next 指向 prevNode 的下一個節點
 newNode.next = prevNode.next;
 // 將新節點插入在 prevNode 之后
 prevNode.next = newNode;
 }

刪除節點

再看一下怎么刪除某個位置的節點：

上面的例子中，我們要刪除第 5 個節點。

刪除的邏輯就是找到第 4 個節點和第 6 個節點。然后將第四個節點的 next 指向第 6 個節點即可。

看下相應的 java 代碼如下：

// 刪除特定位置的節點
 void deleteNode(int index)
 {
 //  如果是空的，直接返回
 if (head == null)
 return;
 // head 節點
 Node temp = head;
 //  如果是刪除 head 節點
 if (index == 1)
 {
 head = temp.next;
 return;
 }
 //  找到要刪除節點的前一個節點
 for (int i=1; temp!=null   i index-1; i++)
 temp = temp.next;
 //  如果超出范圍
 if (temp == null || temp.next == null)
 return;
 // temp- next  是要刪除的節點，刪除節點
 Node next = temp.next.next;
 temp.next = next;
 }

關于如何學 linkedList 算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

正文完