引入鏈表結構：

一：鏈表

1：結構：

?鏈表中的元素可以抽象為對象，每一個對象包含一個val值與next值，next就是指向下一個節點的地址。，這樣就實現了雖然物理上不連續，但是邏輯上實現了連續。

?

演示：?

?鏈表結構一共8中，分別是：

單向? 帶頭? 非循環? ? ?單向? 不帶頭? 非循環? ? ? ? ? ? ? 雙向? 不帶頭? 非循環? ?雙向? 不帶頭? 循環?

?單向? 帶頭? 循環? ? ? ?單向? 不帶頭? ? 循環? ? ? ? ? ? ??雙向? ? 帶頭? 非循環? ??雙向? ? 帶頭? ? ?循環?

2：實現：

?對鏈表的增刪該查方法進行手動實現：

將鏈表抽象為對象，每一個對象中都包含一個val值與next值，將val與next初始化為內部類的成員屬性，通過構造方法對傳輸的val值進行初始化，這樣傳輸的val值就帶有一個next屬性，成為了一個對象。

代碼解釋：?

? next?是一個指向同類對象的引用：

? ? ? 1： 它存儲內存中下一個節點對象的內存地址

? ? ? 2： 類型為 ListNode?表示它只能指向另一個 ListNode?類型的對象

? ? ? 3： 最后一個節點的?next?通常設為?null（表示鏈表結束）

? public?ListNode head;?的含義：

? 1：head：變量名，表示鏈表的頭節點（鏈表的起始點）

? ? ?2：返回ListNode對象，相當于這個head是一個ListNode對象，包含val屬性與next屬性（鏈? ? ? ? ? ? ? ?表由節點組成，頭節點是鏈表的起點）

? ListNode?作為返回類型意味著什么？

? ? 1：? 返回的是對ListNode?對象的引用（reference）

? ? 2 ： 引用本質上是對象的句柄，包含：

? ? ? ? ? ? ?2.1 對象的內存地址（但 Java 不直接暴露地址）

? ? ? ? ? ? ?2.2?通過引用可以訪問對象的完整狀態（字段）和行為（方法）

? ? ? 初始化對象：

? ? ? ? 當使用?new Node(value)?時：new?操作符在堆內存中分配空間創建新對象 → 生成新地址

? ? ? ?然后調用構造方法初始化對象狀態

? ? ? ?最后返回該對象的引用（地址）??

?

?2.1：創建一個鏈表

ListNode node=new ListNode（val）：?調用ListNode內部類，傳入val值，然后調用構造方法初始化對象，最后形成鏈表（對象）。

2.2：display（打印鏈表）

2.3：size（鏈表長度）?

逐一遍歷直到cur為null，也就是遍歷完最后一個節點，最后一個節點的next的節點為null時，停止遍歷，返回len。

2.4:findNodeOfKey(查找)

遍歷cur，直到cur的val為key時，返回cur。

圖示：?

2.5： remove（刪除一個指定元素）

首先保證存在鏈表，如果要刪除的key值為頭節點，然后使head節點指向下一個節點，如果不是頭節點則執行邏輯代碼，先找到要刪除節點的前一個節點，然后del保存為要刪除節點的下一個節點，使cur.next指向要刪除節點的下一個節點，這樣要刪除的節點直接被跳過了。

圖示展示：?

2.6：removeAllKey（刪除所有為key值的節點）

如果要刪除的節點正好是head節點指向的下一個節點，那么執行if語句，刪除（跳過）這個節點，使head指向它的next.next的節點，然后prev指向此時的cur，也就是被跳過的節點，然后cur指向cur的下一個節點，循環執行，如果要刪除的節點包含頭節點，那么最后刪除（跳過）頭節點，最后處理，不要先處理。

?

2.7：clear（刪除所有節點）

刪除所有節點可以直接將head==null這樣鏈表就沒有了頭，其他節點也就自動被清理了。

也可以一個一個的將節點置為null。

?2.8：addFirst（頭插）

將傳輸的data初始化為節點對象，調用構造方法，生成node對象，然后將node的下一個節點指向head節點，此時head節點使第二個節點，最后再將head置為第一個節點指向node。

2.9：addLast（尾插法）?

同理，生成node對象，先遍歷到最后一個節點，然后將node插入到最后，此時cur==null，然后將cur.next=node，這樣就再最后插入了node。

2.10：addIndext（在任意位置插入）?

首先確保插入位置合法，不超過鏈表的長度，也不為負數，也就是在index位置插入data值，那么cur需要走到index節點的前一個節點，也就是要走index-1步

2.11：contain（包含某個節點）?

遍歷cur，從頭節點開始，直到找到key的值，找到返回true，沒有找到返回false

物理連續與邏輯連續：

• 物理存儲結構：指的是數據元素（節點）實際在計算機內存（或存儲介質）中占據的位置。

  • • 物理上連續的存儲結構：?最典型的例子就是數組。

      • 如何連續：?當你創建一個數組（例如?int arr[10];）時，操作系統或運行環境會在內存中找出一塊連續的空閑區域，大小剛好能容納10個整數（假設每個int占4字節，就是40字節的連續空間）。

      • 地址關系：?數組的第一個元素?arr[0]?占據某個起始地址（比如?0x1000），那么?arr[1]?緊挨著它，地址是?0x1004（假設int是4字節），arr[2]?在?0x1008，以此類推，直到?arr[9]?在?0x1024。這些元素的內存地址在數值上是連續的、緊密相鄰的。

      • 特點：?知道第一個元素的地址和每個元素的大小，就能通過簡單的算術運算（起始地址 + 索引 * 元素大小）直接計算出任何一個元素的物理地址，實現快速隨機訪問（O(1)時間復雜度）。

    • 物理上非連續的存儲結構：?最典型的例子就是鏈表。

      • 如何非連續：?當你創建鏈表的節點時，每次創建一個新節點（Node），系統只是在當前可用的任意空閑內存位置分配空間給這個節點。它完全不關心之前創建的節點或之后將要創建的節點在內存的哪個位置。

      • 地址關系：?假設鏈表有3個節點 A、B、C，邏輯順序是 A -> B -> C。

        • 節點 A 可能被分配到地址?0x2000。

        • 節點 B 可能被分配到地址?0x5000（很遠，與 A 不連續）。

        • 節點 C 可能又被分配到?0x3000（在 A 和 B 之間，也不連續）。

        • 這些節點的內存地址在數值上沒有任何規律，是隨機分散在內存中的，彼此之間不是緊挨著的。

      • 特點：?你無法通過起始地址和索引計算出某個節點的物理地址。節點的物理位置是隨機的。