【数据结构】STL实现链表

Dear 丶 2022-11-15 11:52 316阅读 0赞

## 前言 ##

在本教程中，我所介绍的用法或接口可能并不完整，但是在日常的做题学习中已经足够用了。

所以，如有额外需求可私信，我会及时发布新的文章补充相关知识点！

## 1. 什么是STL？ ##

百度百科中给出的解释是：标准模板库（Standard Template Library，STL）是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。虽说它主要表出现到C++中，但在被引入C++之前该技术就已经存在了很长时间。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL实际上就是C++的一个数据结构库，相比于日后的算法设计，我们的重心不能只放在底层数据结构的设计上。对于一些较为基础的、底层的数据结构，使用STL能够大大提高我们的编码效率和编码体验。

## 2. 如何使用 ##

STL标准库只能在C++项目中使用，C语言是不支持的，所以我们需要开C++项目，并且引头文件：

#include<list>

或者，可以直接引万能头文件：

#include<bits/stdc++.h>

头文件引用完毕后就可以开始使用STL进行链表的编码了。

## 3. 构造链表 ##

首先我们需要定义一个空的容器：

list<ElementType> l;

前面的`list`代表l变量为链表（其实是双链表），该链表内所有节点的数据类型为ElementType，需要我们自己去规定。

有了列表对象之后，我们就可以开始一系列的接口介绍了。

## 4. 新增、插入和删除节点 ##

插入和删除也分不同情况，这里将根据操作的不同分类介绍。

### 4.1 新增节点 ###

在创建链表时，有两种构造方法，一种是头插法，一种是尾插法。在STL的接口定义中如下：

l.push_back(e);
    l.push_front(e);

其中，e表示的是你想要往当前链表中插入的节点的元素值。

`push_back()`和`push_front()`其实也是语义化的命名，它们分别代表在当前链表的尾部和头部插入新的节点。

### 4.2 删除节点 ###

新增有头插法和尾插法两种，那么删除节点自然也对应两种方法：尾部删除与头部删除。接口定义如下：

l.pop_back();
    l.pop_front();

注意这两个方法不需要向方法内传入参数。

`pop_back()`和`pop_front()`则分别对应删除尾部元素和删除头部元素，当然只是删除一个节点。

当然，任意位置的删除也是支持的：

l.earse(pos);

这里的pos参数即为你想要删除的节点的位置，也可以理解为下标

或者想删除某个特定值的节点：

l.remove(e);

`e`就是你想删除的值。

### 4.3 插入节点 ###

既然是插入，那么肯定是可以在任意位置上插入新的节点

l.insert(pos, e);

需要传入两个参数，同样的，pos参数表示你想要插入的位置，e则代表你想要插入的新节点的元素值。

## 5. 遍历链表对象 ##

向链表对象中插入元素后，我们就可以对其进行遍历了。

注意，我们在遍历链表对象的时候不是简单的对下标进行操作，因为链表节点中其实没有定义下标这个属性，所以我们需要一个工具叫**迭代器**（iterator）。

对迭代器的定义如下：

list<ElementType>iterator:: iter;

注意，每种STL的容器都有其独特的迭代器，一定不要选错了。`ElementType`是待遍历链表的元素的数据类型，iterator则是定义了接下来的变量`iter`为迭代器类型，后面的`::`是C++的命名空间，不懂的可以移步百度，本文章中不做出说明讲解。

遍历操作如下：

for(iter=l.begin();iter!=l.end();iter++){
        
    	cout<<*iter<<" ";
    }

同样采用for循环来进行遍历，为迭代器变量`iter`赋初始值为`l.begin()`，即当前链表l的第一个节点（非头节点）；迭代结束的标志显然是迭代到链表的末尾，用`l.end()`来获取链表的尾节点；步长设置为1。

注意，这里输出当前节点元素值的操作为`* + iter`，你可以将它理解为指针，取出其中的元素值。

## 6. 顺序问题 ##

