探索數據結構:便捷的雙向鏈表

🔑🔑博客主頁:阿客不是客

🍓🍓系列專欄:漸入佳境之數據結構與算法

歡迎來到泊舟小課堂

😘博客制作不易歡迎各位👍點贊+?收藏+?關注

??

前言

前面我們學習了單鏈表,它解決了順序表中插入刪除需要挪動大量數據的缺點,使單鏈表解決順序表缺陷時,我們發現作為另一種形態出現的單鏈表似乎也有明顯的缺陷。

  1. 在部分功能實現時因為頭結點的改變需要引進二級指針(或者采用返回等更為復雜的方法)導致代碼更加復雜。
  2. 尋找某個節點的前一個節點,對于單鏈表而言只能遍歷,這樣就可能造成大量時間的浪費。
  3. 尾部以及指定位置插入、刪除數據的時間復雜度為O(N)?,效率低下。

為了解決這個問題,我們就要學習今天的主角——雙向鏈表

一、帶頭雙向循環鏈表的介紹

實際中鏈表的結構非常多樣,以下情況組合起來就有8種鏈表結構,雖然有這么多的鏈表的結構,但是我們實際中最常用還是兩種結構無頭單向不循環鏈表,帶頭雙向循環鏈表。

對比單鏈表來了解,帶頭雙向循環鏈表:結構復雜,一般單獨存儲數據。憑著其復雜的結構我們可以做到快速管理數據,實現對數據的操作。

?

帶頭雙向循環鏈表具有以下特點:

  1. 頭節點:帶頭雙向循環鏈表包含一個頭節點,它位于鏈表的起始位置,并且不存儲實際數據。頭節點的前指針指向尾節點,頭節點的后指針指向第一個實際數據節點。
  2. 循環連接:尾節點的后指針指向頭節點,而頭節點的前指針指向尾節點,將鏈表形成一個循環連接的閉環。這樣可以使鏈表在遍歷時可以無限循環,方便實現循環操作。
  3. 雙向連接:每個節點都有一個前指針和一個后指針,使得節點可以向前和向后遍歷。前驅指針指向前一個節點,后繼指針指向后一個節點。

總結:帶頭雙向循環鏈表可以支持在鏈表的任意位置進行插入和刪除操作,并且可以實現正向和反向的循環遍歷。通過循環連接的特性,鏈表可以在連續的循環中遍歷所有節點,使得鏈表的操作更加靈活和高效。

二、帶頭雙向循環雙鏈表的實現

2.1 創建鏈表

雙向鏈表的定義結構體需要包含三個成員,一個成員存儲數值,一個成員存儲前一個節點的地址,最后一個成員存儲下一個節點的地址。

typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTN;

2.2 初始化鏈表

在初始化雙向鏈表時,我們需要創建一個頭節點,也就是我們常說的哨兵位頭節點

這里需要注意一下:創建頭結點的時候,因為鏈表中沒有其它的數據,我們在初始化的時候讓guard的next和prev都要指向自己,這樣才是一個循環鏈表(如下圖所示 ↓↓↓ )

?

