单向链表
首先先谈一下链表和顺序表的区别吧，方便知道两者的本质。
顺序表的底层数据结构还是眉清目秀的数组。为什么称它是眉清目秀呢，因为它有天然优势，它有索引（数组下标），所以对它做增删改查等操作就很方便，可以通过直接遍历下标查找，也可以通过调用下标输出对应的值。
但链表没有这么美妙的功能。那它必然有自己的优势，那就是它可以充分利用内存，而顺序表不能。
为什么呢，这要先回到顺序表的底层数据结构数组。数组有了索引的优势，自然也有了束缚，它必须有顺序，元素和元素之间是连续的关系，所以在内存空间存储时也是连续的。也就是说如果我创建了一个110大小的数组（int a[110];），那么系统就要帮我在内存空间里找一个连续的110这么大的空间用来存我之后的值，这要求未免太苛刻了，毕竟多数时候会有110个空间剩余，但它们并不是连续的呀，这不就不能用了吗，浪费了内存，也没实现想法。
能支持链表利用不连续空间存储内容的本质就是指针。它充当数组中索引的角色。
那参考数组，除了有下标还应该有什么呢？当然是存的值。所以对于链表还应该有存值的空间。
链表的基本单位叫节点，节点里有两部分，存值的地方和存下一个连谁（下一个节点的地址）。因为节点既存值又存地址，所以数据类型较多且互相有封装关系，创建节点构成就用struct了。
代码如下
template
struct Node
{ T data;//存值
Node*next;//存下一个节点的地址
}
★下图为一个链表的基本构成
头节点first相当于一个班的班旗，当系统看见它时就知道，啊，这有个链表。如果它顺着first的指向走下去就能依次看见这个链表的每个节点。
头结点很重要，如果没它，即使内存里已经存了很多节点，系统也不知道从哪开始走，那它就默认没有这个链表，这可不行！我辛辛苦苦写的链表啊！你却视而不见
所以头结点必须写，非必要不改动，不移动。
谈谈链表怎么实现数组的索引功能吧，毕竟之后的很多操作都是基于可以遍历实现的。链表的节点里有一个部分是用来存下一个节点的地址，这样系统才知道下一个地方怎么去。
那就需要一个指针能移动，然后根据节点存的下个地址继续移动。如果想访问值和地址就可以用struct的语法访问了。
我们把这个负责移动的指针称为工作指针。
Node*p=first;//p初始指向头节点
Node*p=first->next;//p初始指向第一个节点
（头结点里啥也没有，是因为算法原因存在的，现在不需要理解，它的本质是用空间换时间。）
（第一个节点指的是像数组的第一个元素，既存值又存下一个地址）
那么工作指针怎么移动呢？
★如下图
链表的遍历
知道了工作指针怎么移动，那就来谈谈链表怎么遍历吧。
链表是不知道有多少个节点的，一般都是动态加。加上它还不连续，那for循环直接pass掉了。那while循环就适合这种情况，那使用while循环就需要跳出循环的条件，那写什么呢？
这个时候就看看尾结点吧，看到它就意味着链表遍历之旅结束啦。如果这个时候你还想向下个景点访问“风景”，你就没有地图啦，不要贪得无厌！
利用这个特点
代码
while(p!=NULL)
{p=p->next;
cout<
}
这样遍历的代码我们就会写啦。注意，NULL也是新建的但不马上用的指针的初始化哦。
比如：int *s=NULL;
好啦，我们的最初的问题解决啦，那让我们接下来就注重了解链表吧。学会怎么写它的基本代码！
构造函数
类都有构造函数，毕竟要创建对象嘛。链表的构造函数一般是无参构造，主要是用来先创建头结点用的。基本意思就是先创建一个空链表。让它满足链表的基本构成，有头有尾的。
template
linkList
{
first=new Node
first->next=NULL;
}
析构函数
链表里对它还真是必须手动写。为了释放掉first指针，毕竟是程序员自己申请的嘛。释放掉first系统就找不到链表了，基本上类似于清空了链表。
插入函数
因为要插入一个新的节点，所以肯定首先应该给这个新节点在堆区开辟一个空间，所以就是
Node*s=new Node;如果你想一次性插入多个节点，那就要用到循环，此时可以把开辟空间的步骤放在循环里，实现开辟多个新节点。（Node*s=NULL;）(s=new Node;这个放在循环里）。
如果想插入一个新节点，那就要告诉它插在哪，值是什么。
那链表怎么处理索引，它是用num替代。num和工作指针同频，一起走。推荐让num初始值为0。
用户输入的插入位置是限制num的，而num和工作指针同频，所以也间接限制了工作指针的指向。本质就是这么个思想。
假如我想在i这个位置插入新节点，那num的限制范围是什么呢？
num 因为新节点想插入那就需要连后继节点，连前驱节点（连前驱节点的时候就已经断了原先两个节点的连接）。新插入的节点是有指针指示的，即我们上面写的那个S。那表示后驱节点就是s->next。但如果工作节点p此时指向s，那么就无法表示前驱节点了。 所以应该找到目标插入位置的前一个节点，即目标位置的前驱节点，用它表示前驱节点。 嗯，就是这么个思想。 放代码啦 template void linkList {int num=0; Node Node s=new Node while(p!=NULL&&num { p=p->next; num++; } if(p==NULL)throw"插入位置异常"; else { s->next=p->next; s->data=x; p->next=s; } } 是的，还有边界分析。 什么时候边界分析？ 当函数参数有用户输入的索引值时。毕竟用户不是写程序的人，很容易输入非法索引嘛。 上面的基本思想可以处理get函数（给址查值），删除，遍历，Locate函数（给值查址），返回长度Length函数。 不过Length函数中注意num应该等于0，p=first->next;为什么此时不同步了呢？因为到最后的时候p被限制了，两者都停止进程，但是此时的p不会访问，但是要输出此时num作为链表长度的输出，那num就多了1。所以num和p此情况下应该错一位。 ★总结 本文可以帮助写完基础函数 1.遍历函数 2.按址查值 3.按值查址 4.返回链表长度 5.删除链表节点 6.插入新节点
