前言
今天給小伙伴們分享的是在數據結構中順序表和鏈表的對比。它們在計算機科學和軟件開發中具有廣泛的應用，是理解更復雜數據結構（如棧、隊列、樹、圖等）的基礎。這次將會給大家從定義初始化，以及功能增刪查改上進行詳細對比，以便于大家掌握并使用。那讓咱們開始吧@
一.基本知識概述
考慮到可能有些小伙伴還沒了解到順序表或鏈表，就先概述一下關于它們的基本知識。
1.順序表
順序表（Sequential List）是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構。一般是使用數組方式實現，它的元素在內存中是連續存儲的。順序表是數據結構中最基礎的一種線性表，具有高效的隨機訪問特性，但在插入和刪除操作上效率較低。
2.鏈表
鏈表(Linked List)? 是一種在物理存儲結構上非連續、非順序的存儲結構，又因為在節點結構和操作上不同分有（雙鏈表還細分是否循環與是否帶哨兵位頭節點）：雙鏈表（Doubly Linked List）和單鏈表（Singly Linked List）。鏈表與順序表不同，它是靠指針鏈接實現的，順序表的元素在內存中是連續存儲的，而鏈表的元素可以分散在內存的任何位置。因此它在插入和刪除上效率比順序表更高些。
二.定義及初始化
1.順序表
順序表通常由以下部分組成：
-
數據存儲區：
一個數組(需要考慮數據大小，是否需要自主開辟空間和擴容），用于存儲元素。 -
長度信息：
一個變量，用于記錄當前順序表中元素的數量
靜態順序表
（靜態的意思是存儲空間有限）首先定義一個結構體，然后在結構體里再定義一個數組以及一個整型變量來顯示順序表長度，不知道數據具體大小的時候，使用起來比較麻煩，容易產生數組越界以及空間浪費問題，這里推薦使用動態的順序表。
#define MAX_SIZE 100 // 定義一個能容納所有數據的容量，這個屬于靜態順序表了，不易把控使用空間//一般推薦大家使用動態順序表typedef struct SequentialList
{int data[MAX_SIZE]; // 數據存儲區int length; // 當前順序表的長度
} SL;靜態順序表的初始化比較簡單，只需初始化長度即可
void InitList(SL* ps)
{L->length = 0; // 初始化長度為 0
}動態順序表
動態順序表則在空間使用上更加靈活，使用數組指針，通過?malloc 函數開辟所需空間，如果不夠再使用realloc 函數進行擴容，但是需考慮內存泄漏問題，以及后續使用完空間的釋放問題。
typedef int SLDataType; //定義數組類型，方便存儲各種類型不同的數據#define INIT_CAPACITY 4 //定義一個空間容量，方便后續擴容// 動態順序表 -- 按需申請
typedef struct SequentialList
{SLDataType* a;int size; // 有效數據個數int capacity; // 空間容量
}SL;對比于靜態順序表，動態順序表初始化則較為復雜一點
（擴容函數的使用放在數據插入，不夠再擴，節省空間）
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY); 通過malloc 函數開辟空間if (ps->a == NULL)//若開辟失敗，返回錯誤信息{perror("malloc fail"); return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}2.鏈表
鏈表的話則是通過結構體指針來實現，單鏈表和雙鏈表的定義差不多，主要區別在節點指針的數量及指向方向。雙鏈表較于單鏈表，支持雙向遍歷，增刪數據更加靈活，但在空間效率上略低于單鏈表，因為它有兩個節點指針，并且在維護時需要調整兩個指針，容易出錯。
1.?單鏈表（Singly Linked List）
-
節點結構：
-
每個節點包含兩個部分：
-
數據域：存儲數據。
-
指針域：指向下一個節點的指針。
-
-
-
鏈表結構：
-
鏈表由一系列節點組成，每個節點通過指針連接。
-
鏈表的最后一個節點的指針域為?
NULL，表示鏈表的結束。
-
typedef int SLTDataType; 定義數據類型，方便后續適用于存儲各種類型數據typedef struct SListNode
{SLTDataType data; struct SListNode* next; 指向下一個節點
}SLTNode;
單鏈表的初始化通過節點創造函數創建了一個節點并賦初值，然后把節點指針傳遞回插入函數(下期會詳細介紹）
SLTNode* CreatSLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //創建節點if (newnode == NULL){perror("malloc fail"); //若開辟失敗，則返回錯誤信息return NULL;}newnode->data = x;newnode->next = NULL; //避免出現野指針return newnode; //返回節點指針到插入函數
}2.?雙鏈表（Doubly Linked List）
-
節點結構：
-
每個節點包含三個部分：
-
數據域：存儲數據。
-
前驅指針：指向前一個節點的指針。
-
后繼指針：指向下一個節點的指針。
-
-
-
鏈表結構：
-
鏈表由一系列節點組成，每個節點通過前驅指針和后繼指針連接。
-
鏈表的第一個節點的前驅指針為?
NULL，最后一個節點的后繼指針為?NULL。
-
雙鏈表的定義則比單鏈表多一個指針，于是便有了訪問上一個節點的功能
typedef int LTDataType; 定義數據類型，方便后續適用于存儲各種類型數據typedef struct ListNode
{struct ListNode* next; 指向下一個節點指針struct ListNode* prev; 指向上一個節點指針LTDataType data;
}SL;雙鏈表的初始化跟單鏈表差不多，多了一個回訪指針的初始化。
SL* CreatSListNode(LTDataType x)
{SL* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");//return NULL;exit(-1);//調用 exit 函數以非零狀態終止程序。}node->next = NULL;node->prev = NULL;//回訪指針，指向上一個節點node->data = x;return node;
}
在這里呢，再提一下帶哨兵位（sentinel node）頭節點的雙鏈表。先解釋一下什么是哨兵位節點（sentinel node）吧。
哨兵節點（sentinel node）是一種特殊的結點，它可以簡化鏈表中的操作，減少邊界條件的判斷和特殊處理，假如用它作頭節點，在進行鏈表增刪操作時就不用單獨考慮鏈表是否為空的情況了。
具體實現也很簡單，大家可以理解成跟不帶哨兵位節點時一樣，只不過之前是在頭節點中開始放數據，現在是在第二個節點中開始放數據，相當于頭節點里面數據是空的，頭節點是空指針。
// 創建新節點的函數SL*CreatSListNode(LTDataType x)
{SL* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");//return NULL;exit(-1);//調用 exit 函數以非零狀態終止程序。}node->next = NULL;node->prev = NULL;//回訪指針，指向上一個節點node->data = x;return node;
}// 初始化雙鏈表的函數void InitList(SL* L)
{// 創建哨兵節點L->sentinel = (Node*)malloc(sizeof(Node));L->sentinel->prev = L->sentinel; // 哨兵節點的 prev 指向自己L->sentinel->next = L->sentinel; // 哨兵節點的 next 指向自己
}void InsertAtHead(SL* L, int x ）
{SL* newNode = CreatSListNode(x);// 將新節點插入到哨兵節點之后newNode->next = L->sentinel->next;newNode->prev = L->sentinel;L->sentinel->next->prev = newNode;L->sentinel->next = newNode;
}以上就是這期的內容，希望能給有需求的小伙伴們提供一些幫助，如果有疏漏的地方，小伙伴們可以直接指出，以便糾正，祝大家天天開心@
