鏈表：

• 基本單位是節點。節點至少兩部分：數據，下一個數據的地址。
• 頭指針head，始終指向鏈表的第一個節點。若沒有節點，則head=NULL。
• 鏈表在內存中是非連續的。不能使用索引（下標）查找元素。只能從頭遍歷。
• 鏈表有單鏈表、循環單鏈表、雙鏈表、循環雙鏈表。本文以單鏈表舉例。

添加節點：（注意指向順序，避免數據丟失）

• 在鏈表頭部添加：先新節點指向第一個節點，再頭指針指向新節點。
• 在鏈表尾部添加：最后一個節點指向新節點。
• 在鏈表指定位置添加：找到指定位置，先新節點指向下一個節點，再上一個節點指向新節點。

?刪除節點：

• 刪除鏈表頭部節點：頭指針指向第二個節點。
• 刪除鏈表尾部節點：倒數第二個節點指向NULL。
• 刪除鏈表指定位置節點：找到指定位置，上一個節點指向該節點的下一個節點。

---

?C語言代碼：

創建節點（結構體數據類型），并創建具體節點實例的函數：

// 節點(結構體數據類型)
typedef struct Node
{int data;                 // 數據為整數struct Node *next;        // 指針指向下一個節點
} LinkNode;                   // 別名LinkNode

// 創建具體節點實例的函數
LinkNode * createNode(int data)
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));   // 給節點分配內存空間if(node == NULL){perror("Memory allocation failed");exit(-1);}node->data = data;node->next = NULL;return node;
}

本文將頭指針和鏈表長度作為全局變量：

LinkNode *header = NULL;		// 頭指針，初始化指向NULL
int length = 0;				    // 統計鏈表元素個數

添加節點：

// 添加節點(鏈表頭部添加)
void addtop(int data)
{LinkNode *node = createNode(data);       // 調用createNode函數,創建具體節點node->next = header;                     // 先新節點指向頭指針指向的節點header = node;                           // 再頭指針指向新節點length++;                                // 每添加一個數據,length+1
}

// 添加節點(鏈表尾部添加)
void append(int data)
{if(length == 0)        // 若空鏈表,在鏈表頭部添加{addtop(data);return ;}LinkNode *node = createNode(data);LinkNode *cur = header;         // 從頭遍歷元素，找到最后while(cur->next != NULL){cur = cur->next;}cur->next = node;length++;
}

// 添加節點(在指定位置,位置從0開始)
void insert(int location, int data)
{if(length == 0)    // 若空鏈表,在鏈表頭部添加{addtop(data);return ;}if(length <= location)    // 若鏈表長度<=指定位置,在鏈表尾部添加{append(data);return ;}LinkNode *node = createNode(data);LinkNode *prev, *cur = header;      // 使用兩個指針,遍歷鏈表,找到指定位置while(location > 0){	prev = cur;cur = cur->next;location--;}node->next = cur;prev->next = node;length++;
}

刪除節點：

// 刪除節點（刪除鏈表頭部節點）
void pop(void)
{if(length == 0) return ;   // 空鏈表,直接退出程序header = header->next;length--;                  // 每刪除一個元素,length-1
}

// 刪除節點（刪除鏈表尾部節點）
void dellast(void)
{	if(length == 0) return ;       // 空鏈表,直接退出程序if(length == 1)                // 一個元素,頭指針直接指向NULL{header = NULL;return ;}LinkNode *prev, *cur = header;     // 使用兩個指針,遍歷鏈表,直到最后的位置while(cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;length--;
}

// 刪除節點（刪除鏈表指定位置的節點,位置從0開始）
void delat(int location)
{if(length == 0) return ;          // 空鏈表,直接退出程序if(length - 1 <= location)        // 鏈表長度-1<=指定位置,刪除鏈表尾部節點{dellast();return ;}LinkNode *prev, *cur = header;     // 使用兩個指針,遍歷鏈表,直到指定位置while(location > 0){prev = cur;cur = cur->next;location--;}prev->next = cur->next;length--;
}

