数据结构之线性表——链表的链式存储（链式描述）

1 基本概念

链式存储定义：为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。在线性表的链式描述中，线性表的元素在内存中的存储位置是随机的。每个元素都有一个明确的指针指向线性表的下一个元素的位置。在顺序表中元素的的地址是按照顺序排序的，在链式描述中，元素的地址是随机的。

链表的链式存储示意图

链式存储头结点：表示链表中的第一个节点，包含指向第一个数据元素的指针以及链表自身的一些信息

链式存储的数据节点：链表中代表数据元素的节点，包含指向下一个数据元素的指针和数据元素的信息

链式存储的尾节点：链表中最后一个数据元素的节点，其下一元素指针为空，表示没有后继结点

2 链表技术领域推演

思考：怎样才能让链式链表的业务节点和算法进行分离？

链表领域的技术推演图：

（1）传统链表：

（2）Linux内核链表

（3）企业通用链表

本文线性表的链式存储方式的实现就是采用第三种方式的链表。

3 链表的具体实现分析

（1）节点指针域定义

typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* next;
}LinkListNode;

（2 ）头结点定义

typedef struct _tag_LinkList
{
	LinkListNode header;//包含指针域节点
	int		length;//头结点自身的信息
}TLinkList;

（3）数据元素定义示例

typedef struct _Teacher
{
	LinkListNode node;//包含指针域节点
	//下面是业务域
	char		name[32];
	int			age ;
}Teacher;

（4）链表的创建

LinkList* LinkList_Create()  //O(1)
{
	TLinkList *tmp = NULL;

	tmp = (TLinkList *)malloc(sizeof(TLinkList));//申请一个头结点空间
	if (tmp == NULL)
	{
		printf("func LinkList_Create() err \n");
		return NULL;
	}
	memset(tmp, 0, sizeof(TLinkList));
	tmp->length = 0;//将链表的长度置为0
	tmp->header.next = NULL; //链表头结点的指针域指向NULL
	return tmp;//返回头结点
}

（5）链表的销毁

void LinkList_Destroy(LinkList* list)  //O(1)
{
	if (list == NULL)//链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
	{
		return ;
	}
	free(list);//释放头结点空间
	return ;
}

（6）链表的清空

void LinkList_Clear(LinkList* list)   //O(1)
{
	TLinkList *tList = NULL;
	tList = (TLinkList *)list;//链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0
	if (tList == NULL)
	{
		return ;
	}
	tList->header.next = NULL;
	tList->length = 0;

	return ;
}

（7）链表的长度

int LinkList_Length(LinkList* list)  //O(1)
{
	TLinkList *tList = NULL;
	tList = (TLinkList *)list;
	if (tList == NULL)
	{
		return -1;
	}
	return tList->length;//链表的长度返回头结点中的length
}

（8）链表的插入

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)  //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;
	
	if (list==NULL || node==NULL || pos<0)
	{
		return -1;
	}
	current = &(tList->header);//当前节点指向头结点指针域
	for (i=0; i<pos; i++)//current节点跳到要插入节点的头一个结点
	{
		current = current->next;
	}
	//新结点 连接 后继链表
	node->next = current->next;//node的节点的指针域指向current节点的下一个节点
	//前面的链表 连接 新结点
	current->next = node;//current节点的指针域指向node节点
	tList->length ++;//链表的长度加一
	return 0;
}

（9）获取链表元素

LinkListNode* LinkList_Get(LinkList* list, int pos)  //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;

	if (list==NULL || pos<0)
	{
		return NULL;
	}

	current = &(tList->header); //赋值指针变量初始化
	for (i=0; i<pos; i++)
	{
		current = current->next;//current指针向后跳
	}
	return current->next;//返回current指向节点的下一个节点的
}

（10）删除链表某一位置元素

LinkListNode* LinkList_Delete(LinkList* list, int pos) //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	LinkListNode	*ret = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;
	if (list==NULL || pos<0)
	{
		return NULL;
	}

	current = &(tList->header);
	for (i=0; i<pos; i++)
	{
		current = current->next;
	}
	ret = current->next; //缓存要删除的结点

	current->next = ret->next;

	tList->length --;

	return ret;
}

4 具体的实现代码

//LinkList.h
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_

typedef void LinkList;//链表的句柄

typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* next;
}LinkListNode;

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif

//LinkList.cpp
#define  _CRT_SECURE_NO_WARNINGS 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linklist.h"

