1. Toy模板网首页
  2. > Toy博客

C语言/C++实现链表的详细教程

9月前 作者：toMontain 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了C语言/C++实现链表的详细教程。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C语言/C++实现链表的详细教程

1. 什么是链表

链表是一种常用的数据结构，它由一系列节点组成，每个节点包含两部分内容：数据和指向下一个节点的指针,最后一个节点指向空。链表的节点可以动态添加和删除，因此可以方便地进行插入、删除等操作。链表有多种类型，包括单向链表、双向链表和循环链表等。

1.1 单向链表（Singly Linked List）

单向链表是最简单的链表类型，它的每个节点只包含一个指向下一个节点的指针。单向链表的优点是插入和删除节点的速度较快，但查找节点的速度较慢。单向链表的数据结构如下所示：

cstruct ListNode {
    int val;  // 节点的值
    struct ListNode *next;  // 指向下一个节点的指针
};
1.2 双向链表（Doubly Linked List）

双向链表是在单向链表的基础上增加了一个指向前一个节点的指针。这样一来，双向链表可以从前往后遍历，也可以从后往前遍历，但相应地，插入和删除节点的操作会稍微复杂一些。双向链表的数据结构如下所示：

cstruct ListNode {
    int val;  // 节点的值
    struct ListNode *prev;  // 指向前一个节点的指针
    struct ListNode *next;  // 指向下一个节点的指针
};
1.3 循环链表（Circular Linked List）

循环链表是一种特殊的链表类型，它的最后一个节点指向第一个节点（或者说，第一个节点指向最后一个节点）。这样一来，循环链表可以无限循环下去，因此常用于循环队列等数据结构中。循环链表的数据结构和单向链表或双向链表类似，只是最后一个节点的指针指向第一个节点。

本教程主要演示的是单向链表的使用。

2. 节点的定义

首先，我们需要定义链表的节点结构。每个节点包含一个数据元素和一个指向下一个节点的指针。在C语言中，我们可以使用结构体来定义节点。

typedef struct Node {
    int data;           // 数据元素
    struct Node* next;  // 指向下一个节点的指针
} Node;

3. 创建和初始化链表

下面是一个函数，用于创建并初始化一个空链表。

Node* createLinkedList() {
    return NULL;  // 返回空链表
}

4. 插入节点

接下来，我们需要实现在链表中插入新节点的功能。我们可以根据需要在链表的开头、末尾或中间插入新节点。

// 插入节点到链表开头
Node *insertAtBeginning(Node *head, int data) {
    // 创建新节点
	Node *newNode = (Node*)malloc(sizeof(Node));  
    // 设置节点数据
	newNode->data = data;  
	// 将新节点指向原来的头节点                        
    newNode->next = head; 
	// 返回新的链表头节点                         
    return newNode;                                
}

// 插入节点到链表末尾
Node *insertAtEnd(Node *head, int data) {
    // 创建新节点
	Node *newNode = (Node*)malloc(sizeof(Node)); 
    newNode->data = data;
    // 将新节点的下一个节点指针设置为NULL
    newNode->next = NULL;                          
	// 如果链表为空，将新节点作为链表的唯一节点
    if (head == NULL) {
        return newNode;  
    }

    Node* current = head;

    // 遍历链表直到达到最后一个节点
    while (current->next != NULL) {
        current = current->next;
    }
	// 将新节点插入到已有链表的末尾
    current->next = newNode;  
    // 返回原来的头节点
    return head;              
}

// 在指定位置插入节点
Node* insertAtPosition(Node* head, int data, int position) {
    // 创建新节点
	Node* newNode = (Node*)malloc(sizeof(Node));  
    newNode->data = data;
	 // 如果插入位置为0，则将新节点作为新的头节点
    if (position == 0) {
        newNode->next = head;
        return newNode; 
    }
    Node* current = head;

    // 找到插入位置的前一个节点
    for (int i = 0; i < position - 1; i++) {
        if (current == NULL) {
            printf("位置超出链表存储范围。\n");
            return head;
        }
        current = current->next;
    }
	// 将新节点的next指针指向当前位置的节点
    newNode->next = current->next;  
    // 将当前位置的节点指向新节点
	current->next = newNode;        
    // 返回原来的头节点
	return head;                    
}

