[数据结构与算法]2021年7月28日c语言 链表的发展及应用

链表：由分布在内存不同位置的节点，通过成员指针所连接起来的表结构，节点之间存在一对一关系。内存近乎无限
优点：对内存依懒性不高，插入删除方便可以使用小块的内存
可以根据元素数量动态调整链表长度，节约内存，还可以几乎无限的添加元素
缺点：频繁的创建删除节点可能出现内存碎片不能随机访问，只能从头节点按个遍历
所以访问速度慢。
链表由一个个节点组成，而节点由两个部分组成，一个是数据域和一个指向下一个节点的指针域组成，便于理解数据用int类型。下面是节点定义：

// 链表的节点
typedef struct Node
{
	TYPE data;			// 数据域
	struct Node* next;	// 指针域
}Node;

然后是节点的创建：

//创建节点
Node* create_node(TYPE data)
{
	//给节点分配内存
	Node* node = malloc(sizeof(Node));
	//数据域赋值
	node->data = data;
	//指针域初始化
	node->next = NULL;
	return node;
}

链表的创建：

typedef struct List
{
	Node* head;    //指向第一个节点
	Node* tail;    //指向最后一个节点
}List;

这是最基础的链表创建，没有什么实际应用价值
一般来说是不用尾指针取而代之 的是size链表长度：

typedef struct List
{
	Node* head;    //指向第一个节点
	size_t size;
}List;

而为了方便一般来说都会舍弃头节点，把他变成空头，这样能大大减少逻辑复杂度。
有空头的头添加：

void add_head_list(Node* head,TYPE data)
{
	Node* node = create_node(data);
	node->next = head->next;
	head->next = node;
}
/*在main函数里定义头部， 一个什么都不做的头节点，只为了占位*/
	Node* head = create_node(0);	

而无空头有尾的头添加：

void adding_head_list(List* list,TYPE data)
{
	Node* node = create_node(data);
	if(empty_list(list))
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		node->next = list->head;
		list->head = node;
	}
}

无空头无尾的两种头添加：

1.
void add_head_list(Node** head,TYPE data)
{
	Node* node = create_list(data);
	if(NULL == *head)
		node->next = *head;
	*head = node;
}
2、
Node* add_head_list(Node* head,TYPE data)
{
	Node* node = create_list(data);
	node->next = head;
	return node;
}

从代码中可以明显的看到空头起到了二重指针的作用。虽然从代码量中看不出来太大差距但是对比一下尾添加就知道了
无空头尾添加：

void add_tail_list(Node** head,TYPE data)
{
	Node* node = create_list(data);
	if(NULL == *head)
	{
		*head = node;
		return ;
	}
	Node* tail = *head;
	while(NULL != tail->next->next) tail = tail->next;
	tail->next = node;
}

有空头的尾添加：

void add_tail_list(Node* head,TYPE data)
{
	Node* tail = head;
	while(NULL != tail->next) tail=tail->next;
	tail->next = create_node(data);
}

现在从代码量中就可以看出有空头的便捷性。