问题标题: 到底什么是链表

讲义内容：

二、链表

1. 基本概念

• 链表是一种线**表
• 链表中，除了第一个元素没有前驱，最后一个元素没有后继以外，其它每一个元素都有唯一的前驱和后继。
  

2. 线**表

链表和数组都属于线**表，区别是

• 数组在计算机中是连续分配内存的
• 链表在计算机中不是连续分配内存
  

3. 链表元素的组成

链表中的每一个元素至少由两部分组成，C语言中一般使用结构体实现：

• 存放值的数据域
• 存放下一个元素地址的地址域
• 地址相当于变量在计算机内存里的“门牌号码

4. 链表首尾元素

链表中第一个元素没有前驱，我们使用一个头指针指向它的位置，头指针是一个专门存储地址的变量。

链表中最后一个元素没有后继，我们在它的地址域放入一个
空地址，NULL

5. 链表的特点

链表由于在内存中不是连续存储的，所以：

• 不能直接计算出某一个元素的地址，所以不支持随机访问第i个元素。每次查询某个元素需要遍历整个链表，时间复杂度为O(n)。
• 插入和删除元素不需要移动后面的元素，只需要修改一些元素的地址域，时间复杂度为O(1)。但是查找到插入和删除的位置需要花时间。

6. 链表的插入操作

链表中，假设我们要在a和b之间插入一个p，要分2步完成：

1. 将p的地址域赋值为b的地址
   
2. 修改a的地址域为p的地址
   

注意：两步的顺序不能颠倒

7. 链表的删除操作

链表中，假设我们要把a和b之间的结点p删除，需要将a的地址
域赋值为p的地址域

通常还跟着一步：删除结点p，释放点p的内存空间。

8. 双向链表

有的链表中，每个元素不仅有存储后继的地址域，还有存储其前驱的地址域。这样的链表叫双向链表。

9. 循环链表

有的链表中，最后一个元素的后继不是NULL，而是链表的第一个元素。这样的链表叫循环链表。

三、STL中的list

1. STL是什么

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。

2. list（链表）

• list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
• list的底层是双向链表结构，双向链表中每个元素存储在互不相关的**节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. 如何使用list

头文件

#include <list>

定义： List<数据类型> 链表名;

例：

list<int> l1;  //定义一个int型的链表l1
list<double> l2;  //定义一个double型的链表l2
struct point{
    int x,y;
}
list<point> l3;   //定义一个（结构体）point型的链表l3

求链表长度与遍历链表

1. 求链表长度：l.size()
2. 遍历链表
   1）定义一个迭代器it，指向链表开头（l.begin()）

list<int> l; list<int>::iterator it=l.begin();

       2）当迭代器没有到达链表尾部（l.end()），迭代器it往后移动

while(it!=l.end()) it++; //注意不能写it<l.end()

      3) 输出迭代器指向的元素

cout<<*it<<' ';

迭代器it指向的是元素地址，*it则是该地址对应的元素。

向链表中插入新元素

1. 向链表尾部插入新元素e：

l.push_back(e);

2. 向链表某个元素前插入新元素，例如在值为x的元素前插入一个值为e的新元素：

list<int> l; list<int>::iterator=l.begin(); while(it!=l.end() && *it!=x) it++; //先找到值为x的元素的位置 l.insert(it,e); //在该元素之前插入值为e的元素，此函数的返回值是一个指向新元素e的迭代器

从链表中删除某个元素

假设从链表中删除一个值为e的元素：

list<int> l; list<int>::iterator=l.begin(); while(it!=l.end() && *it!=e) it++; //先找到值为e的元素的位置 l.erase(it); //删除该元素，此函数会返回指向被删除元素后一个元素的迭代器