C语言Link_List简单实现，不做线程控制
Link_List.h
/****************************************************************************
作者：代浩然
时间：2017-8-2
该文件定义为非线性链表相关的实现
线性链表的特性：
1、在内存中的存放地址是非连续的，随机分配
优点：
1、由于地址的非连续性，所以我们在随机插入的时候只需要找到插入的位置，然后将该位置的前后指针的位置只想该元素的地址就行，不需要重新分配内存
，一瞬间就能完成，速度非常快
缺点：
2、由于地址的非连续性，所以元素在内存中的存放位置是非固定的，所以就造成了第一个元素和第二个元素的内存位置跨度非常大，最大为4GB，所以CPU的PC
指针寻址非常慢。造成随机访问慢、遍历效率低下，释放空间效率低下
****************************************************************************/
#pragma once
#ifndef _Link_LIST_H
#define _Link_LIST_H
#ifdef __cplusplus
extern "C" {
#endif
//定义节点，双向链表
typedef struct _Link_Node{
void* data;//数据域
struct _Link_Node* priorNode;//指向上一个节点的指针
struct _Link_Node* nextNode;//指向下一个节点的指针
}Link_Node;
//定义链表结构
typedef struct _Link_List{
Link_Node *head;//链表的头指针
Link_Node *trail;//链表的尾部指针
unsigned long length;//链表的当前长度
}Link_List;
/**
* 功能：初始化链表
* 返回值：如果成功，则返回链表的地址，如果失败返回NULL
*/
Link_List* Link_List_Init();
/**
* 功能：随机插入链表
* 参数：
* pList：链表地址
* pData：插入的数据节点
* index：要插入的位置，如果为0，则默认从链表的开始处插入，如果为-1，则默认从链表的最后插入
* 返回值：成功返回0，失败返回-1
*/
int Link_List_Insert(Link_List* pList,void* pData,long index);
/**
* 功能：从某个位置取出元素
* 参数：
* pList：链表地址
* index：位置
* 返回值：返回数据体指针
*/
void* Link_List_GetAt(Link_List* pList,unsigned long index);
/**
* 功能：通过索引删除元素，删除元素只是将data域置为NULL，并不会释放data指针，由调用者释放
* 参数：
* pList：链表地址
* index：位置
*/
void Link_List_RemoveAt(Link_List* pList,unsigned long index);
/**
* 功能：清空链表
* 参数：
* pList：链表地址
*/
void Link_List_Clear(Link_List* pList);
/**
* 功能：释放链表空间
* 参数：
* pList：链表地址
*/
void Link_List_Free(Link_List* pList);
/**
* 功能：Link_List测试
*/
void Link_List_Test();
#ifdef __cplusplus
} /* end of the 'extern "C"' block */
#endif
#endif
Link_List.c
#include "Link_List.h"
#include <stdlib.h>
#include <malloc.h>
/**
* 功能：初始化链表
* 返回值：如果成功，则返回链表的地址，如果失败返回NULL
*/
Link_List* Link_List_Init()
{
Link_List* pList = NULL;
pList = (Link_List*)malloc(sizeof(Link_List));
if(pList == NULL)
{
return NULL;
}
pList->length = 0;
pList->head = NULL;
pList->trail = NULL;
return pList;
}
/**
* 功能：随机插入链表
* 参数：
* pList：链表地址
* pData：插入的数据节点
* index：要插入的位置，如果为0，则默认从链表的开始处插入，如果为-1，则默认从链表的最后插入
* 返回值：成功返回0，失败返回-1
*/
int Link_List_Insert(Link_List* pList,void* pData,long index)
{
long i = 0;
if(pList == NULL)
return -1;
if(index < -1 || (index > pList->length && index != -1))
{
return -1;
}
//判断是否是首次插入
if(pList->length == 0)
{
Link_Node* pNode = (Link_Node*)malloc(sizeof(Link_Node));
if(pNode == NULL)
return -1;
pNode->data = pData;
pNode->priorNode = NULL;
pNode->nextNode = NULL;
pList->head = pNode;
pList->trail = pNode;
pList->length++;
return 0;
}
else
{
if(-1 == index)//从末尾处插入
{
//创建节点
Link_Node* pNode = (Link_Node*)malloc(sizeof(Link_Node));
if(pNode == NULL)
return -1;
pNode->data = pData;
pNode->nextNode = NULL;
pNode->priorNode = pList->trail;
//将节点加到末尾处
pList->trail->nextNode = pNode;
pList->trail = pNode;
pList->length++;
}
else if(0 == index) //从开始处插入
{
//创建节点
Link_Node* pNode = (Link_Node*)malloc(sizeof(Link_Node));
if(pNode == NULL)
return -1;
pNode->data = pData;
pNode->nextNode = pList->head;
pNode->priorNode = NULL;
//将节点加载到头部
pList->head->priorNode = pNode;
pList->head = pNode;
pList->length++;
return 0;
}
else//指定位置插入
{
//后期可以使用快速查找算法优化
Link_Node* pNode = pList->head;
i=0;
while(pNode != NULL)
{
if(index == i)//查找到要插入的位置节点
{
//创建节点
Link_Node* pCurrentNode = (Link_Node*)malloc(sizeof(Link_Node));
if(pCurrentNode == NULL)
return -1;
pCurrentNode->nextNode = pNode;
pCurrentNode->priorNode = pNode->priorNode;
pNode->priorNode->nextNode = pCurrentNode;
pNode->priorNode = pCurrentNode;
pList->length++;
return 0;
}
pNode = pNode->nextNode;
i++;
}
}
}
return 0;
}
/**
* 功能：从某个位置取出元素
* 参数：
* pList：链表地址
* index：位置
* 返回值：返回数据体指针
*/
void* Link_List_GetAt(Link_List* pList,unsigned long index)
{
int i = 0;
Link_Node* pNode = NULL;
if(pList == NULL)
{
return NULL;
}
i = 0;
pNode = pList->head;
while(pNode != NULL)
{
if(i == index)
{
return pNode->data;
}
pNode = pNode->nextNode;
i++;
}
return NULL;
}
/**
* 功能：通过索引删除元素，删除元素只是将data域置为NULL，并不会释放data指针，由调用者释放
* 参数：
* pList：链表地址
* index：位置
*/
void Link_List_RemoveAt(Link_List* pList,unsigned long index)
{
int i = 0;
Link_Node* pNode = NULL;
if(pList == NULL)
{
return;
}
i = 0;
pNode = pList->head;
while(pNode != NULL)
{
if(i == index)
{
//找到节点，开始删除
if(pNode->priorNode == NULL) //表示链表头部节点
{
Link_Node* head = pList->head;
pList->head = head->nextNode;
pList->head->priorNode = NULL;
free(head);//释放节点
pList->length--;
}
else if(pNode->nextNode == NULL)//表示链表尾部节点
{
Link_Node* trial = pList->trail;
pList->trail = trial->priorNode;
pList->trail->nextNode = NULL;
free(trial);//释放节点
pList->length--;
}
else
{
//当前节点的上一个节点的下一个节点指向当前节点的下一个节点
pNode->priorNode->nextNode = pNode->nextNode;
//当前节点的下一个节点的上一个节点指向当前节点的上一个节点
pNode->nextNode->priorNode = pNode->priorNode;
free(pNode);
pList->length--;
}
return;
}
pNode = pNode->nextNode;
i++;
}
}
/**
* 功能：清空链表
* 参数：
* pList：链表地址
*/
void Link_List_Clear(Link_List* pList)
{
//将数据域置为空
Link_Node* pNode = NULL;
if(pList == NULL)
{
return;
}
//从尾部开始释放
pNode = pList->trail;
while(pNode != NULL)
{
pList->trail = pNode->priorNode;
free(pNode);
pNode = pList->trail;
}
pList->length = 0;
pList->head = NULL;
pList->trail = NULL;
}
/**
* 功能：释放链表空间
* 参数：
* pList：链表地址
*/
void Link_List_Free(Link_List* pList)
{
Link_Node* pNode = NULL;
if(pList == NULL)
{
return;
}
//从尾部开始释放
pNode = pList->trail;
while(pNode != NULL)
{
pList->trail = pNode->priorNode;
free(pNode);
pNode = pList->trail;
}
pList->length = 0;
pList->head = NULL;
pList->trail = NULL;
free(pList);
pList = NULL;
}
/**
* 功能：Link_List测试
*/
void Link_List_Test()
{
int i = 0;
int *p = NULL;
Link_List* list = Link_List_Init();
//动态添加1000个值
for(i = 0;i < 1000;i++)
{
p = (int*) malloc(sizeof(int));
*p = i;
Link_List_Insert(list,p,-1);
}
//取出第500个元素
p = (int*)Link_List_GetAt(list,499);
//删除第500个元素，删除之后记得释放
Link_List_RemoveAt(list,499);
free(p);
//重新获取第500个元素
p = (int*)Link_List_GetAt(list,499);
//开始释放空间
for(i = 0;i<list->length;i++)
{
p = (int*)Link_List_GetAt(list,i);
free(p);
}
Link_List_Clear(list);
Link_List_Free(list);
}
