[数据结构]链表之单链表

目录

基本概念和操作：

实现方法和原理

应用场景和使用注意事项

算法和复杂度分析：

与其他数据结构的比较：

---

基本概念和操作：

单链表是一种常见的线性数据结构，由若干个节点组成，每个节点包含两部分：数据元素和指向下一个节点的指针。每个节点只有一个指针，通常称为 next 指针，它指向该节点的后继节点。头节点是第一个节点前面额外添加的一个节点，它不包含数据元素，但是包含对第一个节点的指针。

单链表可以表示任意长度的序列，可以动态地插入、删除节点，使其具有灵活性和高效性。但由于每个节点只有一个指针，因此单链表只能从前往后遍历，不能反向遍历。

单链表的节点用C#语言描述为：

namespace DataStructLibrary
{
    class SNode<T>
    {
        private T data;//数据域
        private SNode<T> next;//引用域
        public SNode(T val,SNode<T> p)
        {
            data = val;
            next = p;
        }
 
        public SNode(SNode<T> p)
        {
            next = p;
 
        }
 
        public SNode(T val)
        {
            data = val;
            next = null;
        }
 
        public SNode()
        {
            data = default(T);
            next = null;
        }
 
        public T Data
        {
            get { return data; }
            set { data = value; }
        }
 
        public SNode<T> Next
        {
            get { return next; }
            set { next = value; }
        }
    }
}

以下是单链表常用的操作：

1. 创建链表：创建一个空链表，可选是否带有头节点。

     2. 插入节点：在链表的指定位置（如头部、尾部或中间）插入一个新的节点。

         2.1 在单链表的开头插入一个新的节点

        2.2在链接表的两个节点之间插入节点

        2.3在链表末尾插入一个新的节点

在单链表的末尾插人节点是在链接表的两个节点之间插入节点的特殊情况,当 current为null时,previous 指向最后一个节点时,即可将新节点插人到链接表的末尾。如果在某些情况下,非常明确就是要将节点插人到链接表的末尾,可执行下面的算法步骤。

      3.删除操作

      从单链表中删除指定的节点,首先要判断列表是否为空。如果不为空的话,首先要搜索指定的节点,如果找到指定的节点则将其删除,否则给出没有找到相应节点的提示信息。当找到删除的节点后,在单链接表中删除指定的节点,通常分为下面的三种情况:

         3.1 删除单链表的头节点

         3.2 删除单链表中两个节点之间的节点

         3.3 删除单链表的尾节点

         在上述删除单向链接列表中两个节点之间的节点的算法中,如果搜索操作后，当前节点current 指向列表中最后一个节点,则说明要删除的节点是列表中最后一个节点。该算法也能删除单向链表达式末尾的节点。因此无需专门创建删除单向链接列表末尾节点的算法

     4.取表元素和定位元素

     取表元素和定位元素是指根据给定的序号或节点值,搜索对应该序号或值的节点。具体过程如下所示：

      5.反转链表：将链表中的节点按逆序排列。

      6.追加链表：将另外一个链表的头部追加到本链表。

以上操作是单链表最基本的操作，通过这些操作可以实现诸如栈、队列、哈希表等很多其他数据结构。需要注意的是，在进行链表操作时需要处理一些边界条件和异常情况，以确保链表的正常运行。

