数据结构 - 线性表笔记

This post is not yet available in English. Showing the original version.

February 26, 2025

数据结构-线性表笔记

普通的数组与出入栈在STL很好用，但是涉及链表进行指针操作较为薄弱，因此记录一下链表的操作。

链表的创建

单向链表的创建

struct Node // 创建单向链表
{
    int data; //数据
    Node *next; //指向下一元素
};

单向链表的操作的时间复杂度，插入和删除的时间复杂度为O(n)(n为链表长度)，查找的时间复杂度为O(n)(n为链表长度)

双向链表的创建

struct Node // 创建双向链表
{
    int data;
    Node *next; // 指向下一元素
    Node *prev;// 指向上一元素
};

双向链表的操作的时间复杂度与单向链表类似，只是在插入和删除时需要更改指针的指向，所以时间复杂度为O(n)(n为链表长度)

块状链表,循环链表的创建

都与基本链表的创建有关。

循环链表将末尾元素的next指针指向首元素，构建循环。

// 循环链表的构建
struct CircularNode {
    int data;
    CircularNode* next;
};
// 在插入数据时候，末尾进行
newNode->next = head;

块状链表是由多个链表拼接，存储的数据（data）是不同链表的指针。
```
// 块状链表的构建
struct Block {
    vector<Node*> nodes;
    Block* next;
    Block* prev;
};
```
双向链表与指针结合，构建连接不同双向链表的块状链表，存储数据的同时，还存储了指向前后块的指针，这样就可以在O(sqrt(n))的时间内找到任意一个元素。使用块状链表，可以减少查找的时间复杂度，为O(sqrt(n))。

链表的基本操作

链表的插入

（这里以单向链表为例)

