c++对链表的操作（一）

àì夳堔傛蜴生んèń 2023-07-04 06:22 26阅读 0赞

## 初识链表 ##

很多初学者觉得链表和数组一样都是顺序存储结构，同样每个数据都有自己的指针，它们到底有什么区别？  
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若干个指针。  
链表的最大优势在于数据处理的速度和空间利用率要远高于数组。  
数组首先需要占用一块连续空间，而且不可以实现动态大小，往往会造成空间浪费。而链表由指针直接指向地址，可以把内存分散开，充分利用碎片化的空间。  
从处理数据的速度上时间复杂度来说，数组只能通过顺次指针访问，查询效率低，链表则可以通过头位指针，对任意存储段进行修改、删除和添加。

## 链表的c++实现 ##

![链表基本结构][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA_size_16_color_FFFFFF_t_70]

struct ListNoed
    { 
    	double value;
    	ListNoed* next;
    
    };

ListNode 就是要存储在链表中的结点的类型，结构成员 value 是结点的数据部分，而另一个结构成员 next 则被声明为 ListNode 的指针，它是指向下一个结点的后继指针。

ListNoed* head = nullptr;

将head指向链表头，插入一个新数据

head = new ListNoed;
    	head->value = 1;
    	head->next = nullptr;

创建一个新结点，在其中存储2的值，并将其作为链表中的第二个结点。可以使用第二个指针来指向新分配的结点

ListNoed* secondPtr = new ListNoed;
    	secondPtr->value = 2;
    	secondPtr->next = nullptr;
    	head->next = secondPtr;

最后输出一下链表的两个节点检查一下是否创建成功

cout << "First " << head->value << endl;
    	cout << "Second " << head->next->value << endl;

结果如下  
![执行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA_size_16_color_FFFFFF_t_70 1]这就是链表的创建和插入操作。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200209095648278.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200209101857344.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0VJRG9yYWRvbA==,size_16,color_FFFFFF,t_70