鏈表
什么是數據結構
數據存儲于計算機的內存中，決定數據存儲的順序和位置的便是數據結構。數據在內存中是線性排列的笛洛。可以使用指針等工具乃坤，構造復雜的“樹形”型等復雜結構苛让。
鏈表特點
鏈表是數據結構之一，其中的數據呈現線性排列湿诊。鏈表中的數據進行添加和刪除非常方便狱杰，訪問耗時間。
指針：每個數據都有一個指針厅须，用于指向下一個數據的內存地址仿畸。
image.png
在鏈表中，數據一般是分散存儲于內存中九杂，無需連續(xù)存儲颁湖。
- 訪問：因為無序和分散存儲宣蠕，所以訪問數據的話例隆，只能從頭開始，稱之為順序訪問
- 添加：改變添加位置前后的指針指向即可
- 刪除：也是改變指針指向抢蚀，數據本身還是存在镀层；但是沒有指針指向這個數據，所以無法訪問到該數據
運行時間
將鏈表中的數據量記為n皿曲，
- 訪問：如果數據在末尾唱逢，需要從頭開始線性查找，需要的時間就是O(n)
- 添加和刪除：只是單純的改變指針指向屋休，和n無關坞古，所以時間是O(1)
其他鏈表
循環(huán)鏈表
在鏈表尾部使用指針，使其指向指針鏈表頭部的數據劫樟，形成一個閉環(huán)痪枫，稱之為循環(huán)鏈表。
- 沒有頭和尾的概念
- 保存固定數量的最新數據常用循環(huán)鏈表
image.png
雙向鏈表
指針設為兩個叠艳，分別指向指針前后的數據奶陈，稱之為雙向鏈表。
- 可以前后雙向訪問數據
- 指針數量增加附较，會帶來存儲空間的增加
- 添加和刪除數據時候需要改變更多的指針指向
image.png
