链表是指用若干个结点连接在一起用于存储数据的数据结构，这些节结在物理内存上是离散的，但是在逻辑存储上是连续的。每个节结由两部分组成，如图1，第一部分用于存储数据，第二部分是一个指针，指针类型与结点类型相同，用于指向下一个结点。
图1 结点示意图
本文将对单链表的创建进行详述，单链表是指链表是单向的，每个结点只带有一个指针指向下一个结点，只能由上一个结点来寻找下一个结点，反之则不行。因此，单链表有所谓的头结点head与尾结点tail。以下是建立一个结点类的代码。
class Sint_Node { public: int info; Sint_Node *next; Sint_Node()//构造函数1，用此构造函数初始化创建的结点时，结点没有存储数据，并且指向的的下一个结点为空，可用于创建头结点 { next = 0; } Sint_Node(int num, Sint_Node *ptr)//构造函数2，用此构造函数初始化创建的结点时，可以存入数据，并且连接想要指向的下一结点 { info = num; next = ptr; } };接下来是创建一个链表类的代码
class S_list { private: Sint_Node *head, *tail; public: S_list() { head = tail = 0; }//链表初始化，空链表，头结点与尾结点的指针都为空 ~S_list();//析构函数 int isEmpty()//判断链表是否为空，在插入和删除时，都需要判断链表是否为空 { return head == 0; } void creat_head();//声明：创建头结点 void addTohead(int);//声明：从头部插入 void addTotail(int);//声明：从尾部插入 void deleteFromhead();//声明：从头部删除 void deleteFromtail();//声明：从尾部删除 void output();//声明：输出链表 };在这几个函数声明中，有几个地方需要注意的：1.链表初始化时，注意是指向头结点和尾结点的指针为空，也就是头结点和尾结点根本就不存在，而不是头结点和尾结点是空；2.我们需要一个创建头结点的函数，因为刚才我们也说到了新链表创建时头结点和尾结点根本就不存在，那么在插入时会导致本来是插入问题却变成了创建问题，为了让第一个结点的插入和之后的结点插入问题一致，对于空链表，我们通常需要手动创建一个头结点
接下来是每个成员函数的定义：
首先是析构函数：
S_list::~S_list() { for (Sint_Node *p; !isEmpty();)//依次删除头结点，直到为空 { p = head->next; delete head; head = p; } }然后是创建头结点：
void S_list::creat_head()//就是调用一下结点构造函数1 { head = new Sint_Node(); }然后是从头插法：
void S_list::addTohead(int x) { if (isEmpty())//如果链表为空，则创建头结点 creat_head(); else {} Sint_Node *new_head=new Sint_Node(); //要插入的结点 new_head->info = x; new_head->next = head->next;//这行代码与下行代码是精髓 head->next = new_head; }注意最后两行代码，它实现的效果如图2所示：
图2 头插入法效果示意图
从头部插入时，由于每次都是直接从头结点的位置插入，所以复杂度为O(1)。
最后是尾插法：
void S_list::addTotail(int y) { if (isEmpty()) { creat_head(); } else {} Sint_Node *q; tail = new Sint_Node(y, 0); for (q = head; q->next != 0; q = q->next);//每次都要定位到需要插入的地方，也就是尾结点前一个结点 q->next = tail; }尾插入时，如果链表为空，一样需要先创立一个头结点，然后将第一个需要插入的结点插入到头结点后面。由于每次都需要定位尾结点位置，因此，尾插入的算法复杂度为O(n)。
总结：头插入法，插入数据顺序会颠倒，算法复杂度为O(1);尾插入法，数据插入顺序正常，算法复杂度为O(n)。
