1、线性表的链式存储结构
每个元素多用一个位置来存放指向下一个元素位置的指针，依次类推，可以找到所有的元素。链式存储中，除了要存储数据本身外，还要存储它的后继元素的存储地址（指针）。
数据域：存储数据信息的域；
指针域：存储直接后继位置的域。
这两部分信息组成数据元素称之为存储映像，节点Node。链表中每个结点中只包含一个指针域，为单链表。链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空。
2、头节点和头指针（头节点不是必须的）
头指针：
1）头指针是指链表指向第一个结点的指针，若链表有头节点，则是指向头结点的指针。 2）头指针具有标识作用，常用头指针冠以链表的名字（指针变量的名字）。 3）无论链表是否为空，头指针均不为空。 4）头指针是链表的必要元素。
头节点：
1）放在第一个元素的结点之前，其数据域一般无意义（可以用来存放链表长度） 2）为了操作的统一方便设立（在第一元素结点前插入和删除第一结点与其他结点操作统一） 3）头节点不一定是链表的必要元素。
3、带头结点的单链表实现
C语言中可以用结构指针来描述单链表：
typedef int ElemType; typedef struct Node { ElemType data; //数据域 struct Node* Next;//指针域 }Node, *LinkList; //结点由存放数据的数据域和存放后继结点地址的指针域组成
单链表的插入：
//单链表的插入 STATUS ListInsert(LinkList* L, int i, ElemType e)//L是指向头节点的二级指针 { if ((L == NULL) || (i > (*L)->data + 1)) { return 0; } int j=1; LinkList p = *L; while (p && (j < i))//找到要插入的位置 { p = p->Next; j++; } LinkList n = (LinkList)malloc(sizeof(Node)); n->data = e; n->Next = p->Next; p->Next = n; (*L)->data++; //头节点的数据域，表示当前链表的长度 return 1; }
单链表的删除
//单链表的删除 STATUS ListDelete(LinkList* L, int i, ElemType* e) { if (L == NULL || i > (*L)->data + 1) return 0; int j = 1; LinkList p = (*L); while (p&&j<i) { p = p->Next; j++; } LinkList q = p->Next; //要删除的结点 *e = q->data; p->Next = q->Next; free(q); (*L)->data--; return 1; }
//四个基本操作，初始，清空，判断是否为空，获取长度 //初始化带有头结点的链表 Status InitList(LinkList* L) { *L = (LinkList)malloc(sizeof(Node)); //使头指针指向头结点 if (*L == NULL) //内存分配失败 return ERROR; (*L)->next = NULL; //指针域为空 (*L)->data = 0; //头结点数据域用来存放链表长度 return OK; } //清空链表（不会清除头结点） Status ClearList(LinkList* L) { LinkList q, p; q = (*L)->next; //是q指向第一个结点 while (q) { p = q; q = q->next; free(p); } (*L)->next = NULL; return OK; } //判断链表是否为空 Status ListEmpty(LinkList L) { if (L->next) return FALSE; return TRUE; } //获取列表长度 int ListLength(LinkList L) { /* int length=0; LinkList q=L; while (q=q->next) length++; return length; */ return L->data; }
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef int STATUS; typedef struct Node { ElemType data; //数据域 struct Node* Next;//指针域 }Node, *LinkList; //结点由存放数据的数据域和存放后继结点地址的指针域组成 //单链表的插入 STATUS ListInsert(LinkList* L, int i, ElemType e)//L是指向头节点的二级指针 { if ((L == NULL) || (i > (*L)->data + 1)) { return 0; } int j=1; LinkList p = *L; while (p && (j < i))//找到要插入的位置 { p = p->Next; j++; } LinkList n = (LinkList)malloc(sizeof(Node)); n->data = e; n->Next = p->Next; p->Next = n; (*L)->data++; //头节点的数据域，表示当前链表的长度 return 1; } //单链表的删除 STATUS ListDelete(LinkList* L, int i, ElemType* e) { if (L == NULL || i > (*L)->data + 1) return 0; int j = 1; LinkList p = (*L); while (p&&j<i) { p = p->Next; j++; } LinkList q = p->Next; //要删除的结点 *e = q->data; p->Next = q->Next; free(q); (*L)->data--; return 1; } int main() { LinkList L=(LinkList)malloc(sizeof(Node)); L->Next = NULL; L->data = 0; for (int i = 1; i <= 10; i++) { ListInsert(&L, i, i * i); } LinkList p = L->Next; while (p) { printf_s("%d ", p->data); p = p->Next; } printf_s(" "); int j,e; printf_s("请输入要删除第几个结点 "); scanf_s("%d",&j); ListDelete(&L, j, &e); printf_s("删除的结点为：%d ", e); printf_s("删除后的链表为： "); p = L->Next; while (p) { printf_s("%d ", p->data); p = p->Next; } return 1; }
对于插入或删除数据越频繁的操作，单链表的效率优势越明显。
4、创建链表
头插法：从一个空表开始，生成新节点，读取的数据放到新节点的数据域中，然后将新节点插入到当前链表的表头上。也就是说，把新加的元素放在表头后的第一个位置。
void CreatListHead(LinkList* L, int n) { LinkList p; int i; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); (*L)->Next = NULL; for (i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand() % 10 + 1; p->Next = (*L)->Next; (*L)->Next = p;
(*L)->data++; } }
尾插法：把新节点插入链表的最后，需要增加一个指向链表最后一个尾节点的指针r。
void CreatListEnd(LinkList* L, int n) { LinkList p, r; //创建头结点 *L = (LinkList)malloc(sizeof(Node)); (*L)->data = 0; (*L)->Next = NULL; p = *L; srand(time(0)); for (int i = 0; i < n; i++) { r = (LinkList)malloc(sizeof(Node)); r->data = rand() % 10 + 1; r->Next = p->Next; p->Next = r; p = r; //p指向最后一个结点 (*L)->data++; } }
5、单链表结构与顺序存储结构的优缺点：
1)若线性表需要频繁查找，很少进行插入和删除操作，采用顺序存储结构合适。 例如用户注册信息，绝大多数都是读取数据。
2)若需要频繁的插入和删除，采用单链表合适。
| 优缺点 | 顺序存储结构 | 单链表 |
| 存储分配方式： | 一段连续的存储单元依次存储线性表的数据元素 | 链式存储，用一组任意的存储单元存放线性表的元素 |
| 时间性能： | 查找O(1)，插入和删除O(n) | 查找O(n)，插入和删除O(1) |
| 空间性能： | 需要预先分配存储空间，较大浪费，较小溢出 | 利用零碎空间 |