順序表的優(yōu)缺點

缺點：

• 中間/頭部的插入刪除，時間復雜度效率較低，為O(N)

• 空間不夠的時候需要擴容。

  • 如果是異地擴容，增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間，會有不小的消耗。

• 擴容可能會存在空間浪費。

  • 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。

優(yōu)點：

• 尾差尾刪足夠快。
• 下標的隨機訪問和修改足夠快。

鏈表的初步認知

針對順序表的缺點，鏈表就被設計出來了。
鏈表的特點即，按需申請釋放。
當我們需要一塊空間時，我們就申請一塊空間。當我們需要添加數(shù)據(jù)時，就繼續(xù)增加一個一個小塊。
主要是就是一個一個小塊之間的連接。為了方便連接和管理，每一個結(jié)點中都存有一個指針，用于指向下一個結(jié)點。正式一個一個“鏈接”起來，所以叫做鏈表。

下面圖中主要標識了順序表和鏈表的邏輯結(jié)構(gòu)的不同。
對于順序表，我們只需要知道指向這塊內(nèi)存空間的指針即可。
但是對于鏈表，我們僅僅知道指向第一塊內(nèi)存空間的指針是不夠的，因為一塊與一塊之間沒有連接。所以對于每一塊，都必須存有指向下一塊空間的指針。

定義單鏈表的結(jié)構(gòu)

鏈表的邏輯圖：

鏈表的物理圖：

//Single List Table
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//SLTNode* next 是不可以的
}SLTNode;

下面，我們再來寫一個打印單鏈表的的函數(shù)。

void PrintSList(SLTNode* phead)
{SLTNode* p = phead;while (p != NULL){printf("%d ", p->data);p=p->next;}printf("NULL\n");
}

然后，接下來，我們再來在主函數(shù)中自己建一個單鏈表，其實也就是開辟幾個結(jié)點的空間，然后使得結(jié)點之間可以“鏈接”起來即可。

int main()
{SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));n1->data = 1;SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));n2->data = 2;SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));n3->data = 3;n1->next = n2;n2->next = n3;n3->next = NULL;PrintSList(n1);
}

由上圖，我們可以知道代碼的邏輯。

• 動態(tài)分配內(nèi)存，創(chuàng)建3個 SLTNode 類型的節(jié)點，并將其地址賦值給指針 n1、n2、n3。
• 然后將3個結(jié)點的next字段都賦值。
• 然后將鏈表鏈接起來。
  • n1->next = n2;將節(jié)點 n1 的 next 指針指向節(jié)點 n2，表示 n1 的下一個節(jié)點是 n2。
  • n2->next = n3;將節(jié)點 n2 的 next 指針指向節(jié)點 n3，表示 n2 的下一個節(jié)點是 n3。
  • n3->next = NULL;將節(jié)點 n3 的 next 指針設置為 NULL，表示鏈表到此結(jié)束。
• 最后打印鏈表。

我們進行逐語句調(diào)試，在監(jiān)視窗口中觀察n1,n2,n3的變化。

我們可以看出來，n1、n2 和 n3 的物理地址并不連續(xù)。
根據(jù)結(jié)構(gòu)體的定義，我們可以計算出結(jié)構(gòu)體的大小。

如果內(nèi)存連續(xù)，地址應該是：

而根據(jù)我們的監(jiān)視信息，并非連續(xù)，這正是因為在代碼中使用了 malloc 動態(tài)分配內(nèi)存。
malloc 從堆中分配內(nèi)存，而堆內(nèi)存的分配通常是非連續(xù)的，具體取決于系統(tǒng)內(nèi)存分配器的實現(xiàn)和當前堆內(nèi)存的使用情況。因此，動態(tài)分配的內(nèi)存塊通常在物理地址上是分散的。

---

---

這一篇小博客，我們認識鏈表，下面我們將接著實現(xiàn)鏈表。
加油！