鏈表是什么意思？鏈表與數(shù)組有什么區(qū)別

鏈表是什么意思？鏈表與數(shù)組有什么區(qū)別？很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

鏈表的相關(guān)知識(shí)整理

什么是鏈表

　　鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

鏈表與數(shù)組的區(qū)別

　　回憶下數(shù)組的概念 ，所謂數(shù)組，是相同數(shù)據(jù)類型的元素按一定順序排列的集合。根據(jù)概念我們可以知道數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù)；由于不同的存儲(chǔ)方式導(dǎo)致數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存，數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū)；由于數(shù)組在內(nèi)存中連續(xù)，我們可以利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n)；但是由于數(shù)組的連續(xù)性數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1)?？偨Y(jié)一下，數(shù)組和鏈表的區(qū)別如下
　　1.數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存
　　2.數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù)
　　3.數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū)
　　4.數(shù)組利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n)；
　　5.數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1)。

C#實(shí)現(xiàn)鏈表的基本操作

　　以單鏈表為例，根據(jù)鏈表的定義我們先定義鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

    public class Node<T>
    {
        private T data;
        private Node<T> next;

        //有參構(gòu)造函數(shù)
        //主要用例實(shí)例化需要處理的節(jié)點(diǎn)用
        public Node(T item, Node<T> next)
        {
            data = item;
            this.next = next;
        }

        //無參構(gòu)造函數(shù)，用例實(shí)例化Node節(jié)點(diǎn)
        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; }
        }
    }

　　接下來我們來實(shí)現(xiàn)鏈表的操作，構(gòu)造一個(gè)鏈表，在構(gòu)造鏈表里我們定一個(gè)頭結(jié)點(diǎn)的對(duì)象，頭結(jié)點(diǎn)是個(gè)很有用的節(jié)點(diǎn)，在后續(xù)代碼中就可以慢慢體會(huì)到

    public class MyLinkList<T>
    {
       public Node<T> Head { get; set; }

        //構(gòu)造器  
        public MyLinkList()
        {
            Head = null;
        }
    }

　　1.求鏈表的長(zhǎng)度，思路：從頭結(jié)點(diǎn)向后訪問，直到最后一個(gè)節(jié)點(diǎn)，代碼如下

       public int Length()
        {
            var p = Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }

　　2.清空鏈表，這個(gè)就比較奧簡(jiǎn)單了，直接將頭結(jié)點(diǎn)置為null 即可，代碼如下

        public void Clear()
        {
            Head = null;
        }

　　3.同理判斷鏈表是否為空也要用的頭結(jié)點(diǎn)

        public bool IsEmpty()
        {
            if (Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

　　4.在鏈表的末尾添加新元素，添加新元素，需要先判斷鏈表是否為空，如果為空我們要給頭結(jié)點(diǎn)賦值，如果不為空需要修改最后一個(gè)節(jié)點(diǎn)的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個(gè)結(jié)點(diǎn)的位置前插入一個(gè)指定結(jié)點(diǎn)，首先需要找到插入的位置，然后修改相鄰節(jié)點(diǎn)的指向即可， 代碼如下

        public void Insert(T item, int i)
        {

            if (IsEmpty() || i < 1 || i > GetLength())
            {
                return;
            }
            //如果在第一個(gè)位置插入 則只需要將該節(jié)點(diǎn)的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.刪除指定節(jié)點(diǎn)，先找到要?jiǎng)h除的前一個(gè)結(jié)點(diǎn)，然后修改該結(jié)點(diǎn)的next指向即可  代碼略。。。。

·　　7.鏈表還有刪除、獲取、查找等操作，基本思想都是一樣的，就不一一介紹了

鏈表相關(guān)的經(jīng)典題目

　　1. 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)
　　2. 將單鏈表反轉(zhuǎn)
　　3. 查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn)（k > 0）
　　4. 查找單鏈表的中間結(jié)點(diǎn)
　　5. 從尾到頭打印單鏈表
　　6. 已知兩個(gè)單鏈表pHead1 和pHead2 各自有序，把它們合并成一個(gè)鏈表依然有序
　　7. 判斷一個(gè)單鏈表中是否有環(huán)
　　8. 判斷兩個(gè)單鏈表是否相交
　　9. 求兩個(gè)單鏈表相交的第一個(gè)節(jié)點(diǎn)
　　10. 已知一個(gè)單鏈表中存在環(huán)，求進(jìn)入環(huán)中的第一個(gè)節(jié)點(diǎn)
　　11. 給出一單鏈表頭指針pHead和一節(jié)點(diǎn)指針pToBeDeleted，O(1)時(shí)間復(fù)雜度刪除節(jié)點(diǎn)pToBeDeleted

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。