有关线性表的其他操作如求表长度、判断为空等操作在顺序表中的实现比较简单,参见以下的单链表C#代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace DataStructLibrary
{
    class SingleLinkList<T>:ILinarList<T>
    {
        public SNode<T> start;//单链表的头引用
        int length;//单链表长度
        /// <summary>
        /// 初始化单链表
        /// </summary>
        public SingleLinkList()
        {
            start = null;
        }
 
 
        /// <summary>
        /// 在单链表的末尾追加数据元素 data
        /// </summary>
        /// <param name="data"></param>
        public void InsertNode(T data)
        {
            if(start == null)
            {
                start = new SNode<T>(data);
                length++;
                return;
            }
            SNode<T> current = start;
            while(current.Next != null)
            {
                current = current.Next;
            }
            current.Next = new SNode<T>(data);
            length++;
        }
 
        /// <summary>
        /// 在单链表的第i个数据元素的位置前插入一个数据元素data
        /// </summary>
        /// <param name="data"></param>
        /// <param name="i"></param>
        public void InsertNode(T data, int i)
        {
            SNode<T> current;
            SNode<T> previous;
            if(i<1 || i> (length + 1))
            {
                Console.WriteLine("Position is error!");
                return;
            }
            SNode<T> newNode = new SNode<T>(data);
            //在空链表或第一个元素钱插入第一个元素
            if (i == 1)
            {
                newNode.Next = start;
                start = newNode;
                length++;
                return;
            }
            //单链表的两个元素中间插入一个元素
            current = start;
            previous = null;
            int j = 1;
            while(current != null && j<i)
            {
                previous = current;
                current = current.Next;
                j++;
            }
            if (j == i)
            {
                previous.Next = newNode;
                newNode.Next = current;
                length++;
            }
        }
 
        /// <summary>
        /// 删除单链表的第i个数据元素
        /// </summary>
        /// <param name="i"></param>
        public void DeleteNode(int i)
        {
            if(IsEmpty() || i < 1)
            {
                Console.WriteLine("Link is empty or Position is error");
            }
            SNode<T> current = start;
            if(i == 1)
            {
                start = current.Next;
                length--;
                return;
            }
            SNode<T> previus = null;
            int j = 1;
            while(current.Next != null && j<i)
            {
                previus = current;
                current = current.Next;
                j++;
            }
            if (j == i)
            {
                previus.Next = current.Next;
                current = current.Next;
                length--;
                return;
            }
            //第i个节点不存在
            Console.WriteLine("the ith node is not exist!");
 
        }
 
        /// <summary>
        /// 获取单链表的第i个数据元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T SearchNode(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return default(T);
            }
            SNode<T> current = start;
            int j = 1;
            while (current.Next != null && j<i)
            {
                current = current.Next;
                j++;
            }
            if (j == i)
            {
                return current.Data;
            }
            //第i个节点不存在
            Console.WriteLine("the ith node is not exist!");
            return default(T);
 
        }
 
        /// <summary>
        /// 在单链表中查找值为data的数据元素
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public T SearchNode(T data)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return default(T);
            }
            SNode<T> current = start;
            int i = 1;
            while(current != null && !current.Data.ToString().Contains(data.ToString()))
            {
                current = current.Next;
                i++;
            }
            if(current != null)
            {
                return current.Data;
            }
            return default(T);
        }
 
        /// <summary>
        /// 获取单链表的长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            return length;
        }
 
        /// <summary>
        /// 该函数将链表头节点反转后，重新作为链表的头节点。算法使用迭代方式实现，遍历链表并改变指针指向
        /// 例如链表头结点start:由原来的
        /// data:a,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:c,
        ///           next:null
        ///          ]
        ///     ] 
        ///翻转后的结果为:
        /// data:c,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:a,
        ///           next:null
        ///          ]
        ///     ] 
        /// </summary>
        public void ReverseList()
        {
            if (length ==1 || this.start == null)
            {
                return;
            }
            //定义 previous next 两个指针
            SNode<T> previous = null;
            SNode<T> next = null;
            SNode<T> current = this.start;
            //循环操作
            while (current != null)
            {
                //定义next为Head后面的数，定义previous为Head前面的数
                next = current.Next;
                current.Next = previous;//这一部分可以理解为previous是Head前面的那个数。
                //然后再把previous和Head都提前一位
                previous = current;
                current = next;
            }
            this.start = previous;
            //循环结束后，返回新的表头，即原来表头的最后一个数。
            return;
        }
 
 
 
        /// <summary>
        /// 将另外一个链表头部追加到本链表
        ///  /// 例如链表头结点start:由原来的
        /// data:a,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:c,
        ///           next:null
        ///          ]
        ///     ] 
        ///翻转后的结果为:
        /// data:a,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:c,
        ///           next:[
        ///                 data:x,
        ///                 next:[
        ///                       data:y,
        ///                       next:[
        ///                             data:z,
        ///                             next:null
        ///                            ]
        ///              
        ///                      ]
        ///               ]
        ///          ]
        ///     ] 
        /// </summary>
        /// <param name="nodeB">
        /// 追加的单链表头部数据
        /// 例如：
        /// data:x,
        /// next:[
        ///      data:y,
        ///      next:[
        ///           data:z,
        ///           next:null
        ///          ]
        ///     ]
        /// </param>
        public void Append(SNode<T> nodeB)
        {
            if (nodeB == null)
            {
                return;
            }
            InsertNode(nodeB.Data);
            SNode<T> tmpNode = nodeB.Next;
            while (tmpNode != null)
            {
                InsertNode(tmpNode.Data);
                tmpNode = tmpNode.Next;
            }
 
            return;
        }
 
        /// <summary>
        /// 清空单链表
        /// </summary>
        public void Clear()
        {
            start = null;
        }
 
        /// <summary>
        /// 判断单链表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            if(start == null)
            {
                return true;
            }
            return false;
        }
 
    }
}

