线性表——链表（c语言）

概念篇

对顺序表知识感兴趣的朋友可以看一下线性表-顺序表（c语言)。
对栈感兴趣的朋友可以看一下顺序表实现栈。
想进一步学习链表的朋友可以看下链表实现栈这篇文章。

示意图

1. 单向链表

2.双向链表

3.循环链表

4.链表的元素插入

5.链表的元素删除

代码篇

代码只展示单向链表的写法，其他链表的代码部分改动即可。下面的代码中没有头结点，是否定义头结点全凭个人的喜好。

1.链表的定义

1.链表由多个结点组成的，在定义链表之前要先声明结点。
2.通过结构体把一些属性封装起来表示结点和链表。

typedef struct node
{
	int data;
	//存放数据
	struct node*next;
	//指向后继结点的指针
}node;
typedef struct linkedlist
{
	node*head;
	//始终指向第一个结点的指针
	size_t size;
	//元素个数
}linkedlist;

2.链表的创建

linkedlist_create(linkedlist*list)
{
	list->head=NULL;
	//初始时链表为空，头指针为NULL 
	list->size=0;
	//初始时链表的元素个素为0
}

3.链表的销毁

链表的销毁就是释放所有结点所占有的内存空间。

linkedlist_destory(linkedlist*list)
{
	while(list->head)//为空时说明已经遍历到了最后一个结点
	{
		node*newnode=list->head;
		// 通过头指针的当前位置获取当前结点 
		list->head=list->head->next;
		// 更新头指针，使其指向下一个结点  
		free(newnode);
		//释放当前结点。
	}
}

4.链表的元素插入

1.判断插入的位置是否合法
2.处理插入的位置在第一个结点前面的情况
3.处理插入的位置不在第一个结点前面的情况

	linkedlist_insert(linkedlist*list,int index,int elements)
	{
		node*newnode=(node*)malloc(sizeof(node));
		//声明一个指向结点的指针，并为该指针分配内存
		newnode->data=elements;
		//将elements的值赋给该结点的data成员  
		if(index<0||index>list->size)
    	{
        	printf("invalid index\n");
        	return;
        	//插入的下标不合法则打印非法插入，返回。
    	}
		if(index==0)
		{
			//如果插入的位置在最前面
			newnode->next=list->head;
			//将新结点的next指针指向头指针指向的结点（第一个结点）
			list->head=newnode;
			//更新头指针
		}
		else
		{
			node*current=list->head;
			//初始化一个指针current指向链表的的一个结点
			for(int i=0;i<index-1;i++) 
				current=current->next;
				// 使用for循环来移动current指针，使其指向第 index-1 个节点
			newnode->next=current->next;
			//将新节点的next指针指向current节点的下一个节点
			current->next=newnode;
			//将新节点插入到current节点之后
		}
		list->size++;
		//更新链表的元素个素
	}

5.链表的元素删除

1.判断删除的位置是否合法
2.处理删除的结点是第一个结点的情况
3.处理删除的结点不是第一个结点前面的情况

void linkedlist_delete(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
    {
        printf("invalid index\n");
        return;
    }
    if(index==0)
    {
        node*newnode=list->head->next;
        //声明一个指针来指向链表的第二个结点
        free(list->head);
        //释放第一个结点的内存空间
        list->head=newnode;
        //更新头指针
    }
    else
    {
        node*current=list->head;
        for(int j=0;j<index-1;j++)
            current=current->next;
            // 循环直到找到要删除节点的前一个节点  
        node*newnode=current->next->next;
        //声明一个指针指向要删除结点的下一个结点。
         free(current->next); 
       // 释放要删除的结点的内存空间  
        current->next=newnode;
       // 将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
    }
    list->size--;
    //更新链表的元素个数
}

6.链表的元素查找

逐个遍历，满足条件就返回该结点

node* linkedlist_find(linkedlist*list,int value)
{
    node*current=list->head;
    while(current)
    {
        if(current->data==value)
            return current;
        current=current->next;
        //如果当前没找到就继续遍历
    }
    return NULL;
}

7.链表下标对应的结点

写这个函数是为了下面修改元素方便

node* linkedlist_index(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
        printf("invalid index\n");
    node*current=list->head;
    for(int j=0;j<index;j++)
        current=current->next;
    return current;
}

8.链表元素的修改

通过链表下标对应的结点函数找到索引对应的结点，直接修改结点的data成员

void linkedlist_alter(linkedlist*list,int index,int elements)
{
    node*newnode=linkedlist_index(list,index);
    // 通过索引找到链表中的结点，并将返回的指针赋值给newnode 
    if(newnode)
    //指针不为空
        newnode->data=elements;
}

