线性表（三）——线性链表（单链表）

线性链表（单链表）

构造原理

用一组地址任意的存储单元(连续的或不连续的)依次存储表中各个数据元素, 数据元素之间的逻辑关系通过指针间接地反映出来。

线性表的这种存储结构称为线性链表，又称为单链表。
在C语言中线性链表的定义如下：

typedef struct node { 
    ElemType data;
    struct node *link;
}LNode, *LinkList;          //定义一个线性链表类型
//上述代码相当于给结构体 node 定义了一个别名LNode和一个指针别名LinkList


LinkList list;                //声明一个线性链表List，List为整个线性链表的头指针
//等价于 struct node *list; 等价于 LNode *list;

基本操作

1、求线性链表的长度
1、非递归算法：

int LENGTH( LinkList list ){
    LinkList p=list;
    int n=0;        /* 链表的长度置初值0*/
    while(p!=NULL){
        p=p->link;
        n++;
    }
    return n;       /* 返回链表的长度n */
}

此算法的时间复杂度O(n)
2、递归算法：

int LENGTH(LinkList list){
    if(list != NULL)
        return 1+LENGTH( list->link);
    else 
        return 0;
}

链表本身就是一种递归结构，但递归算法时间效率往往比非递归低。

2、建立一个线性链表
从头到尾建立链表

LinkList CREATE( int n ){
    LinkList p, r, list=NULL;
    datatype a;
    for(i=1;i<=n;i++){
        READ(a);          /* 取一个数据元素*/
        p=(LinkList)malloc(sizeof(LNode));        //申请一个新的链结点   需要引入alloc.h
        p->data=a;
        p->link=NULL;
        if (list==NULL)
            list=p;
        else
            r->link=p;           /* 将新结点链接在链表尾部*/
        r=p;                        //指针变量r总是指向链表末尾
    }
    return list;
}

该算法的时间复杂度O(n)
3、在非空线性链表的第一个结点前插入一个数据信息为item 的新结点

void INSERTLINK1( LinkList &list, ElemType item ){
    //list存放链表的首地址
    LinkList p;
    p=(LinkList)malloc(sizeof(LNode));
    p->data=item;                /* 将item送新结点数据域*/
    p->link=list;                   /* 将list送新结点指针域*/
    list=p;                           /* 修改指针list的指向*/ 
}

该算法的时间复杂度为O(1)，与链表长度n无关
4、在线性链表中由指针q 指的链结点之后插入一个数据信息为item 的链结点

void INSERTLINK2( LinkList &list, LinkList q,ElemType item ){ 
    LinkList p;
    p=(LinkList)malloc(sizeof(LNode));
    p->data=item;          /* 将item送新结点数据域*/
    if (list==NULL) {       /* 若原链表为空*/
        list=p;
        p->link=NULL; 
    }else{            /* 若原链表为非空*/
        p->link=q->link;
        q->link=p;
    }
}

该算法的时间复杂度为O(1)，与链表长度n无关
4、从非空线性链表中删除q指的链结点，设q的直接前驱结点由r指出

void DELETELINK1( LinkList &list, LinkList r, LinkList q ){
    if (q==list) 
        list=q->link;                /* 删除链表的第一个链结点*/
    else
        r->link=q->link;          /* 删除q指的链结点*/
    free(q);                          /* 释放被删除的结点空间*/
}

该算法的时间复杂度为O(1)，与链表长度n无关
5、从非空线性链表中删除q指的链结点，不知q的直接前驱节点
比4增加了一个寻找q直接前驱节点r的过程

void DELETELINK2( LinkList &list, LinkList q ){
    LinkList r;
    if (q==list) {      /*当删除链表第一个结点*/
        list=list->link;
        free(q);        /*释放被删除结点的空间*/
    }else {
        r=list;                             //寻找q的直接前驱节点r
        while( r->link!=q &&r->link!=NULL) 
            r=r->link;      /*移向下一个链结点*/
        if (r->link!=NULL){ 
            r->link=q->link;
            free(q); 
        }
    } 
}

该算法的时间复杂度为O(n)

线性表链式存储结构的特点

1、优点
(1)存储空间动态分配，可以根据实际需要使用。
(2)不需要地址连续的存储空间。
(3)插入/删除操作只须通过修改指针实现,不必移动数据元素，操作的时间效率较高。（无论位于链表何处，无论链表的长度如何，插入和删除操作的时间都是Ο(1)）
2、缺点
(1)每个链结点需要设置指针域(存储密度小)。
(2)是一种非随机存储结构，查找、定位等操作要通过顺序扫描链表实现，时间效率较低。（时间为Ο(n)）