链表概述
　　链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
    链表的各类操作包括：单向链表的创建、删除（头删、尾删）、  插入（头插、C和C++尾插）、输出、  查找某一个结点、指定位置删除某结点等。

各种操作代码如下：

#include"SListNode.h"

SListNode* _BuyNode(DataType x)//开辟新节点
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	tmp->data = x;
	tmp->next = NULL;
	return tmp;
}
void PrintSList(SListNode* & pHead)//打印单链表
{
	SListNode* cur = pHead;
	if (pHead == NULL)
	{
		printf("SListNode is NULL!\n");
		return;
	}
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}
void DestoryList(SListNode* & pHead)//释放空间
{
	SListNode* cur = pHead;
	while (cur)
	{
		SListNode* tmp = cur;
		cur = cur->next;//顺序不可以颠倒
		free(tmp);
	}
	pHead = NULL;
}
void PushBack_C(SListNode** pHead, const DataType x)//c尾插
{
	//情况1.单链表为空；情况2.单链表不为空
	assert(pHead);
	if (*pHead == NULL)
		*pHead = _BuyNode(x);
	else
	{
		SListNode* tail = *pHead;
		while (tail->next != NULL)//找尾
			tail = tail->next;
		tail->next = _BuyNode(x);
	}
}
void PushBack_Cpp(SListNode* & pHead, const DataType x)//c++尾插,使用引用
{//引用相当于定义一个别名,不需断言指针
	//情况1.单链表为空；情况2.单链表不为空
	if (pHead == NULL)
		pHead = _BuyNode(x);
	else
	{
		SListNode* tail = pHead;
		while (tail->next != NULL)//找尾
			tail = tail->next;
		tail->next = _BuyNode(x);
	}
}
void PopBack(SListNode* & pHead)//尾删
{
	// 注意：单链表为空、一个节点以及多个节点的情况
	if (pHead == NULL)
	{
		printf("SListNode is NULL!\n");
		return;
	}
	else if (pHead->next == NULL)
	{//删除节点时置空并释放空间
		pHead = NULL;
		free(pHead);
	}
	else
	{
		SListNode* tail = pHead;
		while (tail->next->next != NULL)
		{//1 2 3 4删除4需要找到3(tail)
			tail = tail->next;
		}
		tail->next = NULL;
		free(tail->next);
	}
}
void PushFront(SListNode* & pHead, const DataType x)//头插
{//单链表为空、不为空
	if (pHead == NULL)
		pHead = _BuyNode(x);
	else
	{//利用两个指针pHead、tmp移动
		SListNode* tmp = _BuyNode(x);
		tmp->next = pHead;//针对没有头结点的情况
		pHead = tmp;
	}
}
void PopFront(SListNode* & pHead)//头删
{
	// 注意：单链表为空、一个节点以及多个节点的情况
	if (pHead == NULL)
	{
		printf("SListNode is NULL!\n");
		return;
	}
	else
	{
		SListNode* newhead = pHead->next;
		free(pHead);
		pHead = newhead;
	}
}
SListNode* Find(SListNode* pHead, const DataType x)//查找某数结点
{
	SListNode* cur = pHead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	printf("%d Position is not exist!", x);
	return NULL;
}
void Insert(SListNode* pos, const DataType x)//指定位置pos后插入新结点
{
	assert(pos);//断言pos有效性
	SListNode* tmp = _BuyNode(x);
	tmp->next = pos->next;
	pos->next = tmp;
}
void Erase(SListNode* & pHead, SListNode* pos)//删除某结点
{//考虑单链表是否空、pos是否为首元节点
	assert(pos);
	if (pos == pHead)
	{
		pHead = pHead->next;
		free(pos);
	}
	SListNode* prev = pHead;
	while (prev)
	{//1 2 3 4删除第三个节点3需找到其前一个节点2
		if (prev->next == pos)
		{
			prev->next = pos->next;
			pos = NULL;
			free(pos);
			return;
		}
		prev = prev->next;
	}
}

各函数测试用例如下：

#include"SListNode.h"

void Test1()
{//尾插尾删
	SListNode *phead = NULL;//注意需要置空
	PushBack_C(&phead, 1);
	PushBack_C(&phead, 2);
	PushBack_Cpp(phead, 3);
	PushBack_Cpp(phead, 4);
	PrintSList(phead);
	PopBack(phead);
	PopBack(phead);
	printf("\n---------------------\n");
	PrintSList(phead);
	PopBack(phead);
	PopBack(phead);
	printf("\n---------------------\n");
	PopBack(phead);
	printf("\n---------------------\n");
	PrintSList(phead);
	DestoryList(phead);
}

void Test2()
{//头插头删
	SListNode *phead = NULL;
	PushFront(phead, 1);
	PushFront(phead, 2);
	PushFront(phead, 3);
	PushFront(phead, 4);
	PrintSList(phead);
	PopFront(phead);
	PopFront(phead);
	printf("\n---------------------\n");
	PrintSList(phead);
	PopFront(phead);
	PopFront(phead);
	printf("\n---------------------\n");
	PopFront(phead);
	printf("\n---------------------\n");
	PrintSList(phead);
	DestoryList(phead);
}