LTN* LTinit()
{LTN* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

2.3 創建新結點

跟之前的一樣就不過多介紹了

LTN* CreateLTNode(LTDataType x)
{LTN* newnode = (LTN*)malloc(sizeof(LTN));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

2.4?打印鏈表

這個鏈表中的結點是沒有NULL的,因此在判斷循環是否要結束的條件應該是判斷tail是否等于phead

void LTprint(LTN* phead)
{assert(phead);printf("哨兵位 <--> ");LTN* tail = phead->next;while (tail != phead){printf("%d <--> ",tail->val);tail = tail->next;}printf("哨兵位\n");
}

2.5?雙向鏈表的查找

和單鏈表一樣,我們也可以對雙向鏈表進行查找。如果找到就返回該節點的地址,否則返回NULL。

LTN* LTFind(LTN* phead, LTDataType x)
{assert(phead);LTN* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

2.6?雙向鏈表的插入

2.5.1 尾插

單鏈表尾插結點需要遍歷全鏈表,當指針走到鏈表最后一個結點的時候,判斷tail->next是否為NULL,若為NULL,則跳出遍歷的循環,尾插新結點。然而帶頭雙向循環鏈表不需要遍歷鏈表,只需要對哨兵位的頭節點的prev域解引用,直接找到帶頭雙向循環鏈表的尾節點,尾插新節點。

?

頭指針的區別:帶頭雙向循環鏈表不需要判斷頭指針是否指向NULL,因為哨兵位的頭節點也是有它的地址的,添加新節點時只需要直接在尾節點尾插。然而單鏈表卻需要判斷頭指針是否指向NULL,而且需要用到二級指針,比較棘手。

??

void LTpushback(LTN* phead, LTDataType x)
{assert(phead);//帶哨兵位頭結點,只改變了結構體成員,不需要二級指針LTN* tail = phead->prev;LTN* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

2.5.2 頭插

void LTpushfront(LTN* phead, LTDataType x)
{assert(phead);LTN* tail = phead->next;LTN* newnode = CreateLTNode(x);tail->prev = newnode;newnode->next = tail;newnode->prev = phead;phead->next = newnode;
}

2.5.3 任意位置插入

void LTInsert(LTN* pos, LTDataType x)
{assert(pos);LTN* newnode = CreateLTNode(x);LTN* tail = pos->prev;pos->prev = newnode;newnode->next = pos;newnode->prev = tail;tail->next = newnode;
}

和單鏈表不同,雙向鏈表頭尾操作完全可以用任意位置操作替代。?

LTInsert實現尾插:
LTInsert(phead, x);
LTInsert實現頭插:
LTInsert(phead->next, x);

2.7?雙向鏈表的刪除

2.6.1 尾刪

?當鏈表只有一個節點(哨兵位不算)時:

若鏈表為NULL(只剩哨兵位就是鏈表為NULL)時,再尾刪就被assert會出錯:

void LTpopback(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->prev;LTN* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}

2.6.2 頭刪

鏈表不止一個結點時:

鏈表為一個結點時:

代碼示例如下:?

void LTpopfront(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->next;LTN* tailnext = tail->next;tailnext->prev = phead;phead->next = tailnext;free(tail);tail = NULL;
}

2.6.3 任意位置刪除

void LTErase(LTN* pos)
{assert(pos);LTN* tailnext = pos->next;LTN* tailprev = pos->prev;tailnext->prev = tailprev;tailprev->next = tailnext;free(pos);pos = NULL;
}
LTErase實現尾刪:
LTErase(phead->prev);

?LTErase實現頭刪:

LTErase(phead->next);

2.8?銷毀鏈表

void LTDestroy(LTN* phead)
{assert(phead);LTN* cur = phead->next;while (cur != phead){LTN* next = cur->next;free(cur);cur = next;}free(phead);
} 

三、完整代碼

3.1 LTN.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTN;LTN* LTinit();//初始化鏈表void LTprint(LTN* phead);void LTpushback(LTN* phead, LTDataType x);
void LTpushfront(LTN* phead, LTDataType x);
void LTpopback(LTN* phead);
void LTpopfront(LTN* phead);LTN* LTFind(LTN* phead, LTDataType x);void LTInsert(LTN* pos, LTDataType x);
void LTErase(LTN* pos);

3.2 LTN.c

#include"SLTN.h"LTN* CreateLTNode(LTDataType x)
{LTN* newnode = (LTN*)malloc(sizeof(LTN));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}LTN* LTinit()
{LTN* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}void LTprint(LTN* phead)
{assert(phead);printf("哨兵位 <--> ");LTN* tail = phead->next;while (tail != phead){printf("%d <--> ",tail->val);tail = tail->next;}printf("哨兵位\n");
}void LTpushback(LTN* phead, LTDataType x)
{assert(phead);//帶哨兵位頭結點,只改變了結構體成員,不需要二級指針LTN* tail = phead->prev;LTN* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//LTInsert(phead->prev, x);
}void LTpushfront(LTN* phead, LTDataType x)
{assert(phead);LTN* tail = phead->next;LTN* newnode = CreateLTNode(x);tail->prev = newnode;newnode->next = tail;newnode->prev = phead;phead->next = newnode;//LTInsert(phead->next, x);
}void LTpopback(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->prev;LTN* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;//LTErase(phead->prev);
}void LTpopfront(LTN* phead)
{assert(phead);assert(phead->next != phead);LTN* tail = phead->next;LTN* tailnext = tail->next;tailnext->prev = phead;phead->next = tailnext;free(tail);tail = NULL;//LTErase(phead->next);
}LTN* LTFind(LTN* phead, LTDataType x)
{assert(phead);LTN* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}void LTInsert(LTN* pos, LTDataType x)
{assert(pos);LTN* newnode = CreateLTNode(x);LTN* tail = pos->prev;pos->prev = newnode;newnode->next = pos;newnode->prev = tail;tail->next = newnode;
}void LTErase(LTN* pos)
{assert(pos);LTN* tailnext = pos->next;LTN* tailprev = pos->prev;tailnext->prev = tailprev;tailprev->next = tailnext;free(pos);pos = NULL;
}

四、順序表與鏈表優缺點分析

  • 鏈表(雙向)優勢:
  1. 任意位置插入刪除都是O(1)
  2. 按需申請釋放,合理利用空間,不存在浪費
  • 問題:
  1. 下標隨機訪問不方便
  • 順序表問題:
  1. 頭部或中間插入刪除效率低,要挪動數據O(N)
  2. 空間不夠要擴容,擴容有一定消耗,且可能存在一定的空間浪費
  3. 只適合尾插尾刪
  • 優勢:?
  1. 支持下標隨機訪問O(1),可以進行排序操作。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/21483.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/21483.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/21483.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

k8s常用命令(持續更新中)

1. 常用命令 # 查看命名空間下的所有pod kubectl get pod -n 命名空間 # 查看某命名空間下某個pod的日志 kubectl logs -f -n 命名空間 pod名# 查看某命名空間下某pod的詳細信息 kubectl describe pod pod名 -n 命名空間# 查看所有命名空間下pod kubectl pods --all-namespac…

等保測評核心對象概覽及實施要點

等保測評的對象主要包括以下幾個方面&#xff1a; 1. 信息系統&#xff1a;由計算機硬件、網絡和通信設備、計算機軟件、信息資源、信息用戶和規章制度組成的以處理信息流為目的的人機一體化系統。常見的信息系統包括辦公自動化系統(OA)、客戶關系管理系統、進銷存管理系統等。…

ICLR24大模型提示(3/11) | PromptAgent:利用語言模型進行戰略規劃,實現專家級提示優化

【摘要】高效的、針對特定任務的提示通常由專家精心設計&#xff0c;以整合詳細的說明和領域見解&#xff0c;這些見解基于對大型語言模型 (LLM) 的本能和目標任務的復雜性的深刻理解。然而&#xff0c;自動生成這種專家級提示仍然難以實現。現有的提示優化方法往往忽視領域知識…

20240603每日AI------------項目引入Spring Cloud Alibaba AI (二)

項目源碼解析 前端代碼&#xff1a; <div class"container"><h1>Spring Cloud Alibaba AI Example</h1><form id"form"><label for"message">User Message&#xff1a;</label><input type"text&q…

大模型PEFT(一)之推理實踐學習記錄

1. 簡介 多種模型: LLaMA、Mistral、Mixtral-MoE、Qwen、Yi、Gemmha、Baichuan、ChatGLM、Phi等等。集成方法:(增量)預訓練、指令監督微調、獎勵模型訓練、PPO訓練和DPO訓練。多種精度:32比特全參數微調、16比特凍結微調、16比特LORA微調和基于AQLM/AWQ/GPTQ/LLM.int8 的2/4/8…

一篇文章掌握Java的80%:面向對象與并發編程

Java作為一種廣泛使用的計算機編程語言&#xff0c;其強大之處在于其面向對象的特性和對并發編程的良好支持。作為一名程序員&#xff0c;我深知掌握Java的面向對象概念、集合框架、多線程與并發編程&#xff0c;以及JVM基礎對于編寫高效、可維護的代碼至關重要。本文將引導你快…

操作字符串獲取文件名字(包含類型)

記錄一種操作字符串獲取文件名字的操作方式&#xff0c;方便后期的使用。示例&#xff1a; 輸入&#xff1a;"D:/code/Test/Test.txt" 輸出&#xff1a;"Test.txt" 設計思路&#xff1a; 首先查找路徑中最后一個”/“&#xff0c;然后再通過字符串截取的…

湖南源點調研 為什么中小企業產品上市前一定要做市場調研?

本文由湖南長沙&#xff08;產品前測&#xff09;源點調研咨詢編輯發布 可能有很多企業主會表示&#xff0c;市場調研&#xff0c;產品調研&#xff0c;不都是大公司、大品牌、上市公司才會有的流程嗎&#xff0c;像我們這種小企業、小品牌、小廠家沒有必要去那么做&#xff0…

Python文本分詞工具庫-jieba

內容目錄 一、分詞二、設置分詞三、詞性信息四、關鍵詞提取 jieba庫是一個針對中文文本的分詞工具庫&#xff0c;廣泛應用于自然語言處理&#xff08;NLP&#xff09;領域的中文文本預處理階段。 主要功能: 中文分詞&#xff1a;能夠將連續的中文文本切割成有意義的詞語序列&a…

變壓器中性點接地電阻柜的出廠標準是什么

變壓器中性點接地電阻柜的出廠標準是什么&#xff1f; 現代電氣配電系統中&#xff0c;接地電阻是保障人身安全的非常重要的設施。在高壓電氣設備中&#xff0c;中性點接地電阻柜的作用是限制設備中的過電流和短路故障所產生的電流&#xff0c;以保障人身安全。變壓器中性點接…

楊輝三角形及其C語言實現

一、引言 楊輝三角形&#xff08;Pascal’s Triangle&#xff09;&#xff0c;又稱帕斯卡三角形&#xff0c;是一個在數學中經常出現的數表。它的構造規則非常簡單&#xff1a;三角形中的每個數字等于它上方兩數字之和&#xff08;或者說&#xff0c;它是位于它肩上的兩個數字…

開源VS閉源:大模型發展路徑之爭,你站哪一派?

文章目錄 引言一、數據隱私1.1開源大模型的數據隱私1.2 閉源大模型的數據隱私1.3 綜合考量 二、商業應用2.1 開源大模型的商業應用2.2 閉源大模型的商業應用2.3 商業應用的綜合考量 三、社區參與3.1 開源大模型的社區參與3.2 閉源大模型的社區參與3.3 綜合考量 結論 引言 在人…

解析“分層引流”在顱內感染治療中的價值意義

臨床中&#xff0c;化膿性顱內感染的治療一直是界內關注的重點。近年來&#xff0c;得益于醫療技術的持續革新與提升&#xff0c;顱內感染的治療方法也獲得了不斷的更新與優化。在此背景下&#xff0c;北京精誠博愛醫院所倡導的“分層引流”理念&#xff0c;作為一種新興的治療…

外貿小白到銷冠,如何30天快速提升?

外貿從業8年&#xff0c;在工廠從0-1做外貿&#xff0c;外貿的坑踩過很多&#xff0c;也做出了很多出色的業績&#xff0c;希望這篇文章可以給到外貿新人快速提升的思路。 對于剛剛進入外貿行業的職場新人&#xff1f;應該怎么做&#xff1f; 第一個月應該學什么&#xff1f;…

什么牌子的開放式耳機質量好?2024超強實力派品牌推薦!

耳機對于一個音樂人有重要這個不必多說&#xff0c;我朋友是個音樂編輯&#xff0c;他經常需要長時間佩戴耳機進行音頻編輯和混音工作。在嘗試過多款開放式耳機后&#xff0c;都沒找到合適的。今天&#xff0c;我將從專業角度為大家帶來幾款熱門開放式耳機的測評報告&#xff0…

第二證券炒股知識:股票內盤外盤代表什么意思?

股票內盤是主動性賣盤&#xff0c;表明以買入價成交的股數&#xff0c;持股的投資者主動以等于或是低于買一、買二、買三、買四、買五的價格賣出手中持有的股份&#xff0c;買入成交數量核算參加內盤。 股票外盤是主動性買盤&#xff0c;表明以賣出價成交的股數&#xff0c;場…

跟著大佬學RE(一)

學了一個 map&#xff08;&#xff09;函數的使用 import base64rawData "e3nifIH9b_CndH" target list(map(ord, rawData)) # map 函數將 rawData 中的每個字符傳遞給 ord 函數。ord 函數返回給定字符的 Unicode 碼點 print(target) # 打印 map 對象的內存地址&…

電腦中病毒了怎么辦?7招教你保護電腦安全!

“不知道怎么回事&#xff0c;我的電腦莫名其妙就中病毒了&#xff0c;實在不知道應該怎么操作了&#xff0c;希望大家可以幫我&#xff01;” 在數字化時代的浪潮中&#xff0c;電腦已成為我們生活與工作中不可或缺的一部分。然而&#xff0c;就像任何事物都有其陰暗面一樣&am…

Python | 武理刷題

1. 為什么是非法的&#xff1f; a1a1 在Python&#xff08;以及大多數其他編程語言&#xff09;中&#xff0c;表達式 a1a1 是非法的&#xff0c;因為它試圖將一個值&#xff08;a1 的結果&#xff09;賦給一個表達式&#xff08;a1 本身&#xff09;&#xff0c;而不是一個…

ip地址快速切換軟件有哪些好處

ip地址快速切換軟件有哪些好處&#xff1f;IP地址快速切換軟件具有諸多顯著的好處&#xff0c;以下是對其主要優勢的詳細闡述&#xff1a; 首先&#xff0c;IP地址快速切換軟件極大地提升了網絡活動的靈活性和便捷性。對于需要經常切換網絡環境或進行多賬號管理的用戶而言&…