单链表

单链表

单链表是一个储存数据的表，那么顾名思义，单链表的存储方式应该就是想一条链子一样将所有的数据连接起来。

储存方式：

顺序存储： 顺序存储就是通过数组来实现。在单链表中相邻的数据之间一定有一个先后的顺序，那么就可以依靠这个先后顺序，将数据依次存储在数组中。 可定义一个结构体

struct Node
{
int data;
int parent;
}

通过建立Node数组，可以将相邻数据之间的关系存储下来。 优点： 建表更加简单易懂，操作简单 缺点： 使用之前必须确定数据的大小，否则可能会出现数组越界或则大量空间浪费的情况 链式存储： 链式储存相对于顺序存储来说更加的灵活，相同的是，第一步还是要自定义一个结构体。

struct Node
{
int data;
Node*last;
}

last存储的是下一个数据的地址，这样各个数据通过指针相连，就可以将顺序存储的缺点给消除掉。 在建立新的节点时，要用new来申请动态空间，虽然在单链表中相邻的数据遍历时是紧紧挨着的，但这并不代表相邻两个节点的地址是相连的。 优点： 相对于顺序存储来说，链式存储更加的灵活，不需要提前确定链表的长度 缺点： 访问时可能需要遍历所有的节点，使用时要特别注意空指针。

建表方式

无论是头插还是尾插都要先定义一个头节点或则头指针 头插建表： 头插建表就是不断在头节点之后并且紧邻头节点加入节点，（头节点之后的第一个节点是首元节点），即在头插建表时首元节点会不断地变化。

Node*first;
void create（）
{
first=new Node;  //头节点也需要申请内存
first->last=NULL;
int data;
Node *e;
while(cin>>data)
{
e=new Node;
e->data=data;
e->last=first->last;
first->last=e;
}
}

此时使用头指针还是头节点，分别插入数据时每次都是相同的。 尾插建表： 尾插法与头插法不同的点在于尾插是在尾部添加新节点，即尾节点是一直变化的，并且每一次添加节点时我们都需要确定尾节点，而获取单链表中的尾节点只有遍历，这种方式十分的浪费时间，为了减小程序的时间复杂度（减少程序运行时间），我们需要设立一个节点来储存尾节点：

Node*first;
void create（）
{
first=new Node;  //头节点也需要申请内存 这一步是必须做的
int data;
Node *e;
Node *h;      //用于储存尾节点
h=first;       
while(cin>>data)
{
e=new Node;
e->data=data;
h->last=e;
h=e;              //尾节点后移
}
e->last=NULL;     //最后进行赋空即可，前面每一次都赋空也可以。但浪费时间
}

单链表的遍历

Node *s;
s=first->last;   //因为需要不断的后移指针，直接对first后移会导致first变化，导致其他操作无法进行
while（s）
{
cout<<s->data;
s=s->last;
}

总结

单链表最容易出错的地方在于指针的运用，指针常常出错的原因大多是空指针的使用。