完整代碼需結(jié)合前面一篇順序表數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)-線性表之順序表各種操作
網(wǎng)易云課堂小甲魚課程鏈接：數(shù)據(jù)結(jié)構(gòu)與算法

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)，最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量的元素鸭轮，這顯然需要耗費(fèi)時(shí)間。導(dǎo)致這個(gè)問(wèn)題的原因是在于相鄰元素的存儲(chǔ)位置具有鄰居關(guān)系盾戴，它們?cè)趦?nèi)存中的位置是緊挨著的，中間沒(méi)有間隙楚堤，當(dāng)然無(wú)法快速插入和刪除逾雄。

定義

• 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，這組存儲(chǔ)單元可以存放在內(nèi)存中未被占用的任意位置品追。
• 相比順序存儲(chǔ)結(jié)構(gòu)玄括，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，除了需要存儲(chǔ)數(shù)據(jù)元素信息之外肉瓦，還需要存儲(chǔ)它的后繼元素的存儲(chǔ)地址(指針)遭京。
• 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素信息的域，指針域：存儲(chǔ)直接后繼位置的域泞莉。指針域中存儲(chǔ)的信息成為指針或鏈哪雕。這兩部分信息組成數(shù)據(jù)元素成為存儲(chǔ)映像，成為結(jié)點(diǎn)(Node)鲫趁。
  
  結(jié)點(diǎn)結(jié)構(gòu)node
• 鏈?zhǔn)浇Y(jié)構(gòu)：n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表斯嚎，即為線性表(a1,a2,a3,...an)；
• 如果鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域挨厚，那就叫做單鏈表孝扛。

單鏈表

小甲魚視屏中的單鏈表

• 頭指針：鏈表中的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。
• 線性表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?NULL)幽崩。

• 看圖說(shuō)明:

  
  
  單鏈表的特點(diǎn)

頭結(jié)點(diǎn)和頭指針

• 頭結(jié)點(diǎn)：

  • 頭結(jié)點(diǎn)是加在單鏈表之前附設(shè)的一個(gè)頭結(jié)點(diǎn)。
  • 頭結(jié)點(diǎn)的數(shù)據(jù)域一般不存儲(chǔ)任何信息寞钥，也可以存放一些關(guān)于線性表的長(zhǎng)度的附加信息慌申。
  • 頭結(jié)點(diǎn)的指針域存放指向第一個(gè)結(jié)點(diǎn)的指針(即第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置)。
  • 頭結(jié)點(diǎn)不一定是鏈表的必要元素理郑。

• 頭指針：

  • 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針蹄溉，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針您炉。
  • 頭指針具有標(biāo)識(shí)作用柒爵，所以常用頭指針冠以鏈表的名字(指針變量的名字)。
  • 無(wú)論鏈表是否為空赚爵，頭指針均不為空棉胀。

  • 頭指針是鏈表的必要元素。

    
    

單鏈表的代碼實(shí)現(xiàn)

#include <stdio.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define MAXSIZE 20  /* 定義線性表可能達(dá)到的最大長(zhǎng)度 */
typedef int  ElemType; /*  定義數(shù)據(jù)元素類型冀膝，類型名為ElemType唁奢，此處所定義的數(shù)據(jù)元素只包含一個(gè)int型的數(shù)據(jù)項(xiàng)*/
typedef struct { /* 定義順序表類型，類型名為SqList,包含兩個(gè)數(shù)據(jù)項(xiàng)：數(shù)組data,用于存放數(shù)據(jù)元素窝剖，整數(shù)length表示線性表當(dāng)前長(zhǎng)度*/
    
    ElemType data[MAXSIZE];   /*定義線性表占用的數(shù)組空間*/
    int length;         /*線性表當(dāng)前長(zhǎng)度*/
    
}SqList;

typedef int Status; /*Status是函數(shù)的類型麻掸，其值是函數(shù)結(jié)果狀態(tài)碼，如OK等*/

// 用結(jié)構(gòu)指針描述單鏈表
typedef struct Node{
    
    ElemType data;  // 數(shù)據(jù)域
    struct Node *Next; // 指針域
    
}Node;

// 取別名
typedef struct Node *LinkList;

通過(guò)這種鏈?zhǔn)酱鎯?chǔ)方式赐纱，若果p->data=ai,那么p->next->data=ai+1.

