數據結構的鏈表有那幾種類型

這篇文章主要介紹“數據結構的鏈表有那幾種類型”，在日常操作中，相信很多人在數據結構的鏈表有那幾種類型問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”數據結構的鏈表有那幾種類型”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

1. 單向循環鏈表

1.1. 結構

單鏈表的尾結點的指針域是  NULL，所以單鏈表到此終止。如果我們使用單鏈表的尾結點的指針域存儲頭結點的地址，即尾結點的直接后繼結點為頭結點，如此一來，單鏈表就構成了一個環(循環)，稱之為單項循環鏈表。

1.2. 實現思路

單向循環鏈表是由單鏈表進化而來的，算是單鏈表的“兒子”，所以單鏈表的那一套結構對于單向循環鏈表來說完全適用，從上圖你也可以看出，結構并無較大改變，二者所不同只在尾結點，所以我們只需要在尾結點和與尾結點相關的操作上下功夫就行了。

因此，單向循環鏈表的結構體和單鏈表的結構體相同。

/*單向循環鏈表的結點的結構體*/ typedef struct _Node {     int data; //數據域：存儲數據     struct _Node *next; //指針域：存儲直接后繼結點的地址 } Node;

為了統一對空鏈表和非空鏈表的操作，我們使用帶頭結點的鏈表來實現它。

1.3. 空鏈表及初始化

一個空鏈表如圖所示，只有一個頭指針和頭結點：

空鏈表

頭結點的指針域指向其本身構成一個循環，我們可以借此來判斷鏈表是否為空。

if (head->next == head) {     printf("空鏈表。\n"); }

想要初始化一個空鏈表很簡單，創造頭結點，使頭結點的 next 指針指向其自身即可：

Node *create_node(int elem) {     Node *new = (Node *) malloc(sizeof(Node));     new->data = elem;     new->next = NULL;     return new; }  /**  * 初始化鏈表  * p_head: 指向頭指針的指針  */ void init(Node **p_head) {     //創建頭結點     Node *head_node = create_node(0);     //頭指針指向頭結點     *p_head = head_node;     //頭結點的next指針指向其本身，構成環     head_node->next = head_node; }

1.4. 插入操作

這里只演示頭插法和尾插法

【頭插法】

因為帶頭結點，所以不需要考慮是否為空鏈表。下圖是向空鏈表中頭插兩個元素的過程：

單向循環鏈表頭插法過程

/**  * 頭插法，新結點為頭結點的直接后繼  * p_head: 指向頭指針的指針  * elem: 新結點的數據  */ void insert_at_head(Node **p_head, int elem) {     Node *new = create_node(elem);     Node *head_node = *p_head; //頭結點     //新結點插入頭結點之后     new->next = head_node->next;     head_node->next = new; }

【尾插法】

因為為了盡量簡單，所以我們并沒有設置指向尾結點的尾指針，所以在尾插之前，需要先借助某個指針，遍歷至尾結點，然后再插入。

/**  * 尾插法：新插入的結點始終在鏈表尾  * p_head: 指向頭指針的指針  * elem: 新結點的數據  */ void insert_at_tail(Node **p_head, int elem) {     Node *new = create_node(elem);     Node *head_node = *p_head; //頭結點     Node *tail = head_node; //tail指針指向頭結點     while (tail->next != head_node) { //tail遍歷至鏈表尾         tail = tail->next;     }     //尾插     new->next = tail->next;     tail->next = new; }

1.5. 刪除操作

刪除的本質是“跳過”待刪除的結點，所以我們要找到待刪除結點的直接前驅結點，然后讓其直接前驅結點的 next  指針指向其直接后繼結點，以此來“跳過”待刪除結點，最后保存其數據域，釋放結點，即完成刪除。

這里只演示頭刪法。

因為刪除的是頭結點的直接后繼結點，所以我們不必再費力尋找待刪除結點的直接前驅結點了。

單向循環鏈表頭刪法過程

/**  * 頭刪法：刪除頭結點之后的結點  * p_head: 指向頭指針的指針  * elem: 指向保存數據變量的指針  */ void delete_from_head(Node **p_head, int *elem) {     Node *head_node = *p_head; //頭結點     if (head_node->next == head_node) {         printf("空鏈表，無元素可刪。\n");         return;     }     Node *first_node = head_node->next; //首結點：頭結點的下一個結點     *elem = first_node->data; //保存被刪除結點的數據     head_node->next = first_node->next; //刪除結點     free(first_node); //釋放 }

1.6. 遍歷操作

我們可以一圈又一圈地循環遍歷鏈表，下面是循環打印 20 次結點地代碼：

/**  * 循環打印20次結點  */ void output_20(Node *head) {     if (head->next == head) {         printf("空鏈表。\n");         return;     }     Node *p = head->next;     for (int i = 0; i <= 20; i++) {         if (p != head) { //不打印頭結點             printf("%d ", p->data);         }         p = p->next;     }     printf("\n"); }

2. 雙向鏈表

2.1.  結構

顧名思義，雙向鏈表，就是有兩個方向，一個指向前，一個指向后。這樣我們就彌補了單鏈表的某個結點只能找到其直接后繼的缺陷。如圖所示：

雙向鏈表

2.2. 實現思路

為了實現能指前和指后的效果，只靠 next 指針肯定是不夠的，所以我們需要再添加一個指針 ——  prev，該指針指向某結點的直接前驅結點。

/*雙向鏈表的結點結構體*/ typedef struct _Node {     int data; //數據域     struct _Node *prev; //指向直接前驅結點的指針     struct _Node *next; //指向直接后繼結點的指針 } Node;

2.3. 空鏈表及初始化

雙向鏈表的空鏈表如圖所示：

要初始化一個這樣的空鏈表，需要創造出頭結點，然后將兩個指針域置空即可：

Node *create_node(int elem) {     Node *new = (Node *)malloc(sizeof(Node));     new->data = elem;     new->prev = NULL;     new->next = NULL;     return new; }  void init(Node **p_head) {     //創建頭結點     Node *head_node = create_node(0);     //頭指針指向頭結點     *p_head = head_node; }

2.4. 插入操作

這里只演示頭插法，過程如下：

雙向鏈表頭插法過程

代碼如下：

/**  * 頭插法，新結點為頭結點的直接后繼  * p_head: 指向頭指針的指針  * elem: 新結點的數據  */ void insert_at_head(Node **p_head, int elem) {     Node *new = create_node(elem);     Node *head_node = *p_head; //頭結點     if (head_node->next != NULL) { //不為空鏈表         Node *first_node = head_node->next; //首結點：頭結點的下一個結點         //首結點的prev指針指向new結點         first_node->prev = new;         //new結點的next指針指向首結點         new->next = first_node;     }     //new結點的prev指針指向頭結點     new->prev = head_node;     //頭結點的next指針指向new結點     head_node->next = new; }

2.5. 刪除操作

這里只演示頭刪法。下圖是將一個有兩個元素結點的雙向鏈表頭刪為空鏈表的過程：

雙向鏈表頭刪法過程

代碼如下：

/**  * 頭刪法  * p_head: 指向頭指針的指針  * elem: 指向保存變量的指針  */ void delete_from_head(Node **p_head, int *elem) {     Node *head_node = *p_head; //頭結點     Node *first_node = head_node->next; //待刪除的首結點：頭結點的下一個結點     if (head_node->next == NULL) { //判空         printf("空鏈表，無元素可刪。\n");         return;     }     *elem = first_node->data; //保存數據          if (first_node->next != NULL) {         first_node->next->prev = first_node->prev;     }     first_node->prev->next = first_node->next;     free(first_node); }

2.6. 遍歷操作

有了 next 指針域，我們可以一路向后遍歷;有了 prev 指針域，我們可以一路向前遍歷。

這里不再展示代碼了。

到此，關于“數據結構的鏈表有那幾種類型”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！