我们来看一道题，读完题后发现一个问题：在插入和删除元素（同学）时，需要移动大量的元素（同学），浪费了时间，那么有没有一种方法可以克服这些问题呢？
我们先甩开这道问题，看看关于他的学术性表示：

概念

在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用
计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。
它的优点如下： 
可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就
可以充分利用存储器的零碎空间。

为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、data）
外，还要存储它的直接后继元素的存储位置（指针域、link或 next）。我们把这两部分信息合在一起称为一
个“结点 node”。 
1、N 个结点链接在一起就构成了一个链表。N=0 时，称为空链表。 
2、为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的
物理位置，这个变量称为“头指针、H 或 head”。也可以把头指针定义成一个结点，称为“头结点”，头结点的
数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一
个结点的指针，若线性表为空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中
最后一个结点的指针域为空（NIL）。 
3、 由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单链表”。

看完这段描述，你是不是觉得晕头转向呢，我们先从火车开始研究。
火车由车头（相当于头指针）、车厢（相当于节点）、连接杆（各个节点的指针域）、行李车（相当于尾指针）组成，但是链表号火车不必连续在一起，也不必事先估计好内存空间。

具体实现（单向链表）

首先要定义一个结构体存储它本身的信息（数据域、data）和它的直接后继元素（下一项）的存储位置（指针域、link或 next）

typedef struct node{
    int data;
    node *next;
}node;

接下来，我们要定义并赋值一个头指针、一个尾指针、一个临时用于申请新节点的指针，这些都应是node类型的。并且加上一个输入用的int类型临时变量和输入数量。

node L;
L.next = NULL;
node *head=&L,*rea=&L,*s;
int x,n;

然后输入并插入
因为头插法是存储是倒着的，此处采用尾插法。

cin>>n;
for(int i=1;i<=n;i++){
	cin>>x;
	node *s=new node;//用new申请一个新的
	s->data=x;//把s的数据域赋值
	s->next=NULL;//把s的后继元素指针指向空
	rea->next=s; //最后一项的后级元素指针指向s
    rea = s;//最后一项指针指向s
}

有兴趣了解下头插法：

for(int i=1;i<=n;i++){
	cin>>x;
	node *s=new node;
	s->data=x;
	s->next=h->next;
	h->next=s; 
}

最后，输出：

node *p=h->next;//指针需要用“->”
while(p!=NULL){
	cout<<p->data<<" ";
	p=p->next;
}

这份代码可以作为模板，以后根据题目改动：

#include<iostream>
using namespace std;
typedef struct node{
	int data;
	node *next; 
}node;
int main(){
	node L;
	L.next=NULL;
	node *h=&L;
	node *rea=&L;
	int n,x;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		node *s=new node;
		s->data=x;
		s->next=NULL;
		rea->next=s; 
        rea = s;
	}
	node *p=h->next;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	return 0;
}

具体实现（双向链表）

单向链表只有一个指针next表示下一项，而开头的那道题中，有可能在元素（同学）前面（左边）插入元素（同学），所以需要使用双向链表。
实现也非常简单：在结构体node里加上一个指针，在插入时，也将指向前一项的指针（后文用pre代替）改变赋值即可。