数据结构：线性表链式存储结构（单链表） C语言版

线性链表：

线性表的链式存储结构特点是用一种任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。这就意味这些数据元素可以存在内存未被占用的任意位置。 元素分布如下图：

因此，为了表示每个数据元素 $a_i$ai​ 与其直接后继数据元素 $a_{i+1}$ai+1​ 之间的逻辑关系，对数据元素$a_i$ai​ 来说，除了存储其本身的信息之外，还需存储一个指示其后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素 $a_i$ai​ 的存储映像，称为节点（node）。它包括两个域：其中存储数据元素信息的域称为数据域 ；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。$n$n 个节点 $[a_i(1\leqslant i \leqslant n) 的存储映像]$[ai​(1⩽i⩽n)的存储映像] 连接成一个链表，即线性表 $(a_1,a_2, ... , a_n)$(a1​,a2​,...,an​)
的链式存储结构，又由于此链表的每个节点只包含一个指针域，有称作线性表或单链表
单链表正是通过每个节点的指针域将线性表的数据元素按其逻辑次序连接在一起。如下图：

对于一个线性表，总有一个头和一个尾，链表也不例外。把链表中第一个节点的存储位置叫做头指针 ，那么整个链表的存储就必须从头指针开始进行了。之后的每个节点，其实就是上一个节点的后继指针指向的位置。
链表最后一个节点是不存在的，所以规定线性表的最后一个节点指针为"空"（NULL 或 ^ 符号表示）。

有时，为了更加方便的对链表进行操作，会在单链表的第一个结点之前附设一个结点，称为头结点。 头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头节点的指针域存储指向第一个节点的指针。

头结点与头指针的异同点：
头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标识作用，所以常用头指针冠以链表的名称。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

• 头结点是为了操作的同一和方便设计的，放在第一个元素结点之前，其数据域一般无意义（可以存放链表的长度，元素个数）。
• 有了头结点，对于在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就同一了。
• 头结点不一定是链表的必要元素。

线性表的链式存储结构描述：

若线性表为空，则头结点的指针域为空(NULL)：

单链表中元素与元素之间的逻辑关系：

若带有头节点的单链表：

线性表的链式存储结构代码实现：

基于Linux 内核链表实现。
定义头文件和链表数据结构：LinkList.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_



#define LINK_LIST_ERR		   (0)							/*非*/
#define LINK_LIST_COR		   (1)							/*是*/
#define LINK_LIST_NULL_ERR     (100)						/*参数为空错误*/
#define LINK_LIST_POS_ERR      (LINK_LIST_NULL_ERR+1)		/*元素位置参数非法*/
#define LINK_LIST_FULL_ERR     (LINK_LIST_NULL_ERR+2)		/*元素位置参数非法*/
#define LINK_LIST_LENGTH_ERR   (LINK_LIST_NULL_ERR+3)		/*链表长度（元素个数）错误*/

/*链表类型*/
typedef void LinkList;  


typedef struct _Tag_LinkListNode
{
	struct _Tag_LinkListNode* next;
}TLKTNode;/*链式元素节点类型 结点指针域*/


/**************************************************************
* 创建链表。
* -------------------------------------------------------------
* 参数		： void
*
* 返回值		： LinkList*    --- 链表指针
			   NULL			--- 空

**************************************************************/
LinkList* LinkList_Create();

/**************************************************************
* 释放销毁链表存储空间。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void LinkList_Destroy(LinkList* list);

/**************************************************************
* 清除链表数据。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void LinkList_Clear(LinkList* list);

/**************************************************************
* 获取链表数据个数。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： int             --- 链表数据个数
**************************************************************/
int LinkList_Length(LinkList* list);

/**************************************************************
* 向链表指定位置插入数据。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
			   TLKTNode* node      --- 待插入的元素
			   int pos             --- 插入位置下标
*
* 返回值		： int                 --- 1 | 0
**************************************************************/
int LinkList_Insert(LinkList* list, TLKTNode* node, int pos);

/**************************************************************
* 获取指定位置的元素。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
			   int pos             --- 元素位置下标
*
* 返回值		： TLKTNode*  | NULL  (元素指针 或 NULL)    
**************************************************************/
TLKTNode* LinkList_Get(LinkList* list, int pos);

