溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹互聯網中鏈表是一種采用什么存儲結構存儲的線性表，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
鏈表是一種采用“鏈式”存儲結構存儲的線性表。鏈表的數據元素所占的存儲單元地址可以是連續的，也可以是不連續的，可根據需要臨時、動態地申請分配相應的存儲空間，數據元素之間的邏輯關系可以用“鏈”來表達。
本教程操作環境：windows7系統、Dell G3電腦。
為了克服順序表存儲結構的缺點，充分利用存儲空間和提高運行效率，線性表可以采用另一種存儲結構——鏈式存儲結構。線性表的鏈式存儲結構簡稱“鏈表（link list）”
鏈表的數據元素所占的存儲單元地址可以是連續的，也可以是不連續的，可根據需要臨時、動態地申請分配相應的存儲空間，數據元素之間的邏輯關系可以用“鏈”來表達。
鏈表的插入和刪除不需要移動數據元素，只需要修改鏈即可實現。
鏈表分類：
1.按鏈表內存分配實現的方式分類
①動態鏈表
②靜態鏈表
2.按鏈接方式分類
①單鏈表
②循環鏈表
③雙鏈表
（它們均為動態鏈表）
為了表示每個數據元素ai與其直接后繼數據元素ai+1之間的邏輯關系，對于每個數據元素ai，除了存儲本身的信息外，還需要存儲一個指示其直接后繼的信息（后繼的存儲位置-地址）。
存儲數據元素信息的域稱為數據域，存儲直接后繼位置的域稱為指針域，指針域中存儲的信息稱為指針或鏈。
這兩部分信息組成數據元素ai的存儲映像，稱為結點。
n個結點鏈成一個鏈表，即為線性表（a1,a2,a3,...,an）的鏈式存儲結構，因為鏈表的每個結點中只包含一個指針域，所以稱為單鏈表。
對于線性表來說，總有個頭有個尾，鏈表也不例外。鏈表中指向單鏈表第一個結點的指針叫做頭指針，整個鏈表的存取必須從頭指針開始進行，之后的每個結點都是上個結點的后繼指針指向的位置。鏈表的最后一個結點的指針為“空（通常用NULL表示）”——空指針。
為了方便實現鏈表的各種運算，在單鏈表的第一個數據結點之前設一個類型相同的結點，該結點稱為頭結點。
頭結點的數據域可以存儲一個特殊的標志信息如鏈表的長度，也可以不存儲任何數據。
鏈表的第一個數據結點和最后一個結點又稱為首結點和尾結點。
頭指針：
頭指針是指鏈表中指向第一個結點的指針，若鏈表有頭結點，則是指向頭結點的指針。
頭指針具有標識作用，常用頭指針冠以鏈表的名字。
無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。
頭結點：
頭結點是為了操作的統一和方便而設立的，放在第一個元素的結點之前，其數據域一般無意。
有了頭結點，對在第一元素結點前插入結點和刪除第一個結點，其操作與其他結點的操作就統一了。
頭結點不一定是鏈表必須要素。
/*線性表的單鏈表存儲結構*/
/*結點定義*/
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
/*單鏈表定義*/
typedef struct Node *LinkList;
假設存儲元素e的結點為s,將s插入到ai結點后面，如何操作？
思考：兩句插入代碼能否交換？
不能，如果調換過來，會導致ai+1等后面的元素無法找到，因為s的指針域沒有指向ai+1的地址。
聲明一個結點p指向鏈表的第一個結點，初始化j=1;
當j<i時，遍歷鏈表,讓p的指針向后移動，不斷指向下一個結點，j++;
若到鏈表末尾p為空，則說明第i個元素不存在；若查找成功，生成一個空節點s（使用malloc函數）
將數據元素e賦值給s->data,即為s->data=e;
插入標準語句：s->next=p->next；p->next=s;
返回成功。
假設存儲元素ai的結點為q,要實現將結點q刪除單鏈表的操作。
聲明一個結點p指向鏈表的第一個結點，初始化j=1;
當j<i時，遍歷鏈表,讓p的指針向后移動，不斷指向下一個結點，j++;
若到鏈表末尾p為空，則說明第i個元素不存在；若查找成功，將刪除結點p->next賦值給q
插入標準語句：p->next=q->next；
將q結點賦值給e,即為e=q->data;
釋放q結點
返回成功。
存儲方式：
順序表用一段連續的存儲單元依次存儲線性表中的數據元素
單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表元素
時間性能：
①查找
順序表O(1)
單鏈表O(n)
②插入和刪除
順序表O(n)
單鏈表O(1)
空間性能：
順序表需要預分配存儲空間，分大了，浪費，分小了易發生上溢
單鏈表不需要預分配存儲空間，需要多少都可以分配，元素個數不受限制
以上是“互聯網中鏈表是一種采用什么存儲結構存儲的線性表”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
