1 单链表的定义

线性表的链式存储又称为单链表。它是指通过一组任意的存储单元来存储线性表中的数据元素。
单链表的结点类型的描述如下：

typedef int ElemType;
typedef struct LNode {   //定义单链表结点类型
    ElemType data;     //数据域
    struct LNode *next;   //指针域
} LNode, *LinkList;

2 单链表上基本操作的实现

设结点的数据类型是整型，32767作为结束标志。
1）采用头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新节点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

LNode *createLinkList(void) {
    int data;
    LNode *head, *p;
    //创建头结点
    head = (LNode *) malloc(sizeof(LNode));
    //初始为空链表
    head->next = NULL;
    while (1) {
        scanf("%d", &data);
        if (data == 32767) {
            break;
        }
        p = (LNode *) malloc(sizeof(LNode));
        //数据域赋值
        p->data = data;
        //新结点总是作为第一个结点    
        p->next = head->next;
        head->next = p;
    }
    return head;
}

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

2）采用尾插法建立单链表
头插法生成的链表中结点的次序与输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。为此必须增加一个尾指针last，使其始终指向当前链表的尾结点。

LNode *createLinkList2(void) {
    int data;
    LNode *head, *last, *p;
    //创建头结点
    head = (LNode *) malloc(sizeof(LNode));
    //初始尾结点就是头结点
    last = head;
    while (1) {
        scanf("%d", &data);
        if (data == 32767) {
            break;
        }
        p = (LNode *) malloc(sizeof(LNode));
        p->data = data;
        //头结点的下一个为p
        last->next = p;
        //last指向新的尾结点
        last = p;
    }
    last->next = NULL;
    return head;
}

时间负责度为O(n)。

3）按序号查找结点值
在单链表中从第一个结点出发，顺指针next逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

//取出单链表L（带头结点）第i个位置的结点指针
LNode *getElem(LinkList L, int i) {
    int j = 1;
    LNode *p = L->next;
    if (i == 0) {
        return L;
    }
    if (i < 1) {
        return NULL;
    }
    //while(p)等价于while(p != NULL)
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

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

4）按值查找表结点
从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的值；若整个单链表中没有这样的结点，则返回NULL。

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p && e != p->data) {
        p = p->next;
    }
    return p;
}

5）插入结点操作
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。

void InsertLNode(LNode *L, int i, ElemType e) {
    int j = 0;
    LNode *p;
    p = L->next;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (j != i - 1) {
        printf("i太大或i为0");
    } else {
        LNode *q = (LNode *) malloc(sizeof(LNode));
        q->data = e;
        //以下两步不能颠倒
        q->next = p->next;
        p->next = q;
    }
}

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

6）删除结点操作
①按序号删除
删除第i个结点。

void DeleteLinkList(LNode *L, int i) {
    int j = 0;
    LNode *p = L->next;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (j != i - 1) {
        printf("i太大或i为0");
    } else {
        LNode *q = p->next;
        p->next = q->next;
        //释放结点的存储空间f
        free(q);
    }
}

时间复杂度为O(n)。
②按值删除
删除单链表中值为key的第一个结点。

void DeleteLinkList2(LNode *L, ElemType e) {
    LNode *p = L;
    LNode *q = p->next;
    while (q && e != q->data) {
        p = q;
        q = q->next;
    }
    if (q->data != e) {
        printf("所要删除的结点不存在");
    } else {
        p->next = q->next;
        free(q);
    }
}

时间复杂度为O(n)。

③变形一：
删除单链表中值为key的所有结点。

void DeleteLinkList3(LNode *L, ElemType e) {
    LNode *p = L;
    LNode *q = p->next;
    while (q) {
        if (e == q->data) {
            p->next = q->next;
            free(q);
        } else {
            p = q;
            q = q->next;
        }
    }
}

④变形二：
删除单链表中所有值重复的结点，使得所有结点的值都不相同。

void DeleteLinkList4(LNode *L) {
    LNode *p = L->next;
    LNode *q, *ptr;
    while (p) {
        q = p;
        ptr = q->next;
        while (ptr && ptr->data != p->data) {
            q = ptr;
            ptr = ptr->next;
        }
        if (ptr->data == p->data) {
            q->next = ptr->next;
            free(ptr);
        }
        p = p->next;
    }
}

时间复杂度O(n2)，需优化。