數據結構

鏈表

鏈表和數組的區別

1. 存儲方式

• 數組：
  • 元素在內存中連續存儲，占用一塊連續的內存空間
  • 元素的地址可以通過索引計算（基地址 + 索引 × 元素大小）
  • 大小固定，在創建時需要指定容量
• 鏈表：
  • 元素（節點）在內存中分散存儲，不要求連續
  • 每個節點包含數據和指向下一個（或上一個）節點的指針
  • 大小動態變化，可根據需要隨時增減節點

2. 訪問效率

• 數組：
  • 支持隨機訪問，通過索引可以直接訪問任意元素，時間復雜度為 O (1)
  • 訪問效率高，適合需要頻繁隨機訪問的場景
• 鏈表：
  • 不支持隨機訪問，必須從表頭（或表尾）開始依次遍歷，時間復雜度為 O (n)
  • 訪問效率低，不適合需要頻繁隨機訪問的場景

3. 插入和刪除操作

• 數組：
  • 插入 / 刪除元素時，需要移動該位置后的所有元素，時間復雜度為 O (n)
  • 尤其在數組頭部操作時效率極低
  • 動態擴容時需要重新分配內存并復制元素
• 鏈表：
  • 插入 / 刪除元素時，只需修改相關節點的指針，時間復雜度為 O (1)（已知前驅節點時）
  • 不需要移動其他元素，操作效率高
  • 沒有擴容問題，內存利用率更高

4. 內存占用

• 數組：
  • 可能存在內存浪費（預分配的容量可能大于實際需要）
  • 內存利用率較低
• 鏈表：
  • 每個節點需要額外存儲指針信息，有一定內存開銷
  • 但整體內存利用率更高，不會浪費空間

5. 適用場景

• 數組：
  • 適合需要頻繁隨機訪問元素的場景（如查找操作多）
  • 元素數量固定或變化不大的情況
  • 例如：數據庫索引、矩陣存儲、緩存實現等
• 鏈表：
  • 適合需要頻繁插入和刪除元素的場景
  • 元素數量動態變化較大的情況
  • 例如：鏈表式隊列 / 棧、哈希表鏈地址法沖突解決、鄰接表等

總結對比表

特性	數組	鏈表
存儲方式	連續內存	分散內存 + 指針
隨機訪問	支持 (O (1))	不支持 (O (n))
插入刪除	低效 (O (n))	高效 (O (1))
內存效率	可能浪費空間	有指針開銷但利用率高
大小	固定	動態

• 數組中的數據我們稱之為元素

• 鏈表中的數據我們稱之為節點

  每一個節點都是一個結構體,當前結構體包含兩種信息

  1. 數據(每個節點中所存儲的信息)
  2. 節點指針(保存下一個節點的信息)

  將節點插入鏈表:頭插法/尾插法/中間插入

  eg:

                                                節點對應結構體
typedef struct Node 
{int num;		   /每個節點中存儲的數據,可以有多個struct Node* pNext;   /用于保存下一個節點(結構體)的指針
} Node;函數功能:      創建一個節點int n --------當前節點的數據NODE*  head---------當前鏈表首節點地址返回類型:成功返回當前節點首地址,失敗返回NULLNODE* createNode(int n,NODE* head)
{//創建一個新節點NODE* pNew = (NODE*)malloc(sizeof(NODE));if(pNew == NULL){printf("createNode %d fail:%s!\n",n,strerror(errno));return NULL;}//初始化新節點中的成員變量pNew -> num = n;pNew -> pNext = NULL;//返回當前節點的首地址return pNew;}函數功能:      刪除整個鏈表NODE*  head---------當前鏈表首節點地址void distroyList(NODE* head){if(head == NULL){return;}NODE* P = head;while(p != NULL){head = p -> pNext;free(p);p = head;}}函數功能:    輸出整個鏈表NODE*  head---------當前鏈表首節點地址返回類型:成功返回當前節點首地址,失敗返回NULLvoid displayList(NODE* head){while(p != NULL){printf("%d",p->num);p = p->pNext;}}                                  void insert_head1(int n,NODE** head)
{//創建新節點NODE*  pNew = createNode(n);//如果是空鏈表if(*head == NULL){*head = pNew;return}//新節點指向原鏈表的首節點pNew -> pNext = *head;//將新節點的起始地址給*head*head = pNew;}NODE*	 insert_head2(int n,NODE* head)
{NODE*  pNew = createNode(n);//如果是空鏈表if(head == NULL){return pNew;}pNew -> pNext = *head;//將新節點的起始地址給*headreturn  pNew;}//插入到結尾NODE* insert_tail(int n, NODE* head)
{//創建節點NODE* pNew == createNode(n);if(pNew == NULL){return pNew;}//獲取原鏈表尾節點的指針NODE* pTail = getTaiilNode(head);if(pTail) = getTaiilNode(head);{return pNew;}pTail ->P=pNext = pNew;return head;}NODE* insertNode(int n,NODE* head,int pos)
{}int main()
{// 用于記錄當前鏈表中首節點的地址NODE* pHead = NULL;// 將節點插入鏈表中：頭插法//insert_head1(5, &pHead);//insert_head1(4, &pHead);//insert_head1(3, &pHead);//insert_head1(2, &pHead);//insert_head1(1, &pHead);//pHead = insert_head2(-5, pHead);//pHead = insert_head2(-4, pHead);//pHead = insert_head2(-3, pHead);//pHead = insert_head2(-2, pHead);//pHead = insert_head2(-1, pHead);// 將節點插入鏈表中：尾插法//pHead = insert_tail(1, pHead);//pHead = insert_tail(2, pHead);//pHead = insert_tail(3, pHead);//pHead = insert_tail(4, pHead);// 將節點插入鏈表中：任意位置插入// 假設位置 0 代表頭插pHead = insertNode(1, pHead, 3);displayList(pHead);distroyList(pHead);return 0;
}