/**************************************************************
* 获取指定位置的元素。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
               int pos             --- 元素位置下标
*
* 返回值		： TLKTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
TLKTNode* LinkList_Delete(LinkList* list, int pos);

#endif /*_LINKLIST_H_*/

数据操作函数实现：LinkList.c

#include <memory.h>
#include <stdlib.h>
#include <stdio.h>
#include "LinkList.h"



typedef struct _Tag_LINK_LIST
{
	TLKTNode  pHeader;
	int		  length;
}TList;/*内部抽象数据域，头结点定义*/



/**************************************************************
* 创建链表。
* -------------------------------------------------------------
* 参数		： void
*
* 返回值		： LinkList*    --- 链表指针
				OR
			   NULL			--- 空
**************************************************************/
LinkList* 
	LinkList_Create()
{
	TList* _ptrHead = NULL;
	_ptrHead = (TList*)malloc(sizeof(TList));
	memset(_ptrHead, 0x00, sizeof(TList));
	_ptrHead->length = 0;
	_ptrHead->pHeader.next = NULL;
	return _ptrHead;
}

/**************************************************************
* 释放销毁链表存储空间。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void 
	LinkList_Destroy(LinkList* list)
{
	if (list!=NULL)
	{
		free(list);
		list = NULL;
	}
	return ;
}

/**************************************************************
* 清除链表数据。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void 
	LinkList_Clear(LinkList* list)
{
	TList* _ptrTmp = NULL;
	if (list!=NULL)
	{
		_ptrTmp = (TList*)list;
		_ptrTmp->length = 0;
		_ptrTmp->pHeader.next = NULL;
	}
	return;
}

/**************************************************************
* 获取链表数据个数。
* -------------------------------------------------------------
* 参数		： LinkList* list  --- 链表指针
*
* 返回值		： int             --- 链表数据个数
**************************************************************/
int 
	LinkList_Length(LinkList* list)
{
	TList* _ptrTmp = NULL;
	if (list != NULL)
	{
		_ptrTmp = (TList*)list;
		return _ptrTmp->length;
	}
	return 0;
}

/**************************************************************
* 向链表指定位置插入数据。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
			   TLKTNode* node      --- 待插入的元素
               int pos             --- 插入位置下标
*
* 返回值		： int                 --- 1 | 0
**************************************************************/
int 
	LinkList_Insert(LinkList* list, TLKTNode* node, int pos)
{
	int		  ret = 0,i=0;
	TList*    _ptrTmp = NULL;
	TLKTNode* _currTmp = NULL;
	
	if (list==NULL||node==NULL)
	{
		ret = LINK_LIST_NULL_ERR;
		return ret;
	}
	if (pos<0)
	{
		ret = LINK_LIST_POS_ERR;
		return ret;
	}
	_ptrTmp = (TList*)list;
	_currTmp = &_ptrTmp->pHeader; //辅助指针指向链表头部
	for (i = 0; i < pos&&(_currTmp->next!=NULL);i++)
	{
		_currTmp = _currTmp->next; //辅助指针指向插入位置的前一元素节点
	}
	//插入
	node->next = _currTmp->next;//插入元素的下一节点指针 指向 当前辅助指针的下一节点 即 POS 位置原有的节点
	_currTmp->next = node;   //辅助指针的下一节点 指向插入元素的指针地址。  
	_ptrTmp->length++; //链表数据长度自增

	return LINK_LIST_COR;
}
 
