单链表的结构

单链表中的每个节点由两个字段组成，一个是数据字段，一个是指向下一个节点的指针字段，我们称这个指针为后驱指针。对于一个单链表来说，它有唯一的一个头节点，也只有唯一的一个尾节点，尾节点的指针始终为NULL。

由于单链表中每个节点都知道它的后驱节点，但是却不知道它的前驱节点，所以在单链表的各种操作中，头节点指针就至关重要，因为只有知道了头节点的地址，我们才能遍历链表、对链表进行插入删除等操作。我们需要通过定义一个头节点的指针变量存储头节点地址，当然为了方便起见，我们也定义一个尾节点指针方便操作。在所有的链表示例代码中，我们都将头节点变量名定义为first，尾节点变量定义为last，所以first和last分别指向链表的第一个节点和最后一个节点。

单链表的定义

我们会在程序中声明Node类和LinkedList类，LinkedList中包含了两个非常重要的指针：头节点指针first和尾节点指针last，还包含了对单链表的所有操作方法，后面我们会一一介绍。

public class Node
{
    public int Data;//数据元素
    public Node Next;//指向下一个节点的指针
    public Node(int data)
    {
        this.Data = data;
    }
}
public class LinkedList
{
    public Node first;//头节点指针
    public Node last;//尾节点指针
}

Node类中我们声明了一个Data字段表示节点的数据，实际上数据字段可以有多个，我们可以在Node类中声明其他字段，比如Data1、Data2等。我们的示例代码为了方便阅读和理解只声明一个Data字段。

算法1:创建单链表

创建单链表指创建包含一组节点的单链表。如依次输入0,1,2,3,4,5来创建单链表，有两种创建方法，前插法和后插法。
前插法通过将新节点插入链表的头部来构建单链表，也就是说，每次插入的时候，新节点将作为头节点地址。具体的插入示意图如下，红色节点代表每次需要插入的节点，红色箭头代表每次插入新节点需要调整的指针:

头插法的伪代码实现主要分两步：
1、将新节点的后驱指针指向first：newNode.Next=first;
2、将first指针指向新节点：first=newNode;
头插法具体实现代码如下：

public void InsertInHead(int data)
{
    Node newNode = new Node(data);
    newNode.Next = first;//步骤1、将新节点的后驱指针指向first
    first = newNode;     //步骤2、将first指针指向新节点
    if (last == null)
    {
        last = newNode;
    }
}

后插法和前插法恰好相反，它是将每次插入的节点插入到链表的尾部来构建单链表。具体操作图如下：

后插法的伪代码实现主要分两步：
1、将尾节点的后驱指针指向新节点：last.Next=newNode;
2、将last指针指向新节点：last=newNode;
后插法具体实现代码如下：

public void InsertInLast(int data)
{
    Node newNode = new Node(data);
    if (first == null)
    {
        first = newNode;
        last = newNode;
    }
    last.Next = newNode;//步骤1、将尾节点的后驱指针指向新节点
    last = newNode;//步骤2、将last指针指向新节点
}

算法2:查找

单链表的查找过程和顺序表的查找过程类似。从链表的头节点first开始，按照每个节点的后驱指针，依次往后顺序查找，直到查到满足条件的节点为止。单链表查找有两种查找算法，一种是按照索引查找(查找单链表中的第几个节点)，第二种是按照值查找(查找节点值和待查找值相同的节点)。
按索引查找具体示例代码如下：

public Node GetByIndex(int index)
{
    Node currentNode = first;
    int i = 1;
    while (i != index)
    {
        currentNode = currentNode.Next;
        i++;
    }
    return currentNode;
}

按值查找的具体示例代码如下:

public Node GetByData(int data)
{
    Node currentNode = first;
    while (currentNode != null && currentNode.Data != data)
    {
        currentNode = currentNode.Next;
    }
    return currentNode;
}

算法3:删除单链表中的节点