void Test3()
{//查找某数节点、插入/删除新结点
	SListNode *phead = NULL;
	PushBack_Cpp(phead, 1);
	PushBack_Cpp(phead, 2);
	PushBack_Cpp(phead, 3);
	PushBack_Cpp(phead, 5);
	PushBack_Cpp(phead, 7);
	PushBack_Cpp(phead, 6);
	PrintSList(phead);
	printf("\n---------------------\n");
	printf("%d\n", Find(phead, 3)->data);
	printf("\n---------------------\n");
	Insert(Find(phead, 3), 4);
	PrintSList(phead);
	printf("\n---------------------\n");
	Erase(phead, Find(phead, 7));
	PrintSList(phead);
	DestoryList(phead);
}
int main()
{
	Test1();
	printf("\n***********************\n");
	Test2();
	printf("\n***********************\n");
	Test3();
	system("pause");
}

头文件如下：

#pragma once
#ifndef __SLISTNODE_H__
#define __SLISTNODE_H__

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include<assert.h>

typedef int DataType;
 
typedef struct SListNode
{
	DataType data;
	struct SListNode* next;
}SListNode;

SListNode* _BuyNode(DataType x);//开辟新节点
void PrintSList(SListNode* & pHead);//打印单链表
void PushBack_Cpp(SListNode* & pHead, const DataType x);//c++尾插
void PushBack_C(SListNode** pHead, const DataType x);//c尾插
void PopBack(SListNode* & pHead);//尾删
void PushFront(SListNode* & pHead, const DataType x);//头插
void PopFront(SListNode* & pHead);//头删
SListNode* Find(SListNode*  pHead, const DataType x);//查找某数结点
void Insert(SListNode* pos, const DataType x);//指定位置pos后插入新结点
void Erase(SListNode* & pHead, SListNode* pos);//删除某结点
void DestoryList(SListNode* & pHead);//释放空间

void PrintTailToHead(SListNode* pHead);//从尾到头打印单链表
void DelNonTailNode(SListNode* pos);//删除一个无头单链表的非尾节点
void InsertFrontNode(SListNode* pos, DataType x);//在无头单链表的一个非头结点前插入一个节点
SListNode* Rverse(SListNode* pHead);//逆置/反转单链表
SListNode* FindMidNode(SListNode* pHead);//查找单链表的中间节点，要求只能遍历一次链表
SListNode* FindMidNode(SListNode* pHead, DataType k);//查找单链表的倒数第k个节点，要求只能遍历一次链表

SListNode* MergeList(SListNode* L1, SListNode* L2);//合并两个有序链表，合并后依然有序
void BubbleSort(SListNode* pHead);//冒泡排序单链表
SListNode* JosephCycle(SListNode* pHead, int k);//单链表实现约瑟夫环
//判断单链表是否带环？若带环，求环长度，求环入口点
SListNode* CheckCycle(SListNode* pHead);//检查是否带环
int GetCycleLength(SListNode* MeetNode);//求环的长度
SListNode* GetEntryNode1(SListNode* pHead);//求环的入口地址
SListNode* GetEntryNode2(SListNode* pHead);//求环的入口地址


#endif //__SLISTNODE_H__

链表操作的其他实现见本人博客：

【面试题】单链表的操作1 http://10741357.blog.51cto.com/10731357/1736395

【面试题】单链表的操作2 http://10741357.blog.51cto.com/10731357/1736403

堆栈的简述：

1、管理方式和碎片问题

对于栈来讲，是由编译器自动管理，无须手工控制；对于堆来说，释放工作由程序员来控制，容易产生内存碎片；对于堆，频繁的new / delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序的效率降低。对于栈来讲，则不会出现这样的问题，因为栈是先进后出的队列，不可能有一个非栈顶的内存块从栈中间弹出，在它弹出之前，它上面后进的栈内容已经被弹出，因此不会出现不连续的碎片。

-----------------------------------------------------------------------------------------

2、分配效率

栈是系统提供的数据结构，计算机会在底层对栈提供支持，分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C / C++提供的，它的机制相对复杂；例如分配一块内存，会按照一定的算法（内存分配算法）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的内存空间（可能由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低很多。

-----------------------------------------------------------------------------------------

3、增长的方向不同

栈内存由一个栈指针esp来开辟和回收，栈内存是从高地址向低地址增长的，增长时，栈指针是向低地址方向移动，指针的地址值也就相应的减小；回收时，栈指针向高地址方向移动，地址值也就增加。所以栈内存的开辟与回收都只是指针的加减。

对于堆来讲，增长的方向是向上的，也就是向着内存高地址的方向移动；回收时，指针向低地址方向移动，地址值也就减小。

-----------------------------------------------------------------------------------------

4、空间大小不同

  一般来讲32位的系统下，堆内存可以达到4GB的空间，从这个角度来看堆内存几乎是没什么限制的。但是对于栈来讲，一般都有一定的空间大小。无论是堆还是栈，都要防止越界现象的发生，因为越界的结果要么是程序崩溃，要么是摧毁程序的堆、栈结构，产生意想不到的结果。