The realization of the list

Before learning list we are going to have a look at the order of the table in front of the defect：

1. 中间/头部的插入删除,时间复杂度为O(N)

2. 增容需要申请新空间,拷贝数据,释放旧空间.会有不小的消耗.

3. 增容一般是呈2倍的增长,势必会有一定的空间浪费.例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间.

It is these defects,So just can have linked list to deal with these problems,Next we are going to study is a singly linked list,Singly linked lists of defects also many,While waiting for the follow-up to two-way cycle lead the list will be able to better solve these problems

链表的概念及结构

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

 The above is the list in the form of,There is a data to add a pointer for maintenance,防止数据的丢失.

链表的分类

1. 单向或者双向     2 . 带头或者不带头    3. 循环或者非循环

According to the permutation and combination we can know,总共有8种链表,当然,We only learn one of the most simple and most complex structure,Because it more specific;

1. 无头单向非循环链表：结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结 构的子结构,如哈希桶、图的邻接表等等.另外这种结构在笔试面试中出现很多.

2. 带头双向循环链表：结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都 是带头双向循环链表.另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带 来很多优势,实现反而简单了.

This time we are to achieve singly linked lists

链表的实现

先来看看接口

 对于数据结构来说,Generally we basically seize the add or delete check to start learning.

First of all, starting from the print,We can print with a single traverse

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

SLTNode* BuySLTNode(SLTDatatype x)//创建节点
{
	SLTNode* tmp = (SLTNode*)malloc(sizeof(SLTNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		tmp->data = x;
		tmp->next = NULL;
	}
	return tmp;
}

头插头删尾插尾删：Here to preach the secondary pointer because we want to change a head node,We're going to pass to change the primary pointer secondary pointer,And print function does not change the head node,So don't need to pass the secondary pointer.

void SLTNodePushFront(SLTNode** pphead, SLTDatatype x)//头插
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;//With no data
	 }
	else
	{
		//Processing data
		newnode->next = *pphead;
		*pphead = newnode;
	}
}


void SLTNodePopFront(SLTNode** pphead)//头删
{
	assert(pphead);
	assert(*pphead);//Make sure that the head has data can delete
	SLTNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
	cur = NULL;//养成好习惯,freeSet to null pointer after
}

void SLTNodePushBack(SLTNode** pphead, SLTDatatype x)//尾插
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;//没有数据
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
	
}

void SLTNodePopBack(SLTNode** pphead)//尾删
{
	assert(pphead);
	assert(*pphead);//Prevent when no data is also delete
	if ((*pphead)->next == NULL)//只有一个头节点
	{
		free((*pphead)->next);
	    *pphead= NULL;
	}
	else
	{
		//多个节点
		SLTNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			//Here to ensure that the address of a node to have before
			//To delete the next node,And link after next node
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
	
}

Below is a list of destruction：Because the list there is a link relationship,If there is no pointer to maintain,List, there is no way to link up again,导致数据的丢失.

void SLTNodeDestroy(SLTNode** pphead)//链表销毁
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;//记录下一个节点,防止找不到
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

查找：
 

SLTNode* SLTNodeFind(SLTNode* phead, SLTDatatype x)//查找
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

Modify the search is also realized,Section for any place to insert remove more convenient also：The following is achieved by looking for changes

void test3()
{
	SLTNode* plist = NULL;
	SLTNodePushBack(&plist, 1);
	SLTNodePushBack(&plist, 2);
	SLTNodePushBack(&plist, 3);
	SLTNodePushBack(&plist, 4);
	SLTNode* pos = SLTNodeFind(plist, 2);
	if (pos)
	{
		pos->data *= 30;//Here is equivalent to implement the change data
		printf("找到了%d\n",pos->data);
	}
	else
	{
		printf("找不到\n");
	}
	SLTNodePrint(plist);
}

Insert or delete data from the data front or more troublesome,But because the front insert demand is big,So will need to implement：

void SLTNodeInsert(SLTNode** pphead, SLTDatatype x,SLTNode* pos)
{
	//从x的前面插入数据
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == pos)
	{
		SLTNodePushFront(pphead, x);//头插
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev);//防止posThe wrong,Pass a null pointer,会导致死循环
		}
		newnode->next = prev->next;
		prev->next = newnode;
	}

}

void SLTNodeErase(SLTNode** pphead, SLTNode* pos)
{
	//pos前删除
	assert(pphead);
	assert(*pphead);//To prevent delete empty
	if (*pphead == pos)
	{
		SLTNodePopFront(pphead);//头删
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next->next != pos)
		{
			prev = prev->next;
		}
		free(prev->next);
		prev->next = pos;
	}
}

从posAfter a position for insertion or deletion is simple,这里就不多赘述：直接上代码

void SLTNodeInsertAfter( SLTDatatype x, SLTNode* pos)
{
	//在x的后面插入数据
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;//The two can't reverse,Otherwise can't link up
	pos->next = newnode;
}


void SLTNodeEraseAfter(SLTNode* pos)
{
	//pos之后删除
	assert(pos->next);//Prevent after no one
	SLTNode* tail = pos->next;
	pos->next = tail->next;
	free(tail);
	tail = NULL;
}

In the final to singly linked lists are not suitable for storing data,Just as other data structures of substructure,但是,对于面试来说,单链表非常重要,Because for two-way cycle lead the list,Structure more perfect,Nothing is worth to take an examination of,So investigation singly linked lists more test of our ability.