什么是链表？

通过研究证明，怎么学好数据结构？怎么入门？需要学些什么东西？链表是数据结构的重要部分，学好用好链表，在解题的过程中，思路将更加清晰，链表作为数据结果的基础之一，本篇将会通过图文和代码展示的形式系统的介绍。

什么是链表？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

顺序存储和链式存储

（1）数组—顺序存储

数组作为一个顺序储存方式的数据结构，可是有大作为的，它的灵活使用为我们的程序设计带来了大量的便利；

但数组最大的缺点就是我们的插入和删除时需要移动大量的元素，所以，很多人想到需要大量的消耗时间，以及冗余度就想放弃或寻求别的方法。

以C语言数组插入一个元素为例，当我们需要在一个数组{1,2,3,4}的第1个元素后的位置插入一个’A’时，我们需要做的有：

1. 将第1个元素后的整体元素后移，形成新的数组{1,2,2,3,4}

2. 再将第2个元素位置的元素替换为我们所需要的元素’A’

3. 最终形成我们的预期，这需要很多的操作喔。

上图可以看出，使用数组都有这两大缺点：

1. 插入删除操作所需要移动的元素很多，浪费算力。

2. 必须为数组开足够的空间，否则有溢出风险。

（2）链表—链式存储

由于数组的这些缺点，自然而然的就产生链表的思想。

链表通过不连续的储存方式，自适应内存大小，以及指针的灵活使用，巧妙的简化了上述的内容。

链表的基本思维是，利用结构体的设置，额外开辟出一份内存空间去作指针，它总是指向下一个结点，一个个结点通过NEXT指针相互串联，就形成了链表。

其中DATA为自定义的数据类型，NEXT为指向下一个链表结点的指针，通过访问NEXT，可以引导我们去访问链表的下一个结点。

对于一连串的结点而言，就形成了链表如下图：

相比起数组，链表解决了数组不方便移动，插入，删除元素的弊端，但相应的，链表付出了更加大的内存牺牲换来的这些功能的实现。

链表概述

包含单链表，双链表，循环单链表，实际应用中的功能不同，但实现方式都差不多。

链表与数组的区别

　　回忆下数组的概念 ，所谓数组，是相同数据类型的元素按一定顺序排列的集合。根据概念我们可以知道数组在内存中连续，链表不连续；由于不同的存储方式导致数组静态分配内存，链表动态分配内存，数组元素在栈区，链表元素在堆区；由于数组在内存中连续，我们可以利用下标定位，时间复杂度为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）链表还有删除、获取、查找等操作，这些都相对简单，大家可以在做题中理解。