数据结构（一）单链表

刷题、面试的时候总是会遇到诸如链表相关的题。来看看Leetcode上都有哪些题目：

一、什么是链表？

为了表示每个数据元素 a i a_i ai​与其直接后继数据 a i + 1 a_{i+1} ai+1​之间的逻辑关系，对于数据 a i a_i ai​来说，除了存储其本身的信息之外，还需存储一个指示其后继信息（即直接后继的存储位置）。我们把存储元素数据的域称为数据域，把存储在直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 a i a_i ai​的存储映像，称为节点。

对于链表而言头结点是可选的，它会出现在单链表的第一个结点前添加一个新的结点方便提供一些链表的额外信息（如长度）。

一个链表可以没有头结点，但是必须有头指针，因此链表名常用头指针表示。头结点的作用：

• 对链表的删除、插入操作时，第一个结点的操作更方便
• 统一空表和非空表的处理

具体的解释可以看https://blog.csdn.net/snow_7/article/details/106919353

按照指针域只有一个称为单链表，本节只介绍单链表，之后我们还会介绍循环链表和双向链表。

二、结点的结构

我们将会用指针来实现这个结构，这个结构至少包含两个部分，指针域和数据域。

typedef struct Node{
	int data;
	struct Node* next;
}Node;
typedef struct Node* pNode;//指向一个结点的指针

非常重要！！！！对于一个没有附加头结点的链表，头指针指向链表第一个结点；如果是一个附加头结点的链表，头指针则指向这个附加头结点。刷题的时候似乎都没有附加头结点，而且如果头结点指向空，那么链表长度为0，即空链表；若，头结点->next为空，则链表长度为1。头结点不等于第一个结点，他是在第一个之前的结点。

三、取值

//pHead在这里是一个指向头结点或者第一个结点
bool get_index_element(pNode pHead, int i, int* value)
{
	
	int j = 1;//用于标识当前检查的结点号
	pNode pCurNode = pHead->next;//j=1,cur指向结点1

    //进入循环的条件：没有达到链表最后结点或者还没检查到指定序号结点或给了一个比1还要小的检查序号
	while (pCurNode &&jnext;
		
	}
	
	//若到达最后了仍然没有找指定序号结点，那么说明长度不够，返回false
	//或者是用户给了一个不正确的序号参数(inext;
	while (pCurNode || j next;
		j++;
	}

	if (!pCurNode && i data = value;
	pNewNode->next = pCurNode->next;
	pCurNode->next = pNewNode;

	return true;
}

五、删除

bool delete_index_element(pNode pHead, int i, int *value)
{
	int j = 1;
	pNode pCurNode = pHead;

	while (!pCurNode->next || j next;
		j++;
	}
	if (!pCurNode->next || i next->data;
	pNode q=pCurNode->next;//必要操作，防止下一步pCurNode->next丢失掉需要释放空间的结点
	pCurNode->next = pCurNode->next->next;
	free(pCurNode->next);
	return true;

}

六、创建整个链表

创建一个链表根据插入方式可以分为前插和后插两种。

尾部插入法

//尾部插入法
void create_random_list(pNode* pHead, int n)
{
	srand(time(0));//初始化种子

	*pHead = (pNode)malloc(sizeof(Node));//创建头结点
	pNode pFinalNode = *pHead;
	pNode pNewNode = nullptr;

	for (int i = 0; i data = rand() % 100 + 1;
		cout next = nullptr;
}

这里，我们传递了结点的指针的指针，因为其头指针改变了指向，如果不涉及头结点的创建和删除可以不传递指针的指针。

七、删除整个链表

void clear_list(pNode pHead)
{
	pNode pCurNode= pHead->next;
	pNode pNextNode = pCurNode;
	while (pCurNode)//指针域不为空
	{
		pNextNode = pCurNode->next;
		free(pCurNode);
		pCurNode = pNextNode;
	}
	pHead->next = nullptr;

}

[1] https://blog.csdn.net/snow_7/article/details/106919353