C++ STL之list双向链表容器方式

目录

• 1.list技术原理
• 2.应用基础
• 2.1元素的遍历访问
• 2.2元素的插入
• 2.3元素的反向遍历和删除
• 2.4list的排序与归并
• 总结

不同于采用线性表顺序存储结构的vector和deque容器，list双向链表中任一位置的元素查找、插入和删除，都具有高效的常数阶算法时间复杂度O(1)。

1.list技术原理

为了支持前向和反向访问list容器的元素，list采用双向循环的链表结构组织数据元素，链表的每个节点包括指向前驱的指针、实际数据和指向后继的指针等数据域。

list的前向链，由头节点→第1个节点→第2个节点→…第n个节点→头节点构成循环。

list的反向链，则由第n个节点→第n-1个节点→…→头节点→第n个节点构成循环。n为list的节点个数，整个链表的存储位置由头指针指出，它指向头节点。

2.应用基础

list对象的创建，初始化赋值方法与vector相同，jslist的交换与deque相同，这里直接跳过。

2.1元素的遍历访问

由于链表中的数据需要一个个元素进行遍历，因此，list元素的遍历只使用迭代器的方式进行。

上代码：

#include <QCoreApplication>
#include <IOStream>
#include <list>
using namespace std;
struct Student{
    char *name;
    int age;
    char *city;
    char *tel;
};
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    Student s[] = {
        {"符符",18,"上海市","156624"},
        {"介介",20,"北京市","152534"},
        {"贝贝",25,"深圳市","453545"},
    };
    //将数据插入链表
    list<Student> l;
    l.push_back(s[0]);
    l.push_back(s[1]);
    l.push_back(s[2]);
    //遍历打印链表元素
    list<Student>::iterator i,iend;
    iend=l.end();
    cout << "姓名 年龄 城市 电话" << endl;
    cout << "----------------------------" << endl;
    for(i=l.begin();i!=iend;i++)
    {
        cout << (*i).name << " ";
        cout << (*i).age << " ";
        cout << (*i).city << " ";
        cout << (*i).tel << " " << endl;
    }
    cout << "----------------------------" << endl;
    return a.exec();
}

运行结果：

2.2元素的插入

由于list链表元素的插入不需要对其他元素进行移位拷贝，除了push_back函数在尾部添加元素外，list还提供了在链首插入元素的push_front函数和在任意迭代器位置的插入insert()函数。

#include <QCoreApplication>
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    list<int> l;
    l.push_back(6);
    l.push_back(8);
    l.push_back(9);
    list<int>::iterator i,iend;
    i=l.begin();
    i++;
    l.insert(i,7);    //在6的后面插入7
    l.push_front(5);     //在链首插入5
    iend=l.end();
    for(i=l.begin();i!=iend;i++)
    {
        cout << *i << ' ';
    }
    return a.exec();
}

输出结果：

2.3元素的反向遍历和删除

由于list容器的迭代器具有"–"操作，因此也定义了反向迭代器。用反向迭代器来进行链表的遍历。

#include <QCoreApplication>
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    list<int> l;
    l.push_back(5);
    l.push_back(6);
    l.push_back(7);
    l.push_back(8);
    l.push_back(9);
    l.push_back(9);
    l.push_back(9);
    l.push_back(10);
    list<int>::reverse_iterator ri,rend;
    rend=l.rend();
    cout << "反向遍历python：";
    for(ri=l.rbegin();ri!=rend;ri++)
    {
        cout << *ri << " ";
    }
    cout << endl;
    list<int>::iterator i,iend;
    i=l.begin();
    i++;
    l.erase(i);     //删除6
    l.pop_back();   //删除末元素10
    l.pop_front();   //删除首元素5
    l.remove(9);     //删除所有值为9的元素
    iend=l.end();
    for(i=l.begin();i!=iend;i++)
    {
        cout << *i << " ";
    }
    cout << endl;
    return a.exec();
}

运行结果：

2.4list的排序与归并

list 提供的void sort函数，将链表中的元素按"<"关系进行排序，较小的排在前面。

list链表元素的排序，是将list链表分割成若干部分进行子排序，然后通过归并处理，实现list的所有元素的排序。为此，list容器提供了splice和merge的归并函数。

void splice(iterator posit编程客栈ion,list& x) //将x的链表归并到当前list链表的position之前，list对象x将被清空
void splice(iterator position,list&,iterator i)//将一个list的迭代器i值所指的元素，归并到当前list链表中，并将被归并的元素从原链表中删除
void merge(list& x)//将list对象x的链表归并到当前list链表中，并清空x的链表。从merge函数的源码可知，只有当前的list链表和x均预先按元素的"<“关系排好序，merge函数才有意义，归并后的链表也是按”<"关系排列。

上代码：

#include <QCoreApplication>
#include <iostream>
#include <list>
using namespace std;
void print(list<int>& l)
{
    list<int>::iterator i,iend;
    iend=l.end();
    for(i=l.begin();i!=iend;i++)
    {
        cout << *i << " ";
    }
    cout<< endl;
}
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    list<int> l;
    l.push_back(13);
    l.push_www.devze.comback(6);
    l.push_back(7);
    l.push_back(15);
    l.push_back(9);
    l.push_back(8);
    l.push_back(9);
    l.push_back(10);
    cout << "未排序前：";
    print(l);
    l.sort();   //从小到大排序
    cout << "排序后：";
    print(l);
    list<int> carry;
    carry.splice(carry.begin(),l,l.begin());   //将l的第一个元素归并到carry的首元素，并将l的首元素删除
    cout << "carry的链表元素为：";
    print(carry);
    cout << "l的链表元素为：";
    print(l);
    list<int> x;
    x.push_back(30);
    x.push_back(31);
    x.push_back(32);
    l.merge(x);                      //将x链表里的元素归并到l,并清空x
    cout << "x的链表元素为：";
    print(x);
    cout &lhttp://www.devze.comt;< "l的元素为：";
    print(l);
    return a.exec();
}

运行结果：

总结

list双向链表容器采用双向链表的数据结构来存储数据，可高效查找、插入和删除容器元素。

list提供的splice和merge归并函数，可用于链表的元素排序。

以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程客栈(www.devze.com)。