溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
鏈表是什么意思？鏈表與數組有什么區別？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
回憶下數組的概念 ，所謂數組，是相同數據類型的元素按一定順序排列的集合。根據概念我們可以知道數組在內存中連續，鏈表不連續；由于不同的存儲方式導致數組靜態分配內存，鏈表動態分配內存，數組元素在棧區，鏈表元素在堆區；由于數組在內存中連續，我們可以利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n)；但是由于數組的連續性數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1)。總結一下，數組和鏈表的區別如下
1.數組靜態分配內存，鏈表動態分配內存
2.數組在內存中連續，鏈表不連續
3.數組元素在棧區，鏈表元素在堆區
4.數組利用下標定位，時間復雜度為O(1)，鏈表定位元素時間復雜度O(n)；
5.數組插入或刪除元素的時間復雜度O(n)，鏈表的時間復雜度O(1)。
以單鏈表為例，根據鏈表的定義我們先定義鏈表節點的數據結構
public class Node<T>
{
private T data;
private Node<T> next;
//有參構造函數
//主要用例實例化需要處理的節點用
public Node(T item, Node<T> next)
{
data = item;
this.next = next;
}
//無參構造函數，用例實例化Node節點
public Node()
{
data = default(T);
next = null;
}
public Node<T> Next
{
get { return next; }
set { this.next = value; }
}
public T Data
{
get { return data; }
set { this.data = value; }
}
}接下來我們來實現鏈表的操作，構造一個鏈表，在構造鏈表里我們定一個頭結點的對象，頭結點是個很有用的節點，在后續代碼中就可以慢慢體會到
public class MyLinkList<T>
{
public Node<T> Head { get; set; }
//構造器
public MyLinkList()
{
Head = null;
}
}1.求鏈表的長度，思路：從頭結點向后訪問，直到最后一個節點，代碼如下
public int Length()
{
var p = Head;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}2.清空鏈表，這個就比較奧簡單了，直接將頭結點置為null 即可，代碼如下
public void Clear()
{
Head = null;
}3.同理判斷鏈表是否為空也要用的頭結點
public bool IsEmpty()
{
if (Head == null)
{
return true;
}
else
{
return false;
}
}4.在鏈表的末尾添加新元素，添加新元素，需要先判斷鏈表是否為空，如果為空我們要給頭結點賦值，如果不為空需要修改最后一個節點的next指向，代碼如下
public void Append(T item)
{
if (Head == null)
{
Head = new Node<T>(item, null);
return;
}
var p = new Node<T>();
p = Head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = new Node<T>(item, null);
}5.在單鏈表的第i個結點的位置前插入一個指定結點，首先需要找到插入的位置，然后修改相鄰節點的指向即可， 代碼如下
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1 || i > GetLength())
{
return;
}
//如果在第一個位置插入 則只需要將該節點的next 指向head即可
if (i == 1)
{
var first = new Node<T>(item, null);
first.Next = Head;
Head = first;
return;
}
var p = new Node<T>();
p = Head;
var left = new Node<T>();
var right = new Node<T>();
int j = 1;
while (p.Next != null && j < i)
{
left = p;
right = p.Next;
++j;
}
var q = new Node<T>(item, null);
left.Next = q;
q.Next = right;
}6.刪除指定節點，先找到要刪除的前一個結點，然后修改該結點的next指向即可 代碼略。。。。
· 7.鏈表還有刪除、獲取、查找等操作，基本思想都是一樣的，就不一一介紹了
1. 求單鏈表中結點的個數
2. 將單鏈表反轉
3. 查找單鏈表中的倒數第K個結點（k > 0）
4. 查找單鏈表的中間結點
5. 從尾到頭打印單鏈表
6. 已知兩個單鏈表pHead1 和pHead2 各自有序，把它們合并成一個鏈表依然有序
7. 判斷一個單鏈表中是否有環
8. 判斷兩個單鏈表是否相交
9. 求兩個單鏈表相交的第一個節點
10. 已知一個單鏈表中存在環，求進入環中的第一個節點
11. 給出一單鏈表頭指針pHead和一節點指針pToBeDeleted，O(1)時間復雜度刪除節點pToBeDeleted
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
