链表分为：单链表，双链表，循环链表，静态链表

一，单链表的定义

在内存空间中，各个节点在逻辑上相邻，但在物理上不相邻。

在单个的结点内部需要存放 数据域 和 指针域（存放指向下一个结点的指针）

优点：不要求一大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定的空间存放指针。

定义

typedef struct LNode{         //定义单链表结点类型
    int data;                 //每个节点存放一个数据元素
    struct LNode * next;       //指针指向下一个节点
}LNode,* LinkList;

定义一个结构体类型，内部分别存放 元素 和 指向下一个节点的指针。

并且为了后续方便，在此使用typedef函数，将 struct LNode 简称为LNode.

初始化单链表

//初始化单链表
bool InitList(LinkList &L) {
    /*无头结点
    L = NULL;           //空表，暂未节点
    return true;
    */
    //带头结点
    
    
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L->next = NULL;
    return true;
}
void test() {
    LinkList L;       //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
}
//判断单链表是否为空
bool Empty(LinkList L) {
    return (L == NULL);
}

 假设我们以及建立了这样一个单链表

二，单链表插入和删除

插入

1）按位序插入

假设我们将在2，3结点中插入一个新结点

只需要将2结点中的next指针指向新结点，将原指针赋值给新结点的next

//按位插入（带头结点）

 //在单链表L中，第i个结点上插入数据域是e的新结点。
bool ListInsert(LinkList &L ,int i,int  e) {  //在单链表L中，第i个结点上插入数据域是e的新结点。
    if (i < 1) {      
        return false;
    }
    LNode * p;  //指针P指向当前扫描到的结点
    int j = 0;
    p = L; //p指向头结点（无数据）
    while (p != NULL && j<i-1){//循环找到第i-1个结点
        p = p->next;
        j++;
    } 
    if (p == NULL) { //i值不合法
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

归纳：从头结点开始循环，找到第i-1位的结点。将s（新结点）的地址赋值给i-1位的结点的next，将原来的第i位结点的地址赋值给s的next即可。

*注意i的合法性。

平均时间复杂度o (n)；

*如果不带头结点：（需要特殊处理i =1的情况 ）

/*  不带头结点
        if (i == 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->next = L;
        s->data = e;
        L = s;
        return true;
    }
    */

后插操作

只需将结点1的指针指向新结点，将原指针赋值给新结点的next

 （在结点p后面插入一个元素e）

//按位插入（后插）
bool InsertNextNode(LNode* p, int e) {   //在结点p后面插入一个元素e

    //判断结点p是否存在
    if (p == NULL) {
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) {    //分配内存失败
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
    
}

前插操作

//指定结点的前插
bool InsertPriorNode(LNode* p, int e) {  //在结点P前插入一个新元素e
    //数据跑路型(无需寻找p结点的前驱结点)
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = p->data;
    p->data = e;
    s->next = p->next;
    p->next = s;
}
bool InsertPriorNode2(LNode* t, LNode* s) { //在结点P前插入一个新结点S
    if (t = NULL) {
        return false;
    }
    if (s == NULL) {
        return false;
    }
    s->next = t->next;
    t->next = s;
    int temp = t->data;
    t->data = s->data;
    s->data = temp;
    
} 

删除

//按位序删除

若要将第三个结点删除：只需将它的下一个结点存放的指针赋值给第二个结点即可

最后通过free函数释放掉要删除的结点的内存即可

bool ListDelete(LinkList& L, int i, int e) {  //将单链表中第i个结点删除
    if (i < 1) {
        return false;
    }
    int j = 0;
    LNode* K;
    K = L;
    //循环找到第i-1位的结点
    while (K!=NULL && j<i-1)  
    {   
        K = K->next;
        j++;
    }
    //判断 i-1位结点 是否存在以及 i位结点是否存在
    if (K == NULL|| K->next==NULL) {
        return false;
    }
    //创一个新的结点q，令其等于 要删除的第i位结点
    LNode* q;
    q = K->next;
    K->next = q->next;         //将i结点中存放下一位结点的指针赋值给 i-1结点
    e = q->data;               //提出删除结点的值
    free(q);                   //释放内存
    return true;
}

//按结点删除

若要将1结点删除，则将它的下结点的data和next复制到1结点即可

最后释放下节点。

//删除指定结点
bool  DeleteNode(LNode* p) {
    if (p == NULL) {
        return false;
    }
    LNode* q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}

 

**但如果要删除的结点是单链表中的最后一个结点，则会发生错误。

删除最后一个结点需要遍历整个单链表，同上。

总结：单链表不能逆向检索，有时会不太方便。

查找

1）按位查找

//单链表的查找
//单链表的按位查找
LNode * GetElem(LinkList & L, int i) {
    if (i < 1) {
        return NULL;
    }
    LNode * p;
    p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;

}

2）按值查找与求表长

//按值查找
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L;
    while (p != NULL && p->data != e)
    {
        p = p->next;

    }
    return p;
}
//求表长
int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

单链表的建立

单链表的建立分为头插法和尾插法

一，尾插法创建单链表

//尾插法插入数据
LinkList TailInsert(LinkList& L) {          //用户输入创建单链表
    int x;
    L = (LinkList)malloc(sizeof(LNode));    //初始化空表
    LNode* s,* r = L;
    scanf("%d", &x);
    while (x != 999)  //输入999结束
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", x);
    }
    r->next = NULL;
    return L;
} 

 

 

 二，头插法建立单链表

 //头插法建立单链表
LinkList HeadInsert(LinkList& L) {
    LNode* s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next == NULL;   //防止内存 中的脏数据
    scanf("%d", &x);
    while (x != 9999)  //输入9999结束建立
    {
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", x);
    }
    return L;
}