由于顺序表的插入，删除操作需要移动大量的元素，影响了运算效率，由此线性表的链式存储便应运而生。链式存储线性表时，逻辑上连续的元素物理结构上不需要连续，它们彼此可以通过“链”建立起数据元素之间的逻辑关系，因此对于线性表的插入，删除操作并不需要移动元素，只需修改指针即可。

一.单链表的定义

线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表结点的结构如下图所示，其中，data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。

对于每一个结点的描述如下：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

利用单链表在解决顺序表需要大量的连续存储空间的缺点的同时，也引入了一些不可避免的缺点。比如因为需要额外的指针域，因此需要额外的存储空间；由于单链表是离散的分布在存储空间中，所以单链表不能完成随机存取的操作。

为了方便标识一个单链表，我们一般需要引入头指针来操作整个单链表。此外，为了统一增加和删除元素的操作，我们一般会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的指针域指向单链表的第一个元素结点。

注：这里应该注意区分头指针和头结点。而不管单链表有没有头结点，头指针总是指向单链表的第一个结点。简单说就是如果单链表有头结点，那么头指针将指向头结点；如果单链表没有头结点，头指针将指向单链表的第一个结点。此处我们应该注意到一般情况下头结点内不存储任何信息。这里说明下，如果后面的例题中没有具体说明，一般都是建立有头结点的单链表。

引入头节点后，可以带来两个优点：

• 由于开始节点的位置被存放在头节点的指针域中，所以在链表的第一个位置上操作与表其他位置上的操作一致，无需进行特殊处理。
• 无论链表是否为空，其头指针都是指向头节点的非空指针（在空表中，头节点的指针域为空），因此也使得空表和非空表的处理方式变得统一。

二.单链表基本操作的实现

2.1建立单链表

2.1.1头插法建立单链表

该方法中，首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将其放置到头结点之后。如下图所示：

算法描述如下：

typedef int ElemType;
LinkList CreateLink(LNode *head)
{
    LNode *s;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;

        s->next=head->next;
        head->next=s;

        scanf("%d",&x);
    }

    return head;
}

注：采用头插法建立单链表，读入数据的顺序与生成的链表中的元素的顺序刚好是相反的。
每个结点插入的时间复杂度为O(1)，设单链表长为n，则总的时间复杂度为O(n)。

2.1.2尾插法建立单链表

该方法中同样首先建立一个具有头结点的空单链表，然后每生成一个读取到数据的新节点，就将它插入到表尾；为了达到这样的目的，必须增加一个尾指针r，使其始终指向当前链表的尾结点。如下图所示

算法描述如下

LinkList CreatLink(LNode *head)
{   
    LNode *s;
    LNode *r=head;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;

        r->next=s;
        r=s;

        scanf("%d",&x);
    }
    s->next=NULL;
    return head;    
}

注：因为附加设置了一个指向表尾的尾指针r，因此每个结点插入的时间复杂度同样为O(1)，设单链表长为n，则总的时间复杂度为O(n)。

2.2按序号查找结点值

从单链表的第一个结点出发，顺着指针next域逐个从上往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
算法描述如下：