typedef struct _tag_LinkList
{
	LinkListNode header;
	int		length;
}TLinkList;
//
LinkList* LinkList_Create()  //O(1)
{
	TLinkList *tmp = NULL;

	tmp = (TLinkList *)malloc(sizeof(TLinkList));//申请一个头结点空间
	if (tmp == NULL)
	{
		printf("func LinkList_Create() err \n");
		return NULL;
	}
	memset(tmp, 0, sizeof(TLinkList));
	tmp->length = 0;//将链表的长度置为0
	tmp->header.next = NULL; //链表头结点的指针域指向NULL
	return tmp;//返回头结点
}

void LinkList_Destroy(LinkList* list)  //O(1)
{
	if (list == NULL)//链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
	{
		return ;
	}
	free(list);//释放头结点空间
	return ;
}

void LinkList_Clear(LinkList* list)   //O(1)
{
	TLinkList *tList = NULL;
	tList = (TLinkList *)list;//链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0
	if (tList == NULL)
	{
		return ;
	}
	tList->header.next = NULL;
	tList->length = 0;

	return ;
}

int LinkList_Length(LinkList* list)  //O(1)
{
	TLinkList *tList = NULL;
	tList = (TLinkList *)list;
	if (tList == NULL)
	{
		return -1;
	}
	return tList->length;//链表的长度返回头结点中的length
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)  //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;
	
	if (list==NULL || node==NULL || pos<0)
	{
		return -1;
	}
	current = &(tList->header);//当前节点指向头结点指针域
	for (i=0; i<pos; i++)//current节点跳到要插入节点的头一个结点
	{
		current = current->next;
	}
	//新结点 连接 后继链表
	node->next = current->next;//node的节点的指针域指向current节点的下一个节点
	//前面的链表 连接 新结点
	current->next = node;//current节点的指针域指向node节点
	tList->length ++;//链表的长度加一
	return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)  //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;

	if (list==NULL || pos<0)
	{
		return NULL;
	}

	current = &(tList->header); //赋值指针变量初始化
	for (i=0; i<pos; i++)
	{
		current = current->next;//current指针向后跳
	}
	return current->next;//返回current指向节点的下一个节点的
}

LinkListNode* LinkList_Delete(LinkList* list, int pos) //O(n)
{
	int				i = 0;
	LinkListNode	*current = NULL;
	LinkListNode	*ret = NULL;
	TLinkList		*tList = NULL;

	tList = (TLinkList *)list;
	if (list==NULL || pos<0)
	{
		return NULL;
	}

	current = &(tList->header);
	for (i=0; i<pos; i++)
	{
		current = current->next;
	}
	ret = current->next; //缓存要删除的结点

	current->next = ret->next;

	tList->length --;

	return ret;
}

//test.cpp
#define  _CRT_SECURE_NO_WARNINGS 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linklist.h"

typedef struct _Teacher
{
	LinkListNode node;//包含指针域节点
	//下面是业务域
	char		name[32];
	int			age ;
}Teacher;


void main()
{
	LinkList	*list = NULL;
	int			i = 0;

	Teacher t1, t2, t3, t4, t5, t6;//节点生命周期在这里由main函数管理
	t1.age = 31;
	t2.age = 32;
	t3.age = 33;
	t4.age = 34;
	t5.age = 35;
	t6.age = 36;

	list = LinkList_Create();

	//思考1: 业务节点 和 链表算法是如何分离
	//思考2:  业务节点的生命周期 归谁管...


	//插入元素
	LinkList_Insert(list, (LinkListNode *)&t1, 0);
	LinkList_Insert(list, (LinkListNode *)&t2, 0);
	LinkList_Insert(list, (LinkListNode *)&t3, 0);
	LinkList_Insert(list, (LinkListNode *)&t4, 0);
	LinkList_Insert(list, (LinkListNode *)&t5, 0);
	LinkList_Insert(list, (LinkListNode *)&t6, 3);


	//遍历链表
	for (i=0; i<LinkList_Length(list); i++)
	{
		Teacher *tmp = (Teacher *)LinkList_Get(list, i);
		if (tmp == NULL)
		{
			return ;
		}
		printf("age:%d \n", tmp->age);
	}


	//删除链表结点
	while (LinkList_Length(list) > 0)
	{
		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
		if (tmp == NULL)
		{
			return ;
		}
		printf("age:%d \n", tmp->age);
	}

	LinkList_Destroy(list);


	printf("hello...\n");
	system("pause");
	return ;
}

5 链表的链式存储优缺点

优点：

（1）无需一次性定制链表的容量

（2）插入和删除操作无需移动数据元素

缺点：

（1）数据元素必须保存后继元素的位置信息

（2）获取指定数据的元素操作需要顺序访问之前的元素

原文链接：https://blog.csdn.net/ds_kuen/article/details/71601389