// 刪除節點(刪除指定數據)
void del(int data)
{LinkNode *prev, *cur = header;      // 使用兩個指針,遍歷鏈表,比對數據內容while(cur != NULL){if(cur->data == data){if(header == cur)       // 若是第一個節點,頭指針直接跳過該節點指向下一個節點{header = cur->next;}else                    // 否則 該節點上一個節點,直接跳過該節點指向下一個節點{prev->next = cur->next;}length--;return ;}prev = cur;cur = cur->next;}return ;
}

遍歷節點：

void travel(void)
{if(length == 0) return ;       // 空鏈表,直接退出程序printf("linklist elements: ");LinkNode *cur = header;while(cur != NULL){printf("%d \t", cur->data);cur = cur->next;}printf("\n");
}

---

完整代碼：（linklist.c）

#include <stdio.h>
#include <stdlib.h>/* structure */
typedef struct Node			// node structure
{int data;struct Node *next;
} LinkNode;/* global variables */
LinkNode *header = NULL;		// header pointer
int length = 0;				    // the number of linklist elements/* function prototype */
void addtop(int data);			// add element to the top of the linklist
void append(int data);			// add element to the end of the linklist
void insert(int location, int data);	// add element to the specify location (start with 0)
void travel(void);			// show element one by one
void pop(void);				// delete element from the top of the linklist
void dellast(void);			// delete element from the end of the linklist
void delat(int location);		// delete element from the specify location (start with 0)
void del(int data);			// delete the specify data/* main function */
int main(void)
{addtop(5);printf("length is %d \n", length);		travel();append(9);printf("length is %d \n", length);		travel();insert(1,8);printf("length is %d \n", length);		travel();addtop(3);printf("length is %d \n", length);		travel();pop();	printf("length is %d \n", length);		travel();dellast();printf("length is %d \n", length);		travel();delat(1);printf("length is %d \n", length);		travel();del(7);printf("length is %d \n", length);		travel();del(5);printf("length is %d \n", length);		travel();
}/* subfunction */
LinkNode * createNode(int data)		// create a node
{LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));if(node == NULL){perror("Memory allocation failed");exit(-1);}node->data = data;node->next = NULL;return node;
}void addtop(int data)			// add element to the top of the linklist
{LinkNode *node = createNode(data);node->next = header;header = node;length++;
}void append(int data)			// add element to the end of the linklist
{if(length == 0){addtop(data);return ;}LinkNode *node = createNode(data);LinkNode *cur = header;while(cur->next != NULL){cur = cur->next;}cur->next = node;length++;
}	void insert(int location, int data)	// add element to the specify location (start with 0)
{if(length == 0){addtop(data);return ;}if(length <= location){append(data);return ;}LinkNode *node = createNode(data);LinkNode *prev, *cur = header;while(location > 0){	prev = cur;cur = cur->next;location--;}node->next = cur;prev->next = node;length++;
}void travel(void)			// show element one by one
{if(length == 0) return ;printf("linklist elements: ");LinkNode *cur = header;while(cur != NULL){printf("%d \t", cur->data);cur = cur->next;}printf("\n");
}void pop(void)				// delete element from the top of the linklist
{if(length == 0) return ;header = header->next;length--;
}void dellast(void)			// delete element from the end of the linklist
{	if(length == 0) return ;if(length == 1){header = NULL;return ;}LinkNode *prev, *cur = header;while(cur->next != NULL){prev = cur;cur = cur->next;}prev->next = NULL;length--;
}void delat(int location)		// delete element from the specify location (start with 0)
{if(length == 0) return ;if(length - 1 <= location){dellast();return ;}LinkNode *prev, *cur = header;while(location > 0){prev = cur;cur = cur->next;location--;}prev->next = cur->next;length--;
}void del(int data)			// delete the specify data
{LinkNode *prev, *cur = header;while(cur != NULL){if(cur->data == data){if(header == cur){header = cur->next;}else{prev->next = cur->next;}length--;return ;}prev = cur;cur = cur->next;}return ;
}

編譯鏈接： gcc -o linklist linklist.c

執行可執行文件： ./linklist

?