/**************************************************************
* 获取指定位置的元素。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
int pos             --- 元素位置下标
*
* 返回值		： TLKTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
TLKTNode*
	LinkList_Get(LinkList* list, int pos)
{
	int		   i = 0;
	TList*    _ptrTmp = NULL;
	TLKTNode* _currTmp = NULL;

	if (list == NULL )
	{
		printf("Function: LinkList_Get() err=%d \n", LINK_LIST_NULL_ERR);
		return NULL;
	}
	if (pos < 0)
	{
		printf("Function: LinkList_Get() err=%d \n", LINK_LIST_POS_ERR);
		return NULL;
	}
	_ptrTmp = (TList*)list;
	_currTmp = &_ptrTmp->pHeader; //辅助指针指向链表头部
	for (i = 0; i < pos && (_currTmp->next != NULL); i++)
	{
		_currTmp = _currTmp->next; //辅助指针指向插入位置的前一元素节点
	}
	return _currTmp->next;
}

/**************************************************************
* 获取指定位置的元素。
* -------------------------------------------------------------
* 参数		： LinkList* list      --- 链表指针
			   int       pos       --- 元素位置下标
*
* 返回值		： TLKTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
TLKTNode*
	LinkList_Delete(LinkList* list, int pos)
{
	int		   i = 0;
	TList*    _ptrTmp = NULL;
	TLKTNode* _currTmp = NULL;
	TLKTNode* _posTmp = NULL;

	if (list == NULL)
	{
		printf("Function: LinkList_Delete() err=%d \n", LINK_LIST_NULL_ERR);
		return NULL;
	}
	if (pos < 0)
	{
		printf("Function: LinkList_Delete() err=%d \n", LINK_LIST_POS_ERR);
		return NULL;
	}
	_ptrTmp = (TList*)list;
	_currTmp = &_ptrTmp->pHeader; //辅助指针指向链表头部
	for (i = 0; i < pos && (_currTmp->next != NULL); i++)
	{
		_currTmp = _currTmp->next; //辅助指针指向插入位置的前一元素节点
	}
	_posTmp = _currTmp->next;//保存删除节点指针
	_currTmp->next = _posTmp->next;//链表连接跳过 pos 位置节点元素指针 
	_ptrTmp->length--;//链表元素长度递减
	return _posTmp;
}

调用示例：

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include "LinkList.h"


//数据元素定义，包含一个结点指针域
typedef struct _User_info
{
	TLKTNode* next;
	int age;
	char name[16];
}User;



int main(void)
{
	int ret = 0;
	int i = 0;
	User u1, u2, u3, u4, u5, u6;
	{
		u1.age = 11;
		u2.age = 12;
		u3.age = 13;
		u4.age = 14;
		u5.age = 15;
		u6.age = 16;
		strcpy(u1.name, "AAAA");
		strcpy(u2.name, "BBBB");
		strcpy(u3.name, "CCCC");
		strcpy(u4.name, "DDDD");
		strcpy(u5.name, "EEEE");
		strcpy(u6.name, "FFFF");
	}

	LinkList* list = NULL;
	list = LinkList_Create();

	if (list==NULL)
	{
		printf("链表创建失败！\n");
	} 
	else
	{
		printf("链表创建成功！\n");

		int len = LinkList_Length(list);
		printf("链表元素个数= %d！\n",len);

		//插入元素
		ret = LinkList_Insert(list, (TLKTNode*)&u1, 0);
		ret = LinkList_Insert(list, (TLKTNode*)&u2, 0);
		ret = LinkList_Insert(list, (TLKTNode*)&u3, 0);
		ret = LinkList_Insert(list, (TLKTNode*)&u4, 0);
		ret = LinkList_Insert(list, (TLKTNode*)&u5, 0);

	    len = LinkList_Length(list);
		printf("插入元素后，链表元素个数= %d！\n", len);


		for (i = 0; i < LinkList_Length(list); i++)
		{
			User* u = (User*)LinkList_Get(list, i);
			if (u==NULL)
			{
				printf("获取 下标=%d 的元素失败！\n",i);
				break;
			}
			printf("位置 %d , 元素数据：age=%d ; name=%s \n", i, u->age, u->name);
		}

		//开始删除元素
		while (LinkList_Length (list)>0)
		{
			LinkList_Delete(list,0);
		}

		//释放链表空间
		LinkList_Destroy(list);

	}
	system("PAUSE");
	return 0;
}

优点和缺点

优点：

• 无需一次性定制链表的容量
• 插入和删除操作无需移动数据元素

缺点：

• 数据元素必须保存后继元素的位置信息
• 获取指定数据的元素操作需要顺序访问之前的元素