什麼是鍊錶？鍊錶與數組的差別？

鍊錶的相關知識整理

什麼是鍊錶

　　鍊錶是一種物理儲存單元上非連續、非順序的儲存結構，資料元素的邏輯順序是透過鍊錶中的指針連結次序實現的。鍊錶由一系列結點（鍊錶中每一個元素稱為結點）組成，結點可以在運行時動態產生。每個結點包括兩個部分：一個是儲存資料元素的資料域，另一個是儲存下一個結點位址的指標域。

鍊錶與陣列的差異

　　回憶下陣列的概念 ，所謂數組，是相同資料型別的元素按一定順序排列的集合。根據概念我們可以知道數組在內存中連續，鍊錶不連續；由於不同的存儲方式導致數組靜態分配內存，鍊錶動態分配內存，數組元素在棧區，鍊錶元素在堆區；由於數組在內存中連續，我們可以利用下標定位，時間複雜度為O(1)，鍊錶定位元素時間複雜度O(n)；但是由於數組的連續性數組插入或刪除元素的時間複雜度O(n)，鍊錶的時間複雜度O(1)。總結一下，數組和鍊錶的區別如下
　　1.數組靜態分配內存，鍊錶動態分配內存
　　2.數組在內存中連續，鍊錶不連續
　　3.數組元素在棧區，鍊錶元素在堆區
　　4.數組利用下標定位，時間複雜度為O(1)，鍊錶定位元素時間複雜度O(n)；
　　5.數組插入或刪除元素的時間複雜度O( n)，鍊錶的時間複雜度O(1)。

C#實現鍊錶的基本操作

　　以單鍊錶為例，根據鍊錶的定義我們先定義鍊錶節點的資料結構

    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. 找出單鍊錶中的倒數第K個結點（k >0）
　　4.鍊錶的中間結點
　　5. 從尾到頭列印單鍊錶
　　6. 已知兩個單鍊錶pHead1 和pHead2 各自有序，把它們合併成一個鍊錶依然有序
　　7.判斷一個單鍊錶中是否有環
　　8. 判斷兩個單鍊錶是否相交
　　9. 求兩個單鍊錶相交的第一個節點
　　10. 已知一個單鍊錶中存在環，求進入環中的第一個節點

　　11. 給出一單鍊錶頭指標pHead和一節點指標pToBeDeleted，O(1)時間複雜度刪除節點pToBeDeleted

 

好了就擼到這裡，題目是劍指offer裡的題目，大家可以解答下，有問題聯絡我

　　

 ###

以上是什麼是鍊錶？鍊錶與數組的差別？的詳細內容。更多資訊請關注PHP中文網其他相關文章！