9.链表的打印

逐个遍历结点，打印元素

void linkedlist_print(linkedlist*list)
{
    node*current=list->head;
    //初始化一个指针current指向链表的的一个结点
    while(current)
    {
        printf("%d->",current->data);
        current=current->next;
        
    }
    printf("NULL\n");
}

10.完整代码

#include
#include
typedef struct node
{
	int data;
	//存放数据
	struct node*next;
	//指向后继结点的指针
}node;
typedef struct linkedlist
{
	node*head;
	//始终指向第一个结点的指针
	size_t size;
	//元素个数
}linkedlist;
linkedlist_create(linkedlist*list)
{
	list->head=NULL;
	//初始时链表为空，头指针为NULL 
	list->size=0;
	//初始时元素个数为0
}
linkedlist_destory(linkedlist*list)
{
	while(list->head)//为空时说明已经遍历到了最后一个结点
	{
		node*newnode=list->head;
		// 通过头指针的当前位置获取当前结点 
		list->head=list->head->next;
		// 更新头指针，使其指向下一个结点  
		free(newnode);
		//释放当前结点。
	}
}
linkedlist_insert(linkedlist*list,int index,int elements)
{
	node*newnode=(node*)malloc(sizeof(node));
	//声明一个指向结点的指针并为指针分配内存空间
	newnode->data=elements;
	//将elements的值赋给该结点的data成员  
	if(index<0||index>list->size)
    {
        printf("invalid index\n");
        return;
        //插入的下标不合法则打印非法插入，返回。
    }
	if(index==0)
	{
		//如果插入的位置在最前面
		newnode->next=list->head;
		//将新结点的next指针指向头指针指向的结点（第一个结点）
		list->head=newnode;
		//更新头指针
	}
	else
	{
			node*current=list->head;
			//初始化一个指针current指向链表的第一个结点
			for(int i=0;i<index-1;i++) 
				current=current->next;
				// 使用for循环来移动current指针，使其指向第 index-1 个节点				 
			newnode->next=current->next;
			//将新节点的next指针指向current节点的下一个节点
			current->next=newnode;
			//将新节点插入到current节点之后
	}
	list->size++;
	//更新链表的元素个素
}
void linkedlist_delete(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
    {
        printf("invalid index\n");
        return;
    }
    if(index==0)
    {
        node*newnode=list->head->next;
        //声明一个指针来指向链表的第二个结点
        free(list->head);
        //释放第一个指针的内存空间
        list->head=newnode;
        //更新头指针
    }
    else
    {
        node*current=list->head;
        for(int j=0;j<index-1;j++)
            current=current->next;
            // 循环直到找到要删除节点的前一个节点  
        node*newnode=current->next->next;
        //声明一个结点指针来存放要删除的结点的后一个结点
         free(current->next); 
       // 释放要删除的结点的内存空间  
        current->next=newnode;
       // 将要删除节点的前一个节点的next指针指向要删除节点的下一个节点
    }
    list->size--;
    //更新链表的元素个数
}
node* linkedlist_find(linkedlist*list,int value)
{
    node*current=list->head;
    while(current)
    {
        if(current->data==value)
            return current;
        current=current->next;        
        //如果当前没找到就继续遍历
    }
    return NULL;
}
node* linkedlist_index(linkedlist*list,int index)
{
    if(index<0||index>=list->size)
        printf("invalid index\n");
    node*current=list->head;
    for(int j=0;j<index;j++)
        current=current->next;
    return current;
}
void linkedlist_alter(linkedlist*list,int index,int value)
{
    node*node=linkedlist_index(list,index);
    // 通过索引找到链表中的结点，并将返回的指针赋值给newnode 
    if(node)
    //指针不为空
        node->data=value;
}
void linkedlist_print(linkedlist*list)
{
    node*current=list->head;
    //初始化一个指针current指向链表的的一个结点
    while(current)
    {
        printf("%d->",current->data);
        current=current->next;
    }
    printf("NULL\n");
}
int main()
{
    linkedlist list;
    linkedlist_create(&list);
    linkedlist_insert(&list,0,10);
    linkedlist_insert(&list,1,20);
    linkedlist_insert(&list,2,30);
    linkedlist_insert(&list,3,40);
    printf("original list:");
    linkedlist_print(&list);
    linkedlist_delete(&list,2);
    linkedlist_alter(&list,1,100);
    printf("now list:");
    linkedlist_print(&list);
    return 0;
}

代码运行效果

以上是我对链表的见解，希望路过的大佬能指正错误并补充没涉及的知识，万分感谢！