單鏈表的讀燃狗堋（工作指針后移）

• 獲取鏈表第i個(gè)數(shù)據(jù)的算法思路：
  1.聲明一個(gè)結(jié)點(diǎn)p指向鏈表的第一個(gè)結(jié)點(diǎn)熬北，初始化j從1開始；
  2.當(dāng)j<i時(shí)诚隙，就遍歷鏈表讶隐，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)最楷，j+1整份；
  3.若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在籽孙；
  4.否則查找成功烈评，返回結(jié)點(diǎn)p數(shù)據(jù)。
• 代碼：

/**
 * 獲取鏈表第`i`個(gè)數(shù)據(jù)的
 */
Status GetElem(LinkList L, int i, ElemType *e){
    
    int j;
    LinkList p;  // 聲明指針p
    
    p = L->next;  // p指向鏈表L的第一個(gè)結(jié)點(diǎn)
    j = 1;      // 當(dāng)前位置計(jì)數(shù)器設(shè)置為1
    
    while (p && j<i) {  // 當(dāng)p不為空 切j<i時(shí)候 j繼續(xù)向后找
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到達(dá)結(jié)尾且沒(méi)找到
    
    *e = p->data;  // 獲取倒找的結(jié)果
    
    return OK;
}

單鏈表的插入算法

• 算法思路：
  1.聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn)犯建，初始化j從1開始讲冠；
  2.當(dāng)j<1時(shí)，就遍歷鏈表适瓦，讓p的指針向后移動(dòng)竿开，不斷指向下一節(jié)點(diǎn)，j累加1玻熙；
  3.若到鏈表末尾p為空否彩，則說(shuō)明第i個(gè)元素不存在；
  4.否則查找成功嗦随，在系統(tǒng)中生成一個(gè)空節(jié)點(diǎn)s;
  5.將數(shù)據(jù)元素e賦值給s->data列荔；
  6.利用單鏈表插入語(yǔ)句插入:s->next = p->next; p->next = s;;
  7.返回成功。
• 代碼：

/**
 * 單鏈表的插入
 */
Status ListInsert(LinkList *L, int i, ElemType e){
    
    int j;
    LinkList p,s;
    
    p = *L;
    j = 1;
    
    while (p && j<i) {  // 用于尋找第i個(gè)結(jié)點(diǎn)
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到達(dá)結(jié)尾且沒(méi)找到
    
    s = (LinkList)malloc(sizeof(Node));  //生成一個(gè)空節(jié)點(diǎn)s
    
    // 插入語(yǔ)句
    s->next = p->next;
    p->next = s;
    
    return OK;
}

單鏈表的刪除算法(前繼結(jié)點(diǎn)的指針繞過(guò)繞過(guò)后繼結(jié)點(diǎn))

• 算法實(shí)現(xiàn)思路：p->next = p->next->next,即 q = p->next; p->next = q->next
  1.聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn)枚尼，初始化j從1開始贴浙；
  2.當(dāng)j<1時(shí)，就遍歷鏈表署恍，讓p的指針向后移動(dòng)崎溃，不斷指向下一節(jié)點(diǎn)，j累加1盯质；
  3.若到鏈表末尾p為空袁串，則說(shuō)明第i個(gè)元素不存在；
  4.否則查找成功呼巷，將欲刪除結(jié)點(diǎn)p->next賦值給q般婆；
  5.單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句：p->next = q->next;
  6.將結(jié)點(diǎn)中的數(shù)據(jù)賦值給e，作為返回朵逝；
  7.釋放q結(jié)點(diǎn)蔚袍。
• 代碼：

/**
 * 單鏈表的刪除
 */