5. 删除节点

我们也可以从链表中删除节点。下面是一些用于删除节点的函数示例。

// 从链表开头删除节点
Node* deleteAtBeginning(Node* head) {
    if (head == NULL) {
        printf("链表为空");
        return NULL;
    }

    Node* temp = head;
    // 更新头节点
    head = head->next;  
    // 释放删除节点的内存
    free(temp);  
	// 返回新的头节点       
    return head;        
}

// 从链表末尾删除节点
Node* deleteAtEnd(Node* head) {
    if (head == NULL) {
        printf("链表为空！！！\n");
        return NULL;
    }
	// 如果只有一个节点，直接删除
    if (head->next == NULL) {
        free(head);   
        return NULL;
    }

    Node *current = head, *prev;
    // 找到倒数第二个节点
    while (current->next != NULL) {
        prev = current;
        current = current->next;
    }
	//将倒数第二个节点的next指针设置为NULL，删除最后一个节点
    prev->next = NULL;  
    // 释放删除节点的内存
	free(current);      
    // 返回原来的头节点
	return head;        
}

// 根据数据值删除节点
Node* deleteByValue(Node* head, int data) {
    if (head == NULL) {
        printf("链表为空！！！\n");
        return NULL;
    }
    Node *current = head, *prev;
    // 遍历链表找到要删除的节点
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) {
        printf("数据不存在！！！\n");
        return head;
    }

    if (current == head) {
        //如果删除节点是头节点，则更新头节点
		head = head->next;  
    } else {
    	//将前一个节点的next指针跳过删除节点
        prev->next = current->next; 
    }
    free(current);// 释放删除节点的内存
    return head;
}

6. 打印链表

为了验证链表的操作，我们可以编写一个函数来打印链表的所有节点。

//打印链表数据 
void printList(Node* head) {
    Node* current = head;
    printf("链表所存数据: ");
	//表头为空，结束循环 
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

7. 测试代码

我们可以编写一段测试代码来验证我们的链表代码：

//主函数 
int main() {
	//创建链表 
    Node* head = createLinkedList();
    printf("链表已经创建完成，可以正常使用！！！\n");
	while(true){
		printf("1、添加新的数据到链表头。\n"); 
		printf("2、添加新的数据到链表尾。\n");
		printf("3、添加新的数据到固定位置。\n");
		printf("4、删除链表头的数据。\n");
		printf("5、删除链表尾的数据。\n");
		printf("6、删除指定数据。\n");
		printf("7、退出程序。\n");
		printf("请输入你的选择：");
		int ch;
		bool flag=false;
		scanf("%d",&ch);
		system("cls");
		switch(ch){
			case 1:
				int insertN;
				printf("请输入需要插入的数据：");
				scanf("%d",&insertN); 
				head = insertAtBeginning(head, insertN);
				break;
			case 2:
				int insertEndN;
				printf("请输入需要插入的数据：");
				scanf("%d",&insertEndN);
				head = insertAtEnd(head, insertEndN);
				break;
			case 3:
				int insertPosN,pos;
				printf("请输入需要插入的数据和位置：");
				scanf("%d %d",&insertPosN,&pos);
				head = insertAtPosition(head, insertPosN, pos-1);
				break;
			case 4:
				head = deleteAtBeginning(head);
				break;
			case 5:
				head = deleteAtEnd(head);
				break;
			case 6:
				int delN;
				printf("请输入需要删除的数据：");
				scanf("%d",&delN); 
				head = deleteByValue(head, delN);
				break;
			case 7:printf("程序结束，欢迎使用。\n");exit(0);
			default:
				printf("您的输入有误，请检查后重新输入！\n");
				flag=true;
				break;
		}
		if(!flag){
			printf("****-----------------------------****\n");
			printList(head);
			printf("****-----------------------------****\n\n");
		}
		getchar();
	}
    return 0;
}

8. 总结

恭喜你！你已经完成了C语言实现链表的教程。链表是一种非常有用的数据结构，可以在运行时动态管理数据。通过学习链表的实现，您可以对如何操作和管理数据有更深入的了解。希望本教程对你有所帮助，谢谢！

9. 完整代码

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;           // 数据元素
    struct Node *next;  // 指向下一个节点的指针
} Node;

