链表是一种常见的数据结构。它主要是利用动态内存分配、结合结构体并配合指针来实现的，能根据需要开辟和释放内存单元。由于链表是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，且链表的长度不是固定的，因此可以非常方便地实现“数据元素”的插入和删除操作。

目录

1. 单链表的建立

2. 单链表的创建

3. 单链表的输出

4. 单链表的销毁

5. 单链表结点的基本操作

5.1 单链表结点的插入

 5.2 单链表结点的删除

---

1. 单链表的建立

        单链表是由若干数据元素按一定原则连接起来。原则是，前一个结点指向下一个结点，只能通过前一个节点才能找到下一个节点。链表一般有一个头指针变量，它存放一个地址，该地址是链表的第一个元素地址。

         单链表中每一个“结点”都由两部分组成：

（1）用户存储的实际的数据（数据域（data））；

（2）下一个结点的地址（指针域（next））；

       单链表的结点结构一般声明如下形式：

typedef struct LinkNode
{int data;                //数据域：存储结点数据信息，数据可以是任何类型struct LinkNode *next;   //指针域：存储直接后继结点的地址
}LinkNode,*LinkList;

 只包含一个指针域、由多个结点链接形成的链表，称为单链表或线性链表。

以学生信息为例，一个链表的存储结构：

 根据存储结构，定义学生信息的结点类型：

typedef struct StuNode       /*  StuNode为自定义  */
{int snum;                //数据域 学号char sname[20];          //数据域 姓名float score;             //数据域 成绩struct Student *next;    //指针域
}StuNode,*StuPtr;            /*  StuPtr为自定义  */

根据单链表定义和学生成绩信息的结点类型，单链表类型可定义如下：

class StuListLink
{public:StuPtr head;StuPtr tail;int count;private:StuListLink(){};				//构造函数 void CreateStuList();           //创建单链表，不带头结点void CreateStuList(int h);		//创建单链表，带头结点 void PrintStuList();			//输出单链表 void InsertStu();				//插入单链表结点 void DeleteStu();				//删除单链表结点 void DestroyStuList();			//销毁单链表 
};
/*  以上并未实际分配存储空间  */

2. 单链表的创建

        链表的建立过程中，需要一个一个地开辟结点和输入各结点的数据，并建立起结点之间的链接的关系。

(1)若为空表，将新建结点p置为单链表的第一个结点，即令p=head->next;NULL=p->next;

(2)若为非空表，则将新建结点添加到表尾。

不带头结点

图和程序

void StuListLink::CreateStuList()
{StuPtr p;int i;cout<<"请输入学生数量："<<endl;cin>>count;if(count<0){head=0;cout<<"错误，学生总数不应该小于0.\n"<<endl;return;} head = NULL;for(i=0;i<count;i++){p=new Student;cout<<"请输入学生学号 姓名 成绩："<<endl;cin>>p->snum>>p->sname>>p->score;p->next = NULL;if(head==NULL)			//空表，接入表头 {head=p;}else					//非空表，接到表尾 {tail->next=p;		//指针域：将tail的下一个结点由NULL换成了p }tail=p;					//数据域：将p的数据给了tail；p成为新的表尾 }cout<<"链表创建成功,共有"<<count<<"名学生信息"<<endl; 
} 

带头结点

图和程序

void StuListLink::CreateStuList()
{StuPtr p;int i;cout<<"请输入学生数量："<<endl;cin>>count;if(count<0){cout<<"错误，学生总数不应该小于0.\n"<<endl;return;} head = new Student;head->snum=0;head->sname='\0';head->score=0;head->next=NULL;tail=head;for(i=0;i<count;i++){p=new Student;cout<<"请输入学生学号 姓名 成绩："<<endl;cin>>p->snum>>p->sname>>p->score;p->next = NULL;tail->next=p;		    //指针域：将tail的下一个结点由NULL换成了p tail=p;					//数据域：将p的数据给了tail；p成为新的表尾 }cout<<"链表创建成功,共有"<<count<<"名学生信息"<<endl; 
} 

3. 单链表的输出

单链表的输出就是利用指向单链表的指针依次将链表中各结点的数据输出。

利用指针变量p从头到尾依次指向链表中的每个结点，当指针指向某个结点时，就输出该结点数据域中的内容直到遇到链表结束标志NULL为止。如果是空链表，就只输出有关提示信息并返回调用函数。

程序如下：

void StuListLink::PrintStuList()
{StuPtr p;p=head->next;if(p==NULL){cout<<"学生链表为空!"<<endl;return; }while(p!=NULL){cout<<"学生信息：学号"<<p->snum<<", 姓名"<<p->sname<<", 成绩"<<p->score<<";"<<endl; p=p->next;}
} 

4. 单链表的销毁

        在C++中我们创建链表要用new分配内存空间，同样在销毁单链表时我们需要释放内存，此时我们就要借助delete进行内存释放。

void StuListLink::DestroyStuList()
{StuPtr p,ptr;p=head;while(p!=NULL){ptr=p; p=p->next;delete[ptr];}head=NULL;cout<<"学生链表已销毁."<<endl;
} 

5. 单链表结点的基本操作

5.1 单链表结点的插入

（1）若链表为空，新结点应插在表尾，即插在头结点之后，作为表的第一个结点。

（2）若链表不为空，在链表中间插入新结点，应将新结点的指针域指向插入点的下一个结点(p->next=pre->next),且让插入点的指针域指向新结点（pre->next=p）。

（3）若在表尾插入新结点，则末结点指针域指向新结点（pre->next）。

void StuListLink::InsertStu() 
{StuPtr p,pre;StuPtr pNode;int sno;cout<<"请输入要在哪个学号之后插入学生信息："<<endl;cin>>sno;pNode= new Student;cout<<"请输入要插入的学生的学号 姓名 成绩:"<<endl;cin>>pNode->snum>>pNode->sname>>pNode->score;p=head->next;pre=head;while(p!=NULL){pre=p;if(p->snum==sno)		//指定学号跳出循环。 {break;}p=p->next;}pNode->next=pre->next;pre->next=pNode
} 

 5.2 单链表结点的删除

单链表结点的删除就是将待删除结点的上一个结点直接指向待删除结点的下一个结点，再将删除的结点释放即可。

void StuListLink::DeleteStu() 
{StuPtr p,pre;int sno;cout<<"请输入要删除的学号："<<endl;cin>>sno;pre=head,p=head->next; while(p!=NULL){if(p->snum==sno)		{pre->next=p->next;delete[p];p=NULL;cout<<"删除成功!";return;}pre=p;p=p->next;}cout<<"未找到该学号，删除失败!"<<endl;
} 

以上就是单链表的全部内容了，欢迎各位补充，如有错误还请指正。

（所有程序仅供理解）