单向链表在实际项目中的应用

前言

在实际项目中，单向链表经常被用来解决排队问题，因为链表允许动态地添加和移除元素，非常适合模拟队列（FIFO，先进先出）的行为。
这里的链表包含头节点，头结点的数据用来记录链表长度，该链表支持任意任意位置插入（插队）、尾插（按序排队），依据数据删除（找不到数据则返回错误），依据位置删除（超过链表节点数则返回失败）。

参考数据结构——单向链表-CSDN博客

有纰漏请指出，转载请说明。

学习交流请发邮件 [e-mail]

单向链表在排队应用中的解决方案

单向链表在实际项目中的应用非常广泛，特别是在处理排队问题时，其灵活性和高效性使其成为理想的数据结构之一。以下是一些单向链表在实际项目中应用于排队问题的例子：

1. 订单处理系统

在电商或餐饮等行业中，订单处理系统需要高效地管理大量的订单请求。使用单向链表，可以将新到达的订单添加到链表的尾部，表示订单队列的末尾。处理订单时，可以从链表的头部开始，依次处理每个订单，直到队列为空。这种方式能够确保订单按照到达的顺序被处理，同时支持快速的插入和删除操作。

2. 任务调度系统

在操作系统或分布式系统中，任务调度系统负责管理和分配计算资源给各个任务。使用单向链表，可以将待调度的任务按照优先级或到达时间排序，形成一个任务队列。调度器可以从链表的头部开始，依次选择任务进行调度。当任务完成后，可以从链表中删除该任务节点。这种方式能够确保任务按照预定的顺序被调度，同时支持动态的插入和删除操作。

3. 网络连接管理

在网络通信中，服务器需要管理大量的客户端连接。使用单向链表，可以将每个客户端连接作为一个节点添加到链表中，形成一个连接队列。服务器可以遍历链表，对每个连接进行处理，如发送数据、接收数据或关闭连接等。当有新连接到达时，可以将其添加到链表的尾部；当连接关闭时，可以从链表中删除该节点。这种方式能够高效地管理网络连接，支持快速的插入和删除操作。

4. 事件驱动系统

在事件驱动的应用程序中，如游戏或实时监控系统，事件需要按照发生的时间顺序被处理。使用单向链表，可以将事件按照发生时间排序，形成一个事件队列。事件处理器可以遍历链表，依次处理每个事件。当有新事件到达时，可以将其插入到链表的合适位置，以保持事件的顺序性。这种方式能够确保事件按照正确的时间顺序被处理，同时支持动态的插入操作。

5. 打印机队列管理

在打印系统中，打印机需要管理多个打印任务。使用单向链表，可以将每个打印任务作为一个节点添加到链表中，形成一个打印任务队列。打印机可以遍历链表，依次处理每个打印任务。当有新的打印任务到达时，可以将其添加到链表的尾部；当任务完成后，可以从链表中删除该节点。这种方式能够高效地管理打印任务，确保任务按照到达的顺序被处理。

综上所述，单向链表在实际项目中的应用非常广泛，特别是在处理排队问题时。其灵活性和高效性使其成为管理动态数据集合的理想选择之一。

单向链表操作相关函数

