单链表：是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。（每个结点 只有一个链域的链表称为单链表）
1）链表中的数据是以结点来表示
2）每个结点的构成：元素(数据元素的映象（Node->data）) + 指针(指示后继元素存储位置（Node->next）)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
3）链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：
1）用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
2）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）。
链表的结构：
data域-->存放结点值的数据域
next域-->存放 存放结点的直接后继的指针域
二、 单链表的多种操作
代码实现：
头文件：list.h
#pragma once //带头节点的单链表,以NULL结尾 typedef struct Node { int data; struct Node*next; }Node,*List;//List == Node* //初始化 void InitList(List plist); //头插，违背生活规律，尽量少用 bool Insert_head(List plist,int val); //尾插 bool Insert_tail(List plist,int val); //查找 Node* Search(List plist,int key); bool Delete(List plist,int key); int GetLength(List plist); bool IsEmpty(List plist); //清空数据 void Clear(List plist); //销毁链表 void Destroy(List plist); void Show(List plist);功能实现：.cpp文件；
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include "list.h" #include <vld.h> //初始化 void InitList(List plist) { assert(plist != NULL); if(plist==NULL) { return ; } plist->next = NULL; } //头插 bool Insert_head(List plist,int val) { Node *p = (Node *)malloc(sizeof(Node)); p->data = val; p->next = plist->next; plist->next = p; return true; } //尾插 bool Insert_tail(List plist,int val) { Node *q; for(q=plist;q->next!=NULL;q=q->next);//尾节点q标记为q->next==NULL Node *p = (Node *)malloc(sizeof(Node)); p->data = val; p->next = q->next;//p->next = NULL;//将p插在q的后面 q->next = p; return true; } //查找 Node* Search(List plist,int key) { for (Node *p = plist->next;p != NULL;p = p->next) { if (p->data == key) { return p; } } return NULL; } //查找前驱 Node* Precunrsor_Search(List plist,int key) { for (Node *p = plist;p != NULL;p = p->next) { if (p->next->data == key) { return p; } } return NULL; } bool Delete(List plist,int key) { Node *p = Precunrsor_Search(plist,key);//前驱 if (p == NULL) { return false; } plist = p; p = plist->next; plist->next = plist->next->next; free(p);//注意：由于这里是删除结点，所以要回收内存，free(所选删除的结点)，防止内存泄漏。 p = NULL;//置空以防止出现ye return true; } int GetLength(List plist) { int count = 0; for (Node *p = plist->next;p != NULL; p = p->next) { count++; } return count; } bool IsEmpty(List plist) { return plist->next == NULL; } //清空数据 void Clear(List plist) { Destroy(plist); } //销毁链表 void Destroy(List plist) { Node *p; while (plist->next != NULL) { p = plist->next; plist->next = p->next; free(p); p=NULL; } } //打印函数 void Show(List plist) { for(Node *p=plist->next;p!=NULL;p=p->next) { printf("%d ",p->data); } printf("\n"); } 对单链表实现就地逆置(笔试、面试重点) void Reverse(List plist) { if (plist == NULL || plist->next == NULL || plist->next->next == NULL) { return ; } Node *p = plist->next; plist ->next = NULL; Node *q; while (p != NULL) { q = p->next; p->next = plist->next; plist->next = p; p = q; } } 结束语：相比于无头链表，单链表中，增加一个头结点的目的是为了(方便运算的实现)，类似于《算法导论》中 讲到的：是作为哨兵的作用，可以使代码简洁方便。而无头链表，没有头结点，则首元素没有前驱结点，在其前插入结点或者删除结点会复杂考虑的多一点。