P3 鏈表的基本介紹

1. 【數(shù)組線性表的內(nèi)存使用】使用數(shù)組來實現(xiàn)動態(tài)列表，就內(nèi)存利用率和消耗量而言，它不是最有效的。在學習鏈表之前我們有必要了解數(shù)組使用的限制。
   ?

   鏈表：基本介紹 P3 - 01:09

   ?

• 計算機中管理內(nèi)存的東西叫內(nèi)存管理器
• 一個字節(jié)一個內(nèi)存空間，int類型是四個字節(jié)，一個int元素需要4個內(nèi)存空間，這個內(nèi)存塊的地址是內(nèi)存中第一個字節(jié)的地址。
• 計算機訪問數(shù)組中任一元素的時間成本是恒定的：O(1)，只要知道首地址和訪問元素在表中的位置，通過就可以知道地址直接訪問

• 數(shù)組是作為一個連續(xù)的內(nèi)存塊存儲在內(nèi)存中

• 當滿元素的數(shù)組要插入新元素，需要創(chuàng)建新的更大的數(shù)組，復制舊內(nèi)容并放入新內(nèi)容，還要釋放舊數(shù)組的內(nèi)存空間。

2.【先看看鏈表是如何解決這個問題的】

• 0是無效地址，即null，不指向任何節(jié)點
• 指針變量需要4個字節(jié)
• 指向節(jié)點的指針
• 我們始終保持的關(guān)于列表的唯一信息是頭節(jié)點的地址
• tips：課本里的頭節(jié)點不是指第一個節(jié)點，而是一個空數(shù)據(jù)的，next指向第一個節(jié)點的特殊節(jié)點：

• 訪問鏈表的某個元素，只能從頭開始一個一個的找，因此時間成本不是恒定的，會和列表的大小成正比，假設(shè)列表大小和元素都是n，最壞情況下，遍歷所有元素，時間復雜度O(n)
• 好處是插入操作不需要復制，可以按需創(chuàng)建和釋放節(jié)點，不必猜測列表大小

P4 數(shù)組和鏈表優(yōu)缺點對比

實際上不存在一個數(shù)據(jù)結(jié)構(gòu)要好于另一個數(shù)據(jù)結(jié)構(gòu)的說法，根據(jù)需求選擇最優(yōu)解，比如與這個數(shù)據(jù)結(jié)構(gòu)相關(guān)的最頻繁的操作，數(shù)據(jù)量的大小等因素。

本節(jié)通過對比，了解什么情況下使用數(shù)據(jù)和鏈表較好（注：這里的討論的鏈表是經(jīng)典結(jié)構(gòu)，沒有包括循環(huán)鏈表等結(jié)構(gòu)）

1. 【訪問元素的成本】

如果你有一個需要始終訪問列表中元素的要求，選數(shù)組更好

2.【內(nèi)存的使用】

• 數(shù)組

優(yōu)：

缺：

1）當數(shù)組被創(chuàng)建時，它占用的內(nèi)存就是固定的

2）會存在某些空間沒被使用

3）當插入的數(shù)據(jù)溢出時，還要新建，復制，消耗更多的時間成本

4）當我們可能想創(chuàng)建一個非常非常大的數(shù)組時，可能沒有那么大的一塊連續(xù)的內(nèi)存

• 鏈表

優(yōu)：

1）占用的內(nèi)存可變

2）沒有未使用的內(nèi)存

缺：

1）指針變量會占用額外的內(nèi)存，但是不同情況不同利弊：

a.當data數(shù)據(jù)部分是簡單的數(shù)據(jù)類型，占用內(nèi)存少，那么隨著數(shù)據(jù)量增加，相比數(shù)組，鏈表會使用更多的內(nèi)存。

b.當data數(shù)據(jù)部分是復雜的數(shù)據(jù)類型，占用的字節(jié)比指針大得多，那么相比數(shù)組，鏈表對內(nèi)存的使用效率會更高。

3.【插入元素的時間成本】

1）在列表的開頭插入元素

數(shù)組：將每個元素向后移動一個位置，花費時間與列表大小成正比：O(n)

鏈表：創(chuàng)建新節(jié)點，next指向舊的第一個節(jié)點，頭指針指向新節(jié)點。時間成本是恒定的：O(1)

2）在數(shù)組末尾插入元素

數(shù)組：如果數(shù)組未滿，只需要寫到列表的下一個更高的索引，時間復雜度恒定O(1)；如果數(shù)組已滿，得創(chuàng)建新數(shù)組并復制先前內(nèi)容，時間復雜度O(n)，n為列表大小

鏈表：需要遍歷整個列表，找到最后一個元素的位置才能將創(chuàng)建的新節(jié)點鏈接在后面，時間復雜度為O(n)，n為列表元素數(shù)量

3）在列表的第 i 個中間位置插入

數(shù)組：平均情況下，插在n/2的位置，也就要移位n/2，n為列表元素數(shù)量，時間復雜度為O(n)

鏈表：也必須遍歷到該位置才能做調(diào)整，時間復雜度為O(n)

Tips：刪除操作也會有這三種情況，時間復雜度也和插入一樣

4.【哪個使用更簡單】

數(shù)組：更容易實現(xiàn)和使用

鏈表：在C或C++中“實現(xiàn)”時更容易出錯，比如段錯誤和內(nèi)存泄漏

P5 鏈表：C/C++實現(xiàn)

前提是要有一些使用C/C++指針的經(jīng)驗并了解動態(tài)內(nèi)存分配的概念，這里的推薦課程：https://www.bilibili.com/video/BV1bo4y1Z7xf/

1.【邏輯視圖】

也可以解釋為鏈表的名稱

• tips：課本里的頭節(jié)點不是指第一個節(jié)點，而是一個空數(shù)據(jù)的，next指向第一個節(jié)點的特殊節(jié)點：

2.【代碼實現(xiàn)】

定義（整型鏈表）

如果你是C++

課本里typedef struct Node{ ... }LNode，*linklist；這段的意思是給Node類型變量和Node*類型指針起了個別名，使用時LNode和Node不做區(qū)分，當用戶聲明指針時可以寫linklist head；就不用多寫個*號（我覺得沒什么意義），聲明時一定要用typedef。

遍歷

末尾插入

tips：頭指針（A）一般不應該被改變

P6 鏈表：頭插入實現(xiàn)