单链表

定义

单链表：用链式存储的方式实现线性表

链式存储：用一组任意的存储单元存储线性表的数据元素，不要求逻辑上相邻的元素在物理位置上也相邻

单链表的优缺点

• 优点：不要求大片连续的空间，该容量方便
• 缺点：不可随机存取，要耗费一定的空间存放指针（每个结点除了存放数据元素外，还要存储指向下一个结点的指针）

用代码定义单链表

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

用typedef对上面的代码进行简化

typedef <数据类型> <别名>

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

要表示一个单链表时，只需声明一个头指针 L ，指向单链表的第一个结点

LNode * L;	//声明一个指向单链表第一个结点的指针，强调这是一个结点LinkList L;	//声明一个指向单链表第一个结点的指针，强调这是一个单链表

初始化单链表

InitList(&L)：初始化表，构造一个空的线性表L，分配内存空间

不带头结点的单链表

typedef struct LNode {			// 定义单链表结点类型ElemType data;              // 每个结点存放一个数据元素struct LNode *next;         // 指针指向下一个结点
} LNode, *LinkList;bool InitList(LinkList &L) {L = NULL;                  //空表，暂时还没有任何结点，防止出现脏数据return true;
}void test(){LinkList L;		// 声明一个指向单链表的指针，这里的L是结构体指针// 注意此处并没有创建一个结点    InitList(L);	//初始化一个空表//......后续代码....
}

带头结点的单链表

typedef struct LNode {          // 定义单链表结点类型ElemType data;              // 每个结点存放一个数据元素struct LNode *next;         // 指针指向下一个结点
} LNode, *LinkList;// 初始化一个单链表(带头结点)
bool InitList(LinkList &L){L = (LNode*) malloc(sizeof(LNode));	//分配头结点if (L == NULL) {			//内存不足，分配失败return false;}L->next = NULL;				//头结点后暂时没有存放数据return true;
}void test(){LinkList L;		//声明一个指向单链表的指针，这里的L是结构体指针//注意此处并没有创建一个结点InitList(L);	// 初始化一个空表//......后续代码....
}

不带头结点，写代码更麻烦，需要对第一个数据结点和后续数据结点的处理，需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑
带头结点，一套代码完成，实现更方便

单链表的插入

ListInsert(&L,i,e)：插入操作，在表L中的第 i 个位置上插入指定元素 e

按位序插入（带头结点）

思路

1. 在表 L 中的第 i 个位置上插入指定元素 e，那么首先要找到第 i-1 个结点，将新节点插入其后，如果是插入到第 1 个位置，那么头节点可以视为第 0 个结点
2. 新结点后继为所寻结点的后继，新结点成为所寻结点的后继

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

bool ListInsert(LinkList &L, int i, ElemType e)
{if (i < 1) {return false;}LNode *p;   // 结构体指针p, 指向当前扫描到的结点int j = 0;  // 当前p指向的是第j个结点p = L;      // L 指向头结点，头结点是第0个结点(不存数据)// 循环找到第 i - 1 个结点// 非空表示不能到链表尽头了，j < i - 1，表示要找到第 i - 1 个节点就停下来了while (p != NULL && j < i - 1) {      p = p->next;j++;}// 到这里 p 指向了第 i - 1 个节点// 校验发现第 i - 1个节点是空的，这就表示原链表只有 i - 2 个节点，第 i - 2 个节点的后继是空指针。if (p == NULL) {            return false;}LNode *s = (LNode *)malloc(sizeof(LNode));// malloc 返回值必须校验if (s == NULL) {return false;}s->data = e;s->next = p->next; p->next = s;    // 将结点s连到p之后//注意上面两句代码的执行顺序不能颠倒return true;    // 插入成功
}

时间复杂度分析

• 最好情况：新元素插入到表头；最好时间复杂度 = $O(1)$
• 最坏情况：新元素插入到表尾；最坏时间复杂度 = $O(n)$
• 平均情况：新元素插入到任何一个位置的概率相同； 平均时间复杂度 = $O(n)$

指定结点的后插操作

// 在 p 结点后插入元素 e
bool InsertNextNode(LNode* p, ElemType e)
{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;
}

时间复杂度：$O(1)$

指定结点的前插操作

方法1：常规算法

bool InsertPriorNode(Linklist L, LNode *p, ElemType e)
{if (p == NULL) {return false;}LNode * pre = L;   // 前驱结点// 遍历循环查找while (pre != NULL) {if (pre->next == p) {break;}pre = pre->next;}// 如果找不到，那就是空值if (pre == NULL) {return false;}// 直接调用指定结点后插元素，在p的前一个结点插入，即是在p的前驱结点的后一个插入return InsertNextNode(pre, e);
}

时间复杂度：$O(n)$

方法2：交换节点算法

思路：直接对指定节点进行后插操作，交换新节点与指定节点的数据域

bool InsertPriorNode(LNode *p, ElemType e)
{if (p == NULL) {return false;}LNode *s = (LNode*)malloc(sizeof(LNode));// 判定内存是否申请成功if (s == NULL) {return false;}// 解链，重新成链s->next = p->next;p->next = s;// 数据交换swaps->data = p->data;p->data = e;return true;
}

