单链表的概念
单链表是一种链式存取的数据结构，链表中的数据是以结点来表示的。
每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)。
元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
以“结点的序列”表示的线性表称作线性链表（单链表），单链表是链式存取的结构。
复习一下之前学过的顺序表：
顺序表的缺陷
1.当空间不够时需要增容，而增容需要付出代价，浪费一些空间。
2.为了避免频繁增容，一般地，增容时都增至原本容量的2倍；这样就会可能存在一部分空间没有被使用的情况。
3.顺序表的数据是从开始的位置连续存储的，当需要从头部或者中间插入或删除数据时，就需要挪动数据，效率不高。
顺序表的优势
1.支持随机访问。
（有些算法需要结构支持随机访问，比如：二分查找、优化的快速排序等等）
而链表呢
链表的优势.1.按需申请空间，不用了就释放空间（更合理地使用空间）。 2.在头部或中间插入或删除数据时，不需要挪动数据，效率较高。
链表的缺陷
1.每一个数据，都要存一个指针去链接后面的数据结点。
2.不支持随机访问。
单链表的结构
逻辑结构
想象出来的、便于理解的
物理结构
内存中实际如何存储的
代码呈现
//单链表的基本结构 #define SLTDataType int typedef struct SListNode { SLTDataType data; struct SListNode * next; }SLTNode;
单链表的打印
//单链表的打印 void SListPrint(SLTNode* phead) { //创建一个临时结点，将phead赋给cur SLTNode* cur = phead; //判断cur是否等于空 while(cur != NULL) { //打印链表数据 printf("%d->",cur->data); //找下一块的数据，就要找下一个结点 //而下一个结点存放于cur中，通过cur找到下一个结点 //一直循环，直到next指针指向NULL时，链表打印完成 cur = cur->next; } }
单链表的尾插函数
要实现单链表尾插，首先判断传入的链表是否为空，如果为空，则直接给其赋值。
如果不为空，则需要找到最后一个结点，即尾结点。尾结点的特征是：next指针指向NULL。
通过这一特征找到尾结点，再将新结点赋给尾结点。同时新结点的next指针指向NULL。
//单链表尾插函数 void SListPushBack(SLTNode ** pphead,SLTDataType x) { //创建一个新结点 SLTNode * newnode = (SLTNode *)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; //当传入的链表为空时，要先给其赋值，才能进行后面的操作 //二级指针pphead存储着一级指针变量phead的地址，解引用一次得到phead的地址 if(*pphead == NULL) { *pphead = newnode; //将新结点赋给头结点 } else { //要进行尾插，就要先找到尾结点 //尾结点的特征：next指针为空指针 //建立一个新结点，命名为尾结点 SLTNode * tail = *pphead; while(tail->next != NULL)//遍历找到尾结点 { tail = tail->next; } tail->next = newnode; } }