void insert(Node *&head, int value)
{
    Node *newNode = new Node(); // 创建一个新的结点
    newNode->data = value;    // 赋值
    newNode->next = nullptr;  // 初始化next指针
    if (head == nullptr)
    {
        head = newNode;
    } // 如果链表为空，直接插入
    else
    {
        Node *temp = head;
        while (temp->next != nullptr) // 遍历链表，找到最后一个结点
        {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

逻辑很简单。

先创一个新结点（因为是指针形式的，所以用new形式建立）。
然后给data赋值。
再看看它要插入的地方是不是head，是head就简单，直接把它的next设立为head。

如果是双向链表就再注意一下head的prev改成新结点

不是head的话，直接while找到要插入的位置（这里自己设定while的循环条件），然后改要插入位置的前者next为它的next，然后把前者的next改为它。

如果是双向链表的话注意一下前者的next的prev也要改成它，它的prev改成前者。

  while (temp->id != k)//k为要插入的位置，这里做个示范
        {
            temp = temp->next;
        }
        if (temp->next != nullptr)
        {
            temp->next->prev = newNode;
        }
        newNode->next = temp->next;
       temp->next = newNode;

然后改完了就完事，插入一个结点嘛。

不过这个方法的时间复杂度为O(n)，在进行大数据的遍历的时候和有可能耗时巨大，之后的学习生活中会学习二叉树，哈希表等方法来优化。

链表的结点删除

void deleteData(Node *&head, int value)
{
    Node *temp = head;
    Node *prev = nullptr;
    if (temp != nullptr && temp->data == value)
    {
        head = temp->next;
        delete temp;
        return;
    } // 删除头结点
    while (temp != nullptr && temp->data != value)
    {
        prev = temp;
        temp = temp->next;
    } // 找到要删除的结点，遍历
    if (temp == nullptr)
    {
        return;
    } // 没找到要删除的结点，没有值对应的链表节点
    prev->next = temp->next;
    delete temp;
}

首先最重要的，head的函数引用为&head！因为head很有可能也是删除结点！

否则退出函数后head并没有进行改变操作，将会造成RE即运行时错误。

先建立一个temp结点，给它先变成head结点，这样可以解决head因为是引用形式的不能轻易去改变值的问题，利于后续while循环来查找值。
在写之前要考虑三种情况
1. 链表是空的，那删什么？
2. 链表找不到我要删掉的值，那删什么？
3. 链表要删掉头，那遍历什么？
然后用if来判断一下情况。
- 先考虑如果是链表是空的，那我们就可以什么都不做了。
  
  if (temp == nullptr) return;
- 再想想如果删掉头，那我们就不用遍历了。
```
  if (temp != nullptr && temp->data == value)
    {
        head = temp->next;
        delete temp;
        return;
    }
```
- 然后就可以开始愉快地遍历了。
```
while (temp != nullptr && temp->data != value)
    {
        prev = temp;
        temp = temp->next;
    } // 找到要删除的结点，遍历
```
- 找到的话，我们需要把这个结点的前者连接到下一结点。如果是双向链表很方便，直接temp->prev->next=temp->next了，不需要prev的参与。
  
  但这里是单向链表，我们还是要有一个临时指针指向temp的前者的，也塞进去循环里就可以了，然后进行一样的操作。
```
prev->next = temp->next;
```
- 没找到的话，那我们这个while的操作一直运行，直到temp变成了链表尾部的next，即就是空指针NULL。
  
  那prev指向的结点就是原链表尾部，temp为nullptr的话，那temp就没有next的值。这样的话进行最后一步就会报错，注意这里的内存管理。
  
  这里选择用语句直接包揽1和2情况。
```
 if (temp == nullptr)
    {
        return;
    } 
```
- 这里体现删除的操作的时间复杂度为O(n)。

链表的显示输出

很简单，从头开始while循环输出值即可。

void printList(Node *head)
{
    Node *temp = head;
    while (temp != nullptr)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

也是从头遍历到尾部，时间复杂度为O(n)。

链表的操作实战

实战题目

题目源于洛谷数据结构题单【数据结构1-1】线性表p1160队列安排。

非AC代码

采用基础的遍历来解决问题，在数据较小的时候可以满足结果，而数据较大时候因为O(n^2)的时间复杂度而导致TLE，解决方法见注释。

点击查看代码

#include <iostream>
using namespace std;
//面对大数据来写直接插入排序，时间复杂度为O(n^2)。
//插入排序与删除的优点是不需要额外的空间，缺点是查找时间复杂度较高。
//优化的话可以考虑利用哈希表，查找时间复杂度为O(1)，空间复杂度为O(n)
//另外一种方法是利用二叉搜索树，查找时间复杂度为O(nlogn)，空间复杂度为O(n)
struct node
{
    int id;
    node *prev;
    node *next;
};
void insert(node *&head, int k, int i, bool left);
void deleteValue(node *&head, int id);
void printList(node *head);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n;
    node *head = new node();
    head->id = 1;
    head->next = nullptr;
    head->prev = nullptr;
    // 重整顺序
    for (int i = 1; i < n; i++)
    {
        int k, p;
        cin >> k >> p;
        bool left = (p == 0 ? true : false);
        insert(head, k, i, left);
        // printList(head);
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int id;
        cin >> id;
        deleteValue(head, id);
        // printList(head);
    }
    printList(head);
} // 链表手写数据结构版本
void insert(node *&head, int k, int i, bool left)
{
    node *newNode = new node();
    newNode->id = i + 1;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    node *temp = head;
    if (!left)
    {
        while (temp->id != k)
        {
            temp = temp->next;
        }
        if (temp->next != nullptr)
        {
            temp->next->prev = newNode;
        }
        newNode->next = temp->next;
        temp->next = newNode;
        newNode->prev = temp;
    }
    else
    {
        while (temp->id != k)
        {
            temp = temp->next;
        }
        if (temp->prev == nullptr)
        {
            head = newNode;
        }
        else
        {
            temp->prev->next = newNode;
        }
        newNode->prev = temp->prev;
        temp->prev = newNode;
        newNode->next = temp;
    }
}
void deleteValue(node *&head, int id)
{
    node *temp = head;
    node *prior = nullptr;
    if (temp != nullptr && temp->id == id)
    {
        head = temp->next;
        head->prev = nullptr; // 这里可要可不要
        delete temp;
        return;
    } // 删除头节点
    while (temp != nullptr && temp->id != id)
    {
        prior = temp;
        temp = temp->next;
    }
    if (temp == nullptr)
    {
        return;
    }
    prior->next = temp->next;
    prior->prev = temp->prev;
    if (temp->next != nullptr)
        temp->next->prev = prior;
    delete temp;
}
void printList(node *head)
{
    node *temp = head;
    while (temp != nullptr)
    {
        cout << temp->id << " ";
        temp = temp->next;
    }
    cout << endl;
}

附经典解法哈希+双向链表AC代码。

优化代码，哈希将查找与删除的时间复杂度优化为O(1)，用空间换时间。

点击查看代码

#include <iostream>
#include <unordered_map>
using namespace std;

struct node {
    int id;
    node *prev;
    node *next;
};

void insert(node *&head, int k_id, int new_id, bool left, unordered_map<int, node*> &nodes) {
    node *target = nodes[k_id];
    node *newNode = new node();
    newNode->id = new_id;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    nodes[new_id] = newNode;

    if (!left) { // 插入到右侧
        newNode->prev = target;
        newNode->next = target->next;
        if (target->next != nullptr) {
            target->next->prev = newNode;
        }
        target->next = newNode;
    } else { // 插入到左侧
        newNode->next = target;
        newNode->prev = target->prev;
        if (target->prev != nullptr) {
            target->prev->next = newNode;
        } else {
            head = newNode; // 更新头节点
        }
        target->prev = newNode;
    }
}

void deleteNode(node *&head, int id, unordered_map<int, node*> &nodes) {
    if (nodes.find(id) == nodes.end()) return;
    node *target = nodes[id];

    // 更新前驱节点
    if (target->prev != nullptr) {
        target->prev->next = target->next;
    } else {
        head = target->next; // 删除的是头节点
    }

    // 更新后继节点
    if (target->next != nullptr) {
        target->next->prev = target->prev;
    }

    nodes.erase(id);
    delete target;
}

void printList(node *head) {
    node *temp = head;
    while (temp != nullptr) {
        cout << temp->id << " ";
        cout << temp->id << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;
    node *head = new node();
    head->id = 1;
    head->prev = head->next = nullptr;
    unordered_map<int, node*> nodes;
    nodes[1] = head;

    for (int i = 1; i < n; ++i) {
        int k, p;
        cin >> k >> p;
        insert(head, k, i + 1, p == 0, nodes);
    }

    cin >> m;
    while (m--) {
        int id;
        cin >> id;
        deleteNode(head, id, nodes);
    }

    printList(head);

    // 释放内存
    node *current = head;
    while (current) {
        node *next = current->next;
        delete current;
        current = next;
    }

    return 0;
}