时间复杂度：$O(1)$

单链表的删除

ListDelete(&L,i,&e)：删除操作，删除表L中第 i 个位置的元素，并用 e 返回删除元素的值

按位序删除（带头节点）

思路：头结点可以看作“第0个”结点，遍历找到第 i-1 个结点，将其指针指向第 i+1 个结点，并释放第 i 个结点

bool ListDelete(Linklist &L, int i, ElemType &e)
{if (i < 1) {return false;}LNode *p;   // 结构体指针p, 指向当前扫描到的结点int j = 0;  // 当前 p 指向的是第 j 个结点p = L;      // L 指向头结点，头结点是第0个结点(不存数据)// 循环找到第 i-1 个结点while (p != NULL && j < i - 1) {      p = p->next;j++;}if (p == NULL) {return false;   // i值不合法}       // 第i-1个结点后没有其他结点，不存在第i个结点if (p -> next == NULL) {return false;   }// 到这里的代码都和指定位序插入结点相同LNode *q = p->next;       // 令q指向被删除结点，即临时变量e = q->data;              // 用e把返回值带回来p->next = q->next;        // 将*q结点从链中断开free(q);                  // 释放结点的存储空间return true;              // 删除成功
}

时间复杂度：$O(n)$

删除指定结点

类似指定结点的插入操作的方法

单链表的查找

按位查找

GetElem(L,i)：按位查找操作，获取表L中第 i 个位置的元素的值

//按位查找，返回第 i 个元素（带头结点）
LNode * GetElem(LinkList L, int i){if(i < 0){return NULL;}LNode *p;   // 结构体指针p, 指向当前扫描到的结点int j = 0;  // 当前 p 指向的是第 j 个结点p = L;      // L 指向头结点，头结点是第0个结点(不存数据)while(p != NULL && j < i){p = p->next;j++;}return p;
}

平均时间复杂度：$O(n)$

按值查找

LocateElem(L,e)：按值查找操作，在表L中查找具有给定关键字值的元素

LNode * LocateElem(LinkList L,ElemType e){LNode *p = L->next;    //从第 1 个结点开始查找数据域为 e 的结点while(p != NULL && p->data != e){p = p->next;}return p;
}

平均时间复杂度：$O(n)$

求单链表的长度

Length(L)：求表长，返回线性表L的长度，即L中数据元素的个数

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

平均时间复杂度：$O(n)$

单链表的建立

基于带头结点的单链表讨论

• Step 1：初始化一个单链表

  typedef struct LNode {          // 定义单链表结点类型ElemType data;              // 每个结点存放一个数据元素struct LNode *next;         // 指针指向下一个结点
  } LNode, *LinkList;// 初始化一个单链表(带头结点)
  bool InitList(LinkList &L){L = (LNode*) malloc(sizeof(LNode));	//分配头结点if (L == NULL) {			//内存不足，分配失败return false;}L->next = NULL;				//头结点后暂时没有存放数据return true;
  }void test(){LinkList L;		//声明一个指向单链表的指针，这里的L是结构体指针//注意此处并没有创建一个结点InitList(L);	// 初始化一个空表//......后续代码....
  }
  

• Step 2：每次取一个数据元素，插入到表尾/表头

尾插法

思路

初始化单链表
设置变量 length 记录链表长度
while 循环 {每次取一个元素 e;ListInsert(L, length + 1, e) 插到尾部;length++;
}

常规做法

每次取新结点，都从头结点开始遍历到尾部，然后将结点插入到尾部

bool ListInsert(LinkList &L, int i, ElemType e)
{if (i < 1) {return false;}    LNode *p;int j = 0;p = L;// 循环找到第 i-1 个结点while (p != NULL && j < i - 1) {p = p->next;j++;}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;         // 把结点s连到p之后return true;
}

时间复杂度：$O(n^2)$

优化算法

将链表值依次输入，并使用一个临时指针变量记录尾部结点

LinkList List_TailInsert(LinkList &L)
{   // 正向建立单链表int x;                                // ElemType -> 整型L = (LinkList)malloc(sizeof(LNode));  // 头结点if (L == NULL) {return NULL;}LNode *s, *r = L;                      // r为表尾指针while(scanf("%d", &x) != EOF){s = (LNode*)malloc(sizeof(LNode));if (s == NULL) {// ... 清理内存代码...return NULL;}s->data = x;r->next = s;r = s;}r->next = NULL;return L;
}

时间复杂度：$O(n)$

头插法

思路

初始化单链表
while (没有取完) {每次取一个数据元素e;ListInsertNode(L,e);
}

LinkList List_HeadInsert(LinkList &L)
{LNode *s;int x;L = (Linklist)malloc(sizeof(LNode));    // 创建头结点if (L == NULL) {return NULL;}L->next = NULL;			//初始为空链表，清除脏数据while (scanf("%d",&x) != EOF) {s = (LNode*)malloc(sizeof(LNode));if (s == NULL) {// ... 清理内存代码...return NULL;}s->data = x;s->next = L->next;L->next = s;}return L;
}

参考文章
【DS 数据结构】003 | 单链表