基于内存指针的链表

1. 基于数组下标的链表结构

struct Node{
    int data;
    int L,R; // L 和 R 分别指向链表的前一个（左边）和下一个（右边）的元素，它们是 int 类型，存放的是数组的下标
} a[10001];

2. 基于指针跳转的链表结构

struct Node{
    int data;
    Node *pre, *next; // pre 和 next 分别指向链表的前一个（左边）和下一个（右边）的元素，它们是 Node 指针，也就是说存放的是内存地址，更准确说， next 和 pre 指向一个 Node 类型的数据
};

3. 为什么要更为抽象的指针结构

1. 大量的程序阅读题是基于内存指针来写的，如果不学这个结构就看不懂这些代码
2. 基于指针的链表结构更加体现链表能动态扩展的特性。我们说数组的大小是不可变的，链表的大小是可变的。如果基于上面的第一个代码，其实是体会不到为什么链表的大小可以扩展。

4. 详细代码

4.1 链表的头和顺序访问

数组是支持随机访问的，例如上面的第一款代码中，定义了 a 数组， a[5] 就是第 5 个数组元素，我们可以通过 [] 运算符可以随机访问 a[4]、a[13]、a[7].....

链表是不支持随机访问的，针对上面的第二款代码，我们没办法直接找到链表中第 5 个数组元素。链表的访问必须是从头开始一个一个去访问（称为顺序访问）。

Node *head;

Node* get_node(int idx){
    // 访问链表中第 idx 个元素，返回该元素的指针
    Node *ptr=head;
    for(int i=1;i<idx;i++)
        ptr = ptr->next;
    return ptr;
}

4.2 动态扩展一个元素

通过 new 命令可以动态申请一块内存，初始化为一个类，返回这个对象的内存地址。这个内存地址一般会赋值给某个指针变量。

Node *ptr = new Node(); // new 命令返回新对象的内存地址，赋值给 ptr 指针。

随后，可以把 ptr 所指向的对象实力插入到链表当中。

4.3 头插法

头插法是链表最重要、最常见的插入手段。在很多场合，我们并不关心链表中数据元素的先后顺序，谁在前谁在后都不重要，我们只是想用链表的动态扩展功能，这时候就会选择头插法。

void insert_head(Node *ptr){
    ptr->next = head;
    head->pre = ptr;
    head = ptr;
}

==基于头插法，越是后面插入的元素，越是靠近链表的头部。==这是理论考试常考的知识点。

4.4 在 s 元素后插入元素 ptr

这里说的 s 和 ptr 都是指针类型

void insert_after(Node *s, Node *ptr){
    ptr->pre = s;
    if(s->next){
        s->next->pre = ptr;
        ptr->next = s->next;
    }
    s->next = ptr; // s->next 必须最后才更新，否则会丢失数据的
}

4.5 删除一个元素

void remove(Node *ptr){
    if(ptr==head){
        head = head->next;
    }
    else{
        ptr->pre->next = ptr->next; // 因为 ptr 不是 head，所以 ptr->pre 一定不为 0
        if(ptr->next) ptr->next->pre = ptr->pre;
    }
    delete ptr; // 根据 ptr 的值（内存地址）删除对象，释放内存
}

优缺点分析

基于 new 命令动态申请内存，并把新的节点插入到链表中，这个方法在现实世界中被广泛应用。道理很简单，设计程序的人在大多数情况下是不会知道将来系统会面对多大的数据的。如果程序只能允许 1000000 个数据元素，那么一旦超过 1000000，程序就内存越界而崩溃了。只有信息学竞赛题才会在每条题跟你交待清楚 n、m 的范围。当现实世界里这个 n 和 m 不确定，就一定要进行动态的内存管理。

但是，每当有新的数据输入，就要执行一次 new 命令，是很花时间的，对于信息学竞赛的编程题，千万不要这样做，会很吃亏。题目都已清清楚楚说明了 n 和 m 的最大值了，那么我们就定义一个足够大的数组。

为了应对理论题，为了看明白别人写的程序，我们必须要学会这种写法。