删除节点的操作分三种情况，删除头节点、删除中间节点、删除尾部节点。三种删除的具体示意图如下：
1、删除头节点：直接将头节点指针指向第二个节点，伪代码为：first=first.Next;

2、删除中间节点：直接将欲删除节点的前一个节点的指针指向欲删除节点的后一个节点即可。伪代码为：pre.Next=deleteNode.Next

3、删除尾部节点：将尾节点的前一个节点的指针设置为NULL。伪代码为：last=preNode; last.Next=null;

删除节点同样有两种删除算法：按索引删除和按值删除。按索引删除指的是删除链表中的第n个节点。按值删除指的是删除链表中节点值为data的节点。删除同样需要从链表的头节点开始查找，直到找到欲删除的那个节点删除即可！
按索引删除的示例代码如下：

public void DeleteByIndex(int index)
{
    //删除第一个节点
    if (index == 1)
    {
        first = first.Next;
        if (first == null)
        {
            last = null;
        }
        return;
    }

    Node current = first;
    Node pre = null;
    int i = 1;
    //找到第i个节点
    while (i != index)
    {
        pre = current;
        current = current.Next;
        i++;
    }

    pre.Next = current.Next;
    //如果是最后一个节点
    if (current.Next == null)
    {
        last = pre;
    }
}

按值删除的具体示例代码如下：

public void DeleteByValue(int data)
{
    if (first == null)
    {
        return;
    }
    Node current = first;
    Node pre = null;

    while (current != null && current.Data != data)
    {
        pre = current;
        current = current.Next;
    }

    //没有找到要删除的节点
    if (current == null)
    {
        return;
    }
    //删除头节点
    if (current == first)
    {
        first = first.Next;
        if (first == null)
        {
            last = null;
        }
        return;
    }
    //删除尾节点
    if (current == last)
    {
        pre.Next = null;
        last = pre;
        return;
    }
    //删除中间节点
    pre.Next = current.Next;
}

算法4:在单链表中插入一个元素

插入指的是在第i个节点的位置插入一个元素。插入元素也分为三种情况：在头节点插入、在中间位置插入、在尾部插入。由于前面介绍的前插法和后插法分别代表在链表的头部和尾部插入新节点，所以这里就只介绍一下在中间插入元素的具体操作流程。假设在第i个节点的位置插入一个新节点。其实只需要将新节点的指针指向第i个节点，将第(i-1)个节点的指针指向新节点，具体请看下图：
插入元素的伪代码实现主要分两步：
1、新节点的指针指向欲插入位置的节点：newNode.Next=currentNode;
2、欲插入位置前一个节点的指针指向新节点：preNode.Next=newNode;
具体代码如下：

public void Insert(int index, int data)
{
    int length = GetLength();
    //头节点插入
    if (index == 1)
    {
        InsertInHead(index);
        return;
    }
    //尾节点插入
    if(index > length)
    {
        InsertInLast(index);
        return;
    }
    //中间插入
    int i = 1;
    Node currentNode = first;
    Node preNode = null;
    while (i != index)
    {
        preNode = currentNode;
        currentNode = currentNode.Next;
        i++;
    }

    Node newNode = new Node(data);
    newNode.Next = currentNode;//步骤1、新节点的指针指向欲插入位置的节点
    preNode.Next = newNode;//步骤2、欲插入位置前一个节点的指针指向新节点
}

其他算法

除了以上的几个算法之外，还有一些别的算法，比如：将两个链表串联起来返回一个新的链表、将链表反转、链表清空、获取链表长度、判断链表是否为空等，这两个算法在这里就不给大家实现了，有兴趣的话，大家去可以去看gitee中的代码

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/02LinkedList.cs

总结

优点：单链表的删除和插入效率很高，因为删除和插入只需要修改对应的节点指针，不需要大量的数据移动，而且它的内存数量不受限制，很容易进行动态扩展。
缺点：随机访问效率慢，由于单链表的地址在内存中并不连续，只能通过指针从头节点开始一个个顺序查找，所以它的随机访问效率就比数组低很多。

单链表