深入理解链表数据结构：从基础概念到带头结点链表的操作指南

任何学习数据结构的人都知道，链接列表是最基本的数据结构。作为合格的程序员，您应该清楚链接列表的操作。

1。什么是链接列表？

我的理解是，链接列表是由每个节点组成的线性表。每个节点的物理存储单元不连续，但是这些节点可以通过指针找到下一个节点的位置。

什么是节点？让我画一张图片来解释。

每个节点由数据域和指针域组成。数据域存储有关此节点的一些信息。指针域存储下一个节点的地址，并且该节点也通过指针域。在地址上找到下一个节点。

上图显示了节点如何通过指针字段找到下一个节点。

2。链接列表的基本操作

单个链接列表有两种形式，一个是领先的节点，另一个不是领先的节点。此博客使用领先的节点链接列表。没有数据保存在Head节点数据字段中，但是您可以存储此链接列表的长度。

创建链接列表

1。首先定义一个结构，其中包含一个数据字段和指针字段。

struct Node 
{
	int data;
	struct Node* next;
};

2。创建一个链接列表并初始化链接列表。

struct Node* createList()
{
	struct Node* list = (struct Node*)malloc(sizeof(struct Node));
	list->next = NULL;
	return list;
}

3。创建一个节点并初始化此节点

struct Node* createNode(int data)
{
	struct Node * node = (struct Node*)malloc(sizeof(struct Node));
	node->next = NULL;
	node->data = data;
	return node;
}

将节点插入链接列表

1。头插头

void headinsert(struct Node *list, int data)
{
	struct Node* node = createNode(data); //需要插入的结点
	node->next = list->next;
	list->next = node;
}

在这里，我正在用图片解释

标题插入方法是每个新插入的节点是标题节点的下一个节点。

①首先让新节点的指针指向原始标题节点的下一个节点。

②让头节点的指针指向新节点

这插入了头节点和原始第一个节点之间的新节点。

2。最终插入

插入尾巴有点麻烦，因此您必须首先找到此链接列表的尾部节点。

void backinsert(struct Node* list, int data)
{
	struct Node* newnode = createNode(data);
	struct Node* temp = list;//定义一个移动指针，用来找到链表尾部
	while (temp->next != NULL)//找到尾部的结点
	{
		temp = temp->next;
	}
	newnode->next = NULL; //将新结点的next置为null
	temp->next = newnode;//将新结点设置为尾部结点。
}

循环是找到此链接列表的尾部节点。找到它之后，只需将指针指向尾部节点的指针字段，以便将指针指向新节点。

3。在指定位置插入节点

以下代码在指定位置之前插入一个新节点。

void insertlocation(struct Node* list, int locat, int newdata)
{
	struct Node* newnode = createNode(newdata);
	struct Node* temp = list;
	struct Node* q = list->next;
	while (q->data != locat)
	{
		q = q->next;
		temp = temp->next;
		if (q == NULL)
		{
			printf("没有找到指定位置\n");
			return;
		}
	}
	newnode->next = temp->next;
	temp->next = newnode;
}

由于需要将其插入指定位置的前面，因此您需要知道其前面指定的节点和节点。温度用于表示指定节点的先前节点，Q用于查找指定节点的位置。如果P的数据字段与指定的数据不同，则两个指针同时向后移动。找到它后，插入。这里的插入方法与标头插入方法相同。

删除指定的节点

删除操作类似于在指定位置插入。首先，您必须穿越链接列表并找到需要删除的位置。同时，您必须找到此节点的先前节点。

void deletlocations(struct Node* list, int deldata)
{
	struct Node* temp = list;
	struct Node* p = list->next;
	while (p->data != deldata)
	{
		p = p->next;
		temp = temp->next;
		if (p == NULL)
		{
			printf("没有找到指定位置\n");
			return;
		}
	}
	temp->next = p->next;
	free(p);
	p = NULL;  //将这个指针置为NULL防止出现野指针
}

温度用于将先前的节点保存在指定的位置，P用于查找指定的节点。

找到此节点后，将上一个节点的指针字段指针指向指定节点的下一个节点，然后释放此节点p的内存空间。为防止野生指针的外观，请将此指针设置为空。

单连接列表遍历

遍历实际上要简单得多，所以我不会说太多。直接查看代码

void print(struct Node* list)
{
	struct Node * p = list->next;
	while (p)
	{
		printf("%d\t", p->data);
		p = p->next;
	}
	printf("\n");
}

单链接列表的逆顺序

单个链接列表的相反顺序实际上是一个相对复杂的操作。我认为这是一个链接列表，因此只有一个指针字段，其指针是指向下一个节点的地址。

反顺序是将尾部节点更改为第一个节点，然后依次更改原始指向顺序。使用图片说明

蓝色是原始链接列表，红色是在反向顺序之后。反向顺序之后将标题节点指向最后一个节点，然后从末端开始，依次指向其原始的先前节点，而原始的第一个节点则指向null。

从上图我们可以看到，在反向顺序之前需要保留第一个节点的位置。同样，由于它需要指向节点之前的节点，因此需要保留节点的位置，其后面的节点的位置以及当前节点的位置。

注意：如果此链接列表是一个空链接列表，则后一个链接列表只有一个节点（标题节点不计数），并且不需要反向顺序。

//单链表的逆序
//因为是单链表，所以需要保留当前结点、前一个结点的、还有下一个节点的位置
//头结点不动，最后将第一个（头结点的后一个）结点指向NULL，因此还要保留第二个结点的位置
void nixu(struct Node* list)
{
	struct Node *last = list->next;//保留第1个结点的位置
	struct Node *pre = list;       //保留上一个结点的位置
	struct Node *cur = list->next; //保留当前结点的位置
	struct Node *next = NULL;      //保留下一个结点的位置
	//如果这个链表是一个空链表就不要逆序
	if (list->next == NULL)
	{
		printf("这是一个空链表\n");
		return;
	}
	//如果这个链表只有一个结点，也不需要逆序
	if (list->next->next == NULL)
	{
		printf("这个链表只有一个元素，不需要逆序\n");
		return;
	}
	while (cur)
	{
		next = cur->next; //保留下原来下一个结点的位置
		cur->next = pre;  //把当前结点的下一个位置指向前一个结点
		pre = cur;        //把当前结点的next指向前一个结点后，将pre指向当前结点，用于下一个结点的逆序。
		cur = next;       //当前结点后移，移动到原来结点的下一个结点，就是next所指向的结点。
	}
	//除了最后一个结点，其他的都逆序完毕，这个时候把头结点的下一个结点指向最后一个结点
	list->next = pre;
	last->next = NULL;
}