数据结构之链表

初识链表

链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点组成，节点在运行时动态生成，每个节点包括两个部分，一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

链表与数组区别

链表	数组
有相同数据类型的有续集，其中每个元素使用指针链接	相似数据类型的数据集合
链表不允许随机访问，元素只能被有序或顺序访问	数组元素可以使用数组索引随机访问
元素可能存储在内存的任意地方，链表创建一个指针指向相应的数据	数组的数据元素在内存中连续储存
链表的插入和删除操作非常快，时间为O(1)	插入和删除操作非常耗时，时间为O(n)，因为元素的内存地址是连续和固定的
链表的内存分配是动态的，在运行时动态分配	数组的内存是静态分配的，在编译期间完成
链表的大小随着元素的插入或删除变化	数组的大小必须在数组的声明或初始化的时候指定

数组优缺点

优点
- 随机访问性比较强，可以通过下标进行快速定位。
- 查找速度快
缺点
- 插入和删除的效率低，需要移动其他元素。
- 可能会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。
- 内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
- 数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。

链表优缺点

优点
- 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
- 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
缺点
- 查找的效率低，因为链表是从第一个节点向后遍历查找。

链表构成

链表由一个个节点构成，每个节点采用结构体的形式组织，例如：

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

单链表的增、删、改、查、插

增

// 链表末尾添加节点
int AddNode(Node* HeadNode,int data)
{
	Node* temp = HeadNode;
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL || temp == NULL)
		return 0; // 添加失败
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->next = newNode;
	newNode->data = data;
	newNode->next = NULL;
	HeadNode->data += 1; // 头节点记录添加了多少个节点
	return 1; // 添加成功
}

删

// 删除第num个节点
int DeleteNode(Node* HeadNode, int num)
{
	if (num <= 0)
		return 0; // 删除失败
	Node* temp = HeadNode, *last = NULL;
	while (num > 0 && temp != NULL)
	{
		num--;
		last = temp;
		temp = temp->next;
	}
	if (temp != NULL)
	{
		last->next = temp->next;
		free(temp);
		HeadNode->data -= 1;
		return 1; // 删除成功
	}
	else
		return 0; // 删除失败
}

改

// 修改第num个节点数据
int ChangeNode(Node* HeadNode, int num,int changed_data)
{
	Node* temp = HeadNode;
	while (num > 0 && temp != NULL)
	{
		num--;
		temp = temp->next;
	}
	if (temp != NULL)
	{
		temp->data = changed_data;
		return 1; // 修改成功
	}
	else
		return 0; // 修改失败
}

查

// 输出第num个节点数据
// 头节点-0 第一个普通节点-1
int SendData(Node* HeadNode, int num)
{
	Node* temp = HeadNode;
	while (num>0 && temp!=NULL)
	{
		num--;
		temp = temp->next;
	}
	if (temp != NULL)
	{
		return temp->data;
	}
	else
		return 0; // 输出失败
}

插

// 在第num节点前插入节点，成为第num个节点
int InsertNode(Node* HeadNode, int num, int data)
{
	Node* temp = HeadNode;
	Node* NewNode = (Node*)malloc(sizeof(Node));
	while ((--num) > 0 && temp != NULL)
	{
		temp = temp->next;
	}
	if (temp != NULL && NewNode != NULL)
	{
		NewNode->next = temp->next;
		NewNode->data = data;
		temp->next = NewNode;
		HeadNode->data += 1;
		return 1; // 插入成功
	}
	else
		return 0; // 插入失败
}