Status ListDelete(LinkList *L, int i, ElemType e){
    
    int j;
    LinkList p,q;
    
    p = *L;
    j = 1;
    
    while (p && j<i) {  // 用于尋找第i個(gè)結(jié)點(diǎn)
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到達(dá)結(jié)尾且沒(méi)找到
    
    q = p->next;
    
    // 刪除語(yǔ)句
    p->next = q->next;
    free(q);
    
    return OK;
}

單鏈表的插入和刪除圖解

單鏈表的整表創(chuàng)建

對(duì)于順序存儲(chǔ)結(jié)構(gòu)的線性表的整表創(chuàng)建啤咽，可以用數(shù)組的初始化來(lái)直觀理解晋辆。
但是對(duì)于單鏈表，和順序存儲(chǔ)結(jié)構(gòu)就不一樣宇整，不像順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)這么幾種瓶佳，它的數(shù)據(jù)可以是分散在各個(gè)角落的，增長(zhǎng)也是動(dòng)態(tài)的鳞青。
對(duì)于每個(gè)鏈表來(lái)說(shuō)霸饲，它所占用空間的大小和位置是不需要預(yù)先分配劃定的，可以根據(jù)系統(tǒng)的情況和實(shí)際的需要及時(shí)生成臂拓。

單鏈表整表創(chuàng)建的算法思路：

1.聲明一個(gè)結(jié)點(diǎn)p和計(jì)數(shù)器變量i;
2.初始化一個(gè)空鏈表L厚脉；
3.讓L的頭結(jié)點(diǎn)的指針指向NULL,即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；
4.循環(huán)實(shí)現(xiàn)后繼結(jié)點(diǎn)的賦值和插入胶惰。

一傻工、頭插法建立單鏈表

頭插法從一個(gè)空表開始，生成新結(jié)點(diǎn)孵滞，讀取數(shù)據(jù)存放到新節(jié)點(diǎn)的數(shù)據(jù)域中中捆，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭，知道結(jié)束坊饶。

簡(jiǎn)單來(lái)說(shuō)泄伪，就是把新加進(jìn)的元素放在表頭的第一個(gè)位置(如同插隊(duì))：

• 先讓新節(jié)點(diǎn)的next指向頭結(jié)點(diǎn)之后；

• 讓后讓表頭的next指向新節(jié)點(diǎn)匿级。

• 代碼：

/**
 * 頭插法
 */
void CreatListHead(LinkList *L, int n){

    LinkList p;
    int i;
    
    srand(time(0));   // 初始化隨機(jī)數(shù)種子
    
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    for (i = 0; i < n; i++) {
        
        p = (LinkList)malloc(sizeof(Node)); // 生成新節(jié)點(diǎn)
        p ->data = rand()%100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;
        
    }
}

這里使用了c語(yǔ)言里面的生成隨機(jī)數(shù)的函數(shù)rand()來(lái)構(gòu)造結(jié)點(diǎn)里面的數(shù)據(jù)蟋滴。

二、尾插法建立單鏈表

頭插法建立鏈表隨讓算法簡(jiǎn)單根蟹，但是生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。
若把新結(jié)點(diǎn)都插入到最后糟秘，那么這種算法就是尾插法简逮。

• 代碼：

/**
 * 尾插法
 */
void CreatListTail(LinkList *L, int n){
    
    LinkList p, r;
    int i;
    
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    
    for (i = 0; i < n; i++) {
        
        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }
    
    r->next = NULL;
}

尾插法圖解

單鏈表的整表刪除

• 單鏈表的整表刪除的算法思路：
  1.聲明結(jié)點(diǎn)p和q;
  2.將第一個(gè)結(jié)點(diǎn)賦值給p，下一結(jié)點(diǎn)賦值給q尿赚；
  3.循環(huán)執(zhí)行釋放p和將q賦值給p的操作散庶。
• 代碼：

Status ClearList(LinkList *L){

    LinkList p,q;
    
    p = (*L)->next;
    
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    
    (*L)->next = NULL;
    
    return OK;
}

注意：整表刪除的時(shí)候，需要一個(gè)個(gè)結(jié)點(diǎn)的刪除凌净。

單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)對(duì)比

存儲(chǔ)分配方式：

• 順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素悲龟；
• 單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的儲(chǔ)存單元存放線性表的元素冰寻；

時(shí)間性能：

• 查找：
  • 順醋存儲(chǔ)結(jié)構(gòu)O(1);
  • 單鏈表O(n);
• 插入和刪除：
  • 順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一般的元素须教，時(shí)間為O(n)；
  • 單鏈表在計(jì)算機(jī)處某位置的指針后，插入和刪除時(shí)間為O(1);

空間性能

• 順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間轻腺，分大了乐疆，容易造成空間浪費(fèi)，分小了贬养，容易發(fā)生溢出挤土。
• 單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配误算，元素個(gè)數(shù)也不受限制仰美。