LNode* GetElem(LNode *head, ElemType i)
{
    LNode *p=head->next;
    int j=1;
    if(i==0){
        printf("The Link is empty!
");
        return head;
    }
    if(i<=0){
        printf("The postion is illegal!
");
        return NULL;
    }
    while(p){
        if(j==i){
            printf("Find success!
");
            break;
        }
        p=p->next;
        j++;
    }
    return p;   
}

注：按序号查找的时间复杂度为O(n)。

2.3按值查找结点值

从单链表的第一个结点开始，由前往后依次比较各结点数据域的值，若某结点数据域的值等于给定值x，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。
算法描述如下：

LNode* GetElem(LNode *head, ElemType x)
{
    LNode *p=head->next;
    if(head==NULL){
        printf("The LinkList is empty!
");
        return head;
    }
    while(p){
        if(p->data==x){
            printf("Find the number!
");
            return p;
        }
        p=p->next;  
    }
    printf("Not Find the number!
");
    return NULL;
}

注：按值查找的时间复杂度为O(n)。

2.4插入结点

2.4.1插入后继结点

插入操作是将值为x的新结点插入倒单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新的结点。
算法首先需要调用GetElem(L,i-1)查找第i−1个结点。假设返回的第i−1个结点为p，然后令新结点s的指针域指向p的后继结点，再令结点p的指针域插入新的结点*s。其操作过程如下图所示：

算法描述如下：

LNode* GetElem(LNode *head, int i)
{
    if(i==0){
        printf("The LinkList is empty!
");
        return head;
    }
    if(i<=0){
        printf("The LinkList is illegal!
");
        return NULL;
    }

    LNode *p=head->next;
    int j=1;
    while(p){
        if(j==i){
            printf("Find it!The postion is %dth
", j);
            break;
        }
        j++;
        p=p->next;
    }
    return p;
}

void InertElem(LNode *p, ElemType x){
    LNode *s;
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;

    s->next=p->next;
    p->next=s;
}

算法中，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。

2.4.1插入前驱结点

在方法一中，我们可以在指针p指向的结点后面插入新的结点s，但是有时如果我们需要在指针p指向的结点前面插入新的结点s时，上述算法明显是办不到的。
但是如果我们换个思路，将指针p指向的结点和s结点它们之间的数据域做一次交换，依旧将s结点插入到指针p指向的结点后面，如此我们便将前插操作变为了向指针p指向的结点的后插操作，并且在逻辑上仍旧满足条件。
算法描述如下：

void InertElem(LNode *p, ElemType x){
    LNode *s;
    s=(LNode*)malloc(sizeof(LNode));
    s->data=x;

    ElemType temp;
    temp=p->data;
    p->data=s->data;
    s->data=temp;

    s->next=p->next;
    p->next=s;  
}

注：同方法一相同，时间的主要开销是查找第i−1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。

2.5删除结点

2.5.1删除后继结点

删除结点操作即将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点（即将要被删除结点的前驱结点），然后在删除第i个结点。其操作过程如下图所示：

假设我们要删除指针q指向的结点，那么我们首先通过遍历所有结点找到指针q指向的结点的前驱结点p，为了实现算法，我们只需修改指针p的指针域，将指针p的指针域next直接指向指针q指向的结点的指针域next所指的下一个结点便可。
算法描述如下：

void DelLNode(LNode *head, int i)
{
    LNode *p=head;
    LNode *q=head->next;
    while(i){
        p=q;
        q=q->next;
        i--;
    }
    p->next=q->next;
    free(q);
}

注：删除操作中，时间的主要开销是查找第i−1个元素，因此时间复杂度为O(n)。若是删除给定结点的后继结点，则时间复杂度为O(1)。

2.5.2删除自身结点

有时我们需要删除指针所指向的自身结点（比如指针p指向的结点），此时如果继续使用上述方法明显是不可能的。我们采用与2.4.1插入前驱结点相似的方法，将指针p所指向的结点的数据域与指针q所指向的结点的数据域进行一次交换（因为是一次删除操作，我们只需要将指针q指向的结点的数据域直接赋值为指针p指向的结点的数据域便可），这样，我们就又变成了删除指针q指向的结点的操作。
算法描述如下：

void DelList(LNode *head, int i)
{
    LNode *p=head;
    LNode *q=p->next;

    while(i){
        p=q;
        q=q->next;
        i--;
    }

    p->data=q->data;

    p->next=q->next;
    free(q);
}

注：与上述算法一样，删除操作中，时间的主要开销是查找第i个元素，因此时间复杂度为O(n)。若是删除给定的结点，则时间复杂度为O(1)。

2.5求链表长度

求表长实际上就是计算单链表中数据结点（不含头节点）的个数。为了达到这个目的，我们只需对链表进行一次遍历，同时设置计数器对每次访问到的结点计数便可。
算法描述如下：

int LenLink(LNode *head)
{
    int cnt=0;
    LNode *p=head->next;
    while(p){
        p=p->next;
        cnt++;
    }
    return cnt;
}

注：遍历操作中需要访问所有结点，因此时间复杂度为O(n)。