既然涉及到容器，难免会遇到排序问题。其实链表的排序和数组很像，只不过区别在与内存空间的连续与否。同样，STL-list中内置了相关的接口：

l.sort();
    l.reverse();

`l.sort()`方法就是排序，对当前链表中所有节点的元素值进行排序，并用排序后的结果**取代**之前的链表。

`l.reverse()`方法则是对当前链表进行**逆置**，即倒序。

对于某些特定场合，合理使用这些方法会较为方便。

## 7. 链表合并 ##

如果想将两个，甚至多个链表合并到一个链表中，则可以：

l.merge(list<ElementType>);

传入`merge()`方法中的参数即为要合并到l中的链表，此时的数据类型不必一致；若一致，且合并前两链表均有序，则合并之后的结果仍然有序。

发表评论取消回复

表情：

评论列表（有 0 条评论，316人围观）

还没有评论，来说两句吧...

相关阅读

相关 STL底层数据结构实现

C++ STL 的实现： 1.vector 底层数据结构为数组，支持快速随机访问 2.list 底层数据结构为双向链表，支持快速增删 3.deque 底层数据结构为一个

╰+哭是因爲堅強的太久メ/ 2024年02月19日 13:28/ 0 赞/ 43 阅读

相关【数据结构】STL实现队列

queue就是我们熟悉的队列，是一种遵从先进先出(FIFO)原则的数据结构，本文将介绍相关的类方法。一、头文件的引用想使用STL的queue类容器，我们需要首先引用

谁践踏了优雅/ 2023年07月19日 12:05/ 0 赞/ 1 阅读

相关【数据结构】STL实现栈

不知道你们有没有这种感觉：刷题时固定的代码要重复写很多遍，浪费时间；稍不注意一点错误就可能会被学校的OJ墙掉，来个WA或者RE。太痛苦了QAQ 那为什么不试试神奇的STL

向右看齐/ 2023年07月18日 02:45/ 0 赞/ 1 阅读

相关【数据结构】STL实现链表

前言在本教程中，我所介绍的用法或接口可能并不完整，但是在日常的做题学习中已经足够用了。所以，如有额外需求可私信，我会及时发布新的文章补充相关知识点！ 1. 什么

Dear 丶/ 2022年11月15日 11:52/ 0 赞/ 317 阅读

相关数据结构:JavaScript实现链表

链表是由一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继。数组元素靠他们的位置进行引用，链表元素则是靠互相之间的关系进行引用。一.一个基本的链表

冷不防/ 2022年08月20日 04:23/ 0 赞/ 193 阅读

相关数据结构-链表的实现

include<stdio.h> include<stdlib.h> typedef int Elemtype; typedef struct

野性酷女/ 2022年06月05日 22:25/ 0 赞/ 208 阅读

相关数据结构-链表结构

\include<stdio.h> \include<stdlib.h> \include<conio.h> //定义一个结构体 struct Student\

超、凢脫俗/ 2022年06月04日 08:25/ 0 赞/ 292 阅读

相关数据结构-链表实现（单链表，双链表，类实现）

1.单链表 1）单的意思就是说只有一个方向，所以只能往一个方向增加节点。 2）也因为单（身）所以处理起来很寂寞，注意几点吧： A）创建和遍历需要一个头节点（不含数据）

桃扇骨/ 2022年05月28日 12:54/ 0 赞/ 260 阅读

相关数据结构与算法——栈的实现（数组，链表，STL实现）

概念：栈（stack）是限定只能在表的一段进行插入或删除操作的线性表。在表中允许插入和删除的一端称为“栈顶（top）”，不允许插入和删除的叫“栈底（bottom）”。用四

柔光的暖阳◎/ 2022年02月27日 23:58/ 0 赞/ 260 阅读

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

双向链表(Double Linked List) 由两个指针域构成，分别指向前驱、后驱。如下图。 ![在这里插入图片描述][2020031420072497.png_

叁歲伎倆/ 2021年09月21日 04:34/ 0 赞/ 382 阅读