typedef int data_t;typedef struct node {data_t data;struct node * next;
}listNode, * linkList;linkList list_create(void) //创建链表，即头节点
{linkList list;list = (linkList)malloc(sizeof(listNode));//给节点动态分配内存if (list == NULL)//判断是否申请内存成功 {return list;}	//如果成功了，则进行赋初值list->data = 0; //一般存放节点个数list->next = NULL;//刚开始时没有节点插入链表，所以该头节点即是尾节点return list; //返回头节点指针
}int list_tail_insert(linkList list, data_t data) //传入待插入的链表地址和待插入的数据
{linkList p = NULL;//定义临时指针变量linkList q = NULL;if (list == NULL) //检验传入的链表是否有效{return -1;}//创建新节点并检查有效性，存放待插入数据if ((p = (linkList)malloc(sizeof(listNode))) == NULL){return -1;}p->data = data;p->next = NULL;q = list;while (q->next != NULL) //遍历链表找尾部{q = q->next;}q->next = p;//插入链表，尾部的next指针指向新节点list->data++;//插入数据后，数据个数加一 return 0;
}// 插入函数，位置从0开始计数
int list_insert_at_position(linkList list, int position, data_t data) {linkList p = NULL; // 新节点指针linkList q = list; // 用于遍历的临时指针linkList prev = NULL; // 用于记录当前节点的前一个节点int i = 0; // 位置计数器// 检查位置是否有效（非负且不大于当前链表长度）if (position < 0) {return -1; // 位置无效}// 创建新节点并检查内存分配是否成功if ((p = (linkList)malloc(sizeof(listNode))) == NULL) {return -1; // 内存分配失败}p->data = data;p->next = NULL;if (list->next==NULL && position==0) {list->data = 1;list->next = p;} else{q = q->next; //跳过头节点// 遍历链表找到插入位置while (q != NULL && i < position) {prev = q;q = q->next;i++;}// 检查位置是否超出了链表长度if (i > position) {// 如果i大于position，说明position是在链表尾部或之后的位置，应该插入到尾部prev->next = p;} else {// 否则，插入到指定位置if (prev != NULL) {p->next = q;prev->next = p;} else {// 如果prev是NULL，说明position是0，应该插入到链表头部p->next = list;list = p;}}list->data++;//插入数据后，数据个数加一 }return 0; // 插入成功
}//寻找链表上某一位置的节点的地址，返回该节点地址
linkList list_get_addr(linkList list, int pos) //传入链表指针和待寻找节点的位置
{linkList p = NULL;int i = -1;if (list == NULL) {return NULL;}if (pos == -1) {return list;//如果是-1，则返回链表头节点，因为用0表示第一个节点的位置}p = list;while (i < pos) //遍历寻找{p = p->next;if (p == NULL) //没有到达指定位置，链表已经结尾了，位置错误，返回NULL{return NULL;}i++;		}return p;
}int list_deleteBaseOnPos(linkList list, int pos) 
{linkList p = NULL;linkList deleteNode = NULL;if (list == NULL) return -1;p = list_get_addr(list, pos-1);//寻找待删除节点的上一个节点if (p == NULL) {return -1;//没有找到则返回}if (p->next == NULL) //如果要删除的节点不存在，则返回{return -1;}deleteNode = p->next;//找到要删除的节点//将待删除的next指针赋给上一个节点的next指针p->next = deleteNode->next;//也可以用p->next = p->next->next;//释放删除节点的内存free(deleteNode);deleteNode = NULL;list->data--;//删除节点后，数据个数减一 return 0;
}int list_deleteBaseOnData(linkList list, data_t data) 
{int pos = 0;linkList p = NULL;linkList q = NULL;linkList deleteNode = NULL;if (list == NULL) return -1;q = list->next;while (q->data != data) //遍历链表找相同数据{q = q->next;pos++;if (pos >= list->data){return -1;//没有找到则返回}}p = list_get_addr(list, pos-1);//寻找待删除节点的上一个节点if (p == NULL) {return -1;//没有找到则返回}if (p->next == NULL) //如果要删除的节点不存在，则返回{return -1;}deleteNode = p->next;//找到要删除的节点//将待删除的next指针赋给上一个节点的next指针p->next = deleteNode->next;//也可以用p->next = p->next->next;//释放删除节点的内存free(deleteNode);deleteNode = NULL;list->data--;//删除节点后，数据个数减一 return 0;
}

实例 

int main(void)
{ linkList list;	list = list_create();//外部调用函数进行创建if (list == NULL)return -1;list_insert_at_position(list,0,7);list_tail_insert(list, 6);//在链表尾部进行插入list_tail_insert(list, 2);//在链表尾部进行插入list_tail_insert(list, 5);//在链表尾部进行插入list_tail_insert(list, 3);//在链表尾部进行插入list_tail_insert(list, 4);//在链表尾部进行插入list_insert_at_position(list,2,1);list_deleteBaseOnData(list, 2);list_deleteBaseOnPos(list, 3);while (1){}
}

仿真结果

变量定义

创建链表

list = list_create();

在第“0”个位置插入数据7

list_insert_at_position(list,0,7);

依次尾插数据6 2 5 3 4 

    list_tail_insert(list, 6);//在链表尾部进行插入
    list_tail_insert(list, 2);//在链表尾部进行插入
    list_tail_insert(list, 5);//在链表尾部进行插入
    list_tail_insert(list, 3);//在链表尾部进行插入
    list_tail_insert(list, 4);//在链表尾部进行插入

在第“2”个位置插入数据1

list_insert_at_position(list,2,1);

找到数据为2的节点并删除

list_deleteBaseOnData(list, 2);