写在前面

博主教你用最简单的方式，让你彻底理解链表，实现链表。 学习链表，要多调试，多画图，自己多实现几遍，拿下链表不在话下！
@TOC

本节目标

1.链表表示和实现（单链表+双向链表）
2.链表的常见OJ题
3.顺序表和链表的区别和联系

链表表示和实现（单链表+双向链表）

顺序表的问题及思考问题：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
4. 思考：如何解决以上问题呢？下面给出了链表的结构来看看。

链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

逻辑结构

想必大家看的都是链表的逻辑结构，其实真实并不存在连接两个链表的箭头，为了更好理解罢了。箭头代表前面的节点存了，后面节点的指针。
物理结构
物理结构就是真正的结构，便于初学者学习!
是不是突然对链表有了更深刻的理解！

单链表的实现

// 1、无头+单向+非循环链表增删查改实现
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

链表节点创建
链表的创建也是用结构体创建。

  //类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType date;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;

// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
   newnode->date = x;
   newnode->next = NULL;
   return newnode;
}

// 打印
void SListPrint(SLTNode* phead)
{
   while (phead != NULL)
   {
   	printf("%d ", phead->date);
   	phead = phead->next;
   }
   printf("NULL\n");
}

//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
   if (*pphead == NULL)
   {
   	*pphead = BuySListNode(x);
   }
   else
   {
   	SLTNode* tail = *pphead;
   	while (tail->next)
   	{
   		tail = tail->next;
   	}
   	tail->next = BuySListNode(x);
   }
}

//头插接口测试
void TestSList2()
{
   SLTNode* plist = NULL;
   SListPushFront(&plist, 1);
   SListPushFront(&plist, 2);
   SListPushFront(&plist, 3);
   SListPushFront(&plist, 4);
   SListPushFront(&plist, 5);
   SListPushFront(&plist, 6);
   SListPrint(plist);
}

//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
   if (!*pphead)
   {
   	*pphead= BuySListNode(x);
   }
   else
   {
   	SLTNode* first = BuySListNode(x);
   	first->next = *pphead;
   	*pphead = first;
   }
}

//头插接口测试
void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
}

//头删
void SListPopFront(SLTNode** pphead)
{
	if (!*pphead)
	{
		return;
	}	
	else
	{
		*pphead = (*pphead)->next;
	}
}

//头删接口测试
void TestSList3()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}

//尾删
void SListPopBack(SLTNode** pphead)
{
	//1头结点为空
	//2只有一个节点
	//3多个节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next ==NULL)
	{
		*pphead = NULL;
		free(*pphead);
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* ret = *pphead;
		while (tail->next)
		{
			ret = tail;
			tail = tail->next;
		}
		tail = NULL;
		ret->next = NULL;
		free(tail);
	}
}

//尾删接口测试
void TestSList4()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);
}

//查找节点x位置并返回节点位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	if (phead == NULL)  //节点为空
	{
		return NULL;
	}
	else
	{
		SLTNode *ret= phead;
		while (ret) 
		{
			if (ret->date == x)    //找到了
			{
				return ret;
			}
			ret = ret->next;
		}
		return NULL;           //找不到
		
	}
}

// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		return;
	}
	else if(*pphead==pos)
	{
		*pphead = newnode;
		newnode->next = pos;
	}
	else
	{
		SLTNode* ret = *pphead;
		while (ret->next != pos)
		{
			ret = ret->next;
		}
		ret->next = newnode;
		newnode->next = pos;
	}
	
}

//任意位置查找插入测试

void TestSList5()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	SListPrint(plist);
	SLTNode* pos = SListFind(plist,3);
	if (pos)
	{
		SListInsert(&plist,pos,0);
	}
	SListPrint(plist);
}

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead==NULL)
	{
		return;
	}
	else if (*pphead == pos)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* ret = *pphead;
		while (ret->next != pos)
		{
			ret = ret->next;
		}
		ret->next = pos->next;
		pos = NULL;
		free(pos);
	}
}

//任意位置修改接口测试
void TestList6()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 5);
	SListPushBack(&plist, 6);
	SListPrint(plist);
	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

单链表的实现就学习到这里，还有很多接口，等以后我们再学习吧，单链表结构简单但是实现复杂，我们下期博客学习双链表的实现！结构复杂，实现简单…未完待续····