//创建并初始化链表
Node *createLinkedList() {
    return NULL;  // 返回空链表
}

// 插入节点到链表开头
Node *insertAtBeginning(Node *head, int data) {
    // 创建新节点
	Node *newNode = (Node*)malloc(sizeof(Node));  
    // 设置节点数据
	newNode->data = data;  
	// 将新节点指向原来的头节点                        
    newNode->next = head; 
	// 返回新的链表头节点                         
    return newNode;                                
}

// 插入节点到链表末尾
Node *insertAtEnd(Node *head, int data) {
    // 创建新节点
	Node *newNode = (Node*)malloc(sizeof(Node)); 
    newNode->data = data;
    // 将新节点的下一个节点指针设置为NULL
    newNode->next = NULL;                          
	// 如果链表为空，将新节点作为链表的唯一节点
    if (head == NULL) {
        return newNode;  
    }

    Node* current = head;

    // 遍历链表直到达到最后一个节点
    while (current->next != NULL) {
        current = current->next;
    }
	// 将新节点插入到已有链表的末尾
    current->next = newNode;  
    // 返回原来的头节点
    return head;              
}

// 在指定位置插入节点
Node* insertAtPosition(Node* head, int data, int position) {
    // 创建新节点
	Node* newNode = (Node*)malloc(sizeof(Node));  
    newNode->data = data;
	 // 如果插入位置为0，则将新节点作为新的头节点
    if (position == 0) {
        newNode->next = head;
        return newNode; 
    }
    Node* current = head;

    // 找到插入位置的前一个节点
    for (int i = 0; i < position - 1; i++) {
        if (current == NULL) {
            printf("位置超出链表存储范围。\n");
            return head;
        }
        current = current->next;
    }
	// 将新节点的next指针指向当前位置的节点
    newNode->next = current->next;  
    // 将当前位置的节点指向新节点
	current->next = newNode;        
    // 返回原来的头节点
	return head;                    
}

// 从链表开头删除节点
Node* deleteAtBeginning(Node* head) {
    if (head == NULL) {
        printf("链表为空");
        return NULL;
    }

    Node* temp = head;
    // 更新头节点
    head = head->next;  
    // 释放删除节点的内存
    free(temp);  
	// 返回新的头节点       
    return head;        
}

// 从链表末尾删除节点
Node* deleteAtEnd(Node* head) {
    if (head == NULL) {
        printf("链表为空！！！\n");
        return NULL;
    }
	// 如果只有一个节点，直接删除
    if (head->next == NULL) {
        free(head);   
        return NULL;
    }

    Node *current = head, *prev;
    // 找到倒数第二个节点
    while (current->next != NULL) {
        prev = current;
        current = current->next;
    }
	//将倒数第二个节点的next指针设置为NULL，删除最后一个节点
    prev->next = NULL;  
    // 释放删除节点的内存
	free(current);      
    // 返回原来的头节点
	return head;        
}