实现方法和原理

单链表的实现方法和原理主要包括以下几个方面：

1. 节点：单链表中的节点由两部分组成，即数据域和指针域。数据域存储节点的数据元素，指针域指向下一个节点。节点可以用结构体来表示。

2. 头节点：头节点是链表中第一个节点前面额外添加的一个节点，不包含数据元素，但是包含对第一个节点的指针。头节点的作用在于简化链表的操作，使得插入、删除等操作更加便捷。

3. 指针操作：链表中节点之间的连接是通过指针来实现的。每个节点都有一个指针指向下一个节点，在插入或删除节点时需要修改节点之间的指针关系。

4. 遍历链表：遍历链表是指按顺序访问链表中的所有节点。通过遍历链表，可以读取或修改节点中的数据值，也可以计算链表的长度以及查找某个节点。

5. 内存管理：在插入和删除节点时需要分配或释放内存空间。为了避免内存泄漏和重复释放等问题，需要合理地管理内存空间。

6. 边界条件处理：在进行链表操作时需要处理一些边界条件和异常情况，例如链表为空、插入位置超出范围等情况，以确保链表的正常运行。

了解单链表的实现方法和原理对于理解链表性能和优化有很大帮助。同时，需要注意在具体实现时要根据实际情况进行合理的设计和优化，以提高代码的效率和可维护性。

应用场景和使用注意事项

单链表是一种常见的数据结构，常用于以下应用场景：

1. 实现栈和队列：单链表可以用来实现栈和队列。在栈中，元素只能从栈顶进出；在队列中，元素只能从队尾进，队首出。利用单链表的头插和尾插操作，可以很方便地实现这两种数据结构。

2. 内存分配：在计算机内存管理中，单链表常被用作动态内存分配的数据结构。通过链表节点之间的指针连接，可以动态地申请和释放内存块。

3. 音频和视频播放列表：单链表可以用来实现音频和视频播放列表。每个节点表示一个音频或视频文件，并保存下一个文件的位置。通过遍历链表，可以依次播放整个列表中的音频和视频。

4. 寻找环形结构：单链表也可以用来处理关于环形结构的问题，例如判断一个链表是否有环、找到环的入口等。

5. 缓存淘汰策略：在缓存系统中，当缓存空间已满时，需要淘汰一些数据来腾出空间。单链表可以用来维护缓存中的数据项，同时记录它们的使用情况。当需要淘汰数据时，可以选择最近最少使用的数据项进行淘汰，即删除单链表尾部的节点。

在使用单链表时需要注意以下几点：

1. 空指针问题：在链表操作中容易出现空指针问题，例如访问空链表或者一个不存在的节点等。为了避免这些问题，需要对输入参数进行判空处理。

2. 内存管理问题：在插入和删除节点时需要分配或释放内存空间，如果管理不当容易出现内存泄漏或者重复释放等问题。可以使用垃圾回收机制或手动管理内存空间来解决这些问题。

3. 边界条件问题：在进行链表操作时需要处理一些边界条件和异常情况，例如链表为空、插入位置超出范围等情况，以确保链表的正常运行。

4. 性能问题：在处理大规模数据时，单链表会存在一些性能问题，例如随机访问速度较慢、空间开销较大等。因此在实际应用中需要根据实际情况选择合适的数据结构。

算法和复杂度分析：

1. 了解单链表相关算法和复杂度分析，如如何判断一个链表是否有环、如何反转一个链表、如何合并两个有序链表等。掌握这些算法可以提高编程技能，同时加深对单链表的理解。

单链表算法和复杂度分析主要包括以下几个方面：

1. 遍历链表：遍历链表是访问链表中所有节点的基本操作，可以通过循环或递归实现。时间复杂度为 O(n)，其中 n 表示链表的长度。

2. 查找指定节点：在链表中查找指定节点，可以按照节点的位置或者节点的关键字进行搜索。线性搜索的时间复杂度为 O(n)，二分搜索的时间复杂度为 O(logn)。

3. 插入节点：在链表中插入一个新的节点，需要修改节点之间的指针关系。如果插入到开头或结尾，则时间复杂度为 O(1)，否则为 O(n)。

4. 删除节点：在链表中删除一个节点，需要修改节点之间的指针关系。如果删除的是头节点或尾节点，则时间复杂度为 O(1)，否则为 O(n)。

5. 反转链表：将链表中的节点按逆序排列，需要修改节点之间的指针关系。可以使用迭代或递归实现，时间复杂度均为 O(n)。

6. 合并链表：将两个有序链表合并成一个新的有序链表，需要逐个比较两个链表的节点并合并。时间复杂度为 O(m+n)，其中 m 和 n 分别表示两个链表的长度。

需要注意的是，在进行链表算法时需要注意处理一些边界条件和异常情况，例如链表为空、插入位置超出范围等情况。同时，在具体实现时要根据实际情况进行合理的设计和优化，以提高代码的效率和可维护性。

与其他数据结构的比较：

1. 了解单链表与其他数据结构的比较，例如数组、双向链表等。了解它们的优缺点和适用场景，可以更好地选择合适的数据结构来解决实际问题。

单链表与其他数据结构的比较主要包括以下几个方面：

1. 数组：数组和单链表都可以用来表示序列，但是它们的实现方式不同。数组在内存中是连续分配的一段存储空间，可以直接访问任意元素。而单链表需要通过指针来连接节点，只能从前往后遍历。由于单链表每个节点只有一个指针，因此空间开销较小；而数组需要预先分配一定大小的内存空间，在插入或删除元素时可能会浪费一部分空间。

2. 栈和队列：栈和队列是两种常见的数据结构，可以使用数组或者单链表进行实现。用数组实现的栈和队列可以随机访问，但是插入或删除元素时需要移动其他元素，时间复杂度为 O(n)。而用单链表实现的栈和队列可以在头部或尾部进行插入和删除操作，时间复杂度为 O(1)。

3. 哈希表：哈希表是一种基于哈希函数实现的数据结构，可以快速地查找和修改元素。在哈希表的实现中，通常使用数组来保存元素，同时使用链表或者其他数据结构来处理哈希冲突。单链表可以作为哈希表中链式存储的一种实现方式，但是由于只能从前往后遍历，因此可能会影响哈希表的查询效率。

4. 红黑树：红黑树是一种自平衡的二叉搜索树，可以实现快速的插入、删除和查找操作。相比于单链表等数据结构，红黑树的时间复杂度更低，并且支持范围查找和排名操作等高级功能。但是相应地，在实现上也更为复杂，需要处理各种旋转和着色操作。

综上所述，单链表适合表示序列，并且支持动态插入和删除操作，空间开销较小。相比于数组，其插入和删除元素的时间复杂度更低；而相比于栈和队列等其他数据结构，可以更方便地在中间位置进行插入和删除操作。但是在查询和排序等操作中性能较差，不如红黑树等高级数据结构。

PS：如有错漏之处，敬请指正