// 根据数据值删除节点
Node* deleteByValue(Node* head, int data) {
    if (head == NULL) {
        printf("链表为空！！！\n");
        return NULL;
    }
    Node *current = head, *prev;
    // 遍历链表找到要删除的节点
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) {
        printf("数据不存在！！！\n");
        return head;
    }

    if (current == head) {
        //如果删除节点是头节点，则更新头节点
		head = head->next;  
    } else {
    	//将前一个节点的next指针跳过删除节点
        prev->next = current->next; 
    }
    free(current);// 释放删除节点的内存
    return head;
}
//打印链表数据 
void printList(Node* head) {
    Node* current = head;
    printf("链表所存数据: ");
	//表头为空，结束循环 
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

//主函数 
int main() {
	//创建链表 
    Node* head = createLinkedList();
    printf("链表已经创建完成，可以正常使用！！！\n");
	while(true){
		printf("1、添加新的数据到链表头。\n"); 
		printf("2、添加新的数据到链表尾。\n");
		printf("3、添加新的数据到固定位置。\n");
		printf("4、删除链表头的数据。\n");
		printf("5、删除链表尾的数据。\n");
		printf("6、删除指定数据。\n");
		printf("7、退出程序。\n");
		printf("请输入你的选择：");
		int ch;
		bool flag=false;
		scanf("%d",&ch);
		system("cls");
		switch(ch){
			case 1:
				int insertN;
				printf("请输入需要插入的数据：");
				scanf("%d",&insertN); 
				head = insertAtBeginning(head, insertN);
				break;
			case 2:
				int insertEndN;
				printf("请输入需要插入的数据：");
				scanf("%d",&insertEndN);
				head = insertAtEnd(head, insertEndN);
				break;
			case 3:
				int insertPosN,pos;
				printf("请输入需要插入的数据和位置：");
				scanf("%d %d",&insertPosN,&pos);
				head = insertAtPosition(head, insertPosN, pos-1);
				break;
			case 4:
				head = deleteAtBeginning(head);
				break;
			case 5:
				head = deleteAtEnd(head);
				break;
			case 6:
				int delN;
				printf("请输入需要删除的数据：");
				scanf("%d",&delN); 
				head = deleteByValue(head, delN);
				break;
			case 7:printf("程序结束，欢迎使用。\n");exit(0);
			default:
				printf("您的输入有误，请检查后重新输入！\n");
				flag=true;
				break;
		}
		if(!flag){
			printf("****-----------------------------****\n");
			printList(head);
			printf("****-----------------------------****\n\n");
		}
		getchar();
	}
    return 0;
}

以上就是C语言实现链表的详细教程。希望对您有所帮助！如果您还有其他问题，请随时提问。文章来源地址https://www.toymoban.com/news/detail-581256.html

到了这里，关于C语言/C++实现链表的详细教程的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构_链表_单向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

    数据结构_链表_单向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

    版本: 2024年4月25日 V1.0 发布于博客园 目录 目录 单向循环链表公式 初始化单向循环链表 构建单向循环链表结点 创建一个空链表（仅头结点） 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 CircularLinkedLis

    2024年04月25日
    浏览(51)
  • 【数据结构】—C语言实现双向链表（超详细!）

    【数据结构】—C语言实现双向链表（超详细!）

                                          食用指南：本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了：C语言                                     🍀 双向链表 前 置知识 ：单链表      

    2024年02月13日
    浏览(51)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N) 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后

    2024年02月21日
    浏览(51)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样，但本文并未采用 #define 定义容量的写法，这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟，后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中，重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(70)
  • 【数据结构】双向链表的实现

    【数据结构】双向链表的实现

    我要扼住命运的咽喉，他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表，创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(47)
  • 数据结构——双向链表的实现

    数据结构——双向链表的实现

    注意： 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点，实际为“ 哨兵位 ”，哨兵位节点不存储任何有效元素，只

    2024年02月06日
    浏览(48)
  • 【（数据结构）— 双向链表的实现】

    【（数据结构）— 双向链表的实现】

    注意： 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念，实际前面的在单链表阶段称呼不严 谨，但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点，实际为 “哨兵位” ，哨兵位节点不存储任何有效元素，只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(46)

  • 数据结构——链表的实现（Java版）

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 （1）在头部添加 （2）在尾部添加 （3）在索引位置添加 （4）对头插法和尾插法代码进行简化（调用任意位置添加的方法） 7.打印链表（遍历，重写toString方

    2024年01月23日
    浏览(50)
  • 【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题： 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表，每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(87)
  • 数据结构：双向链表的实现(C实现)

    数据结构：双向链表的实现(C实现)

    个人主页 ： 个人主页 个人专栏 ： 《数据结构》 《C语言》 本篇博客，将要实现的是 带头双向循环链表 ，该结构实现尾插，尾删只需要O(1)的时间复杂度。 其结构如下所示： 既然要实现的链表是双向循环的，那么对于指针域，我们就需要 指向节点上一个的指针 和 指向节点

    2024年02月14日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包