链表实现

静态数组 - 带哨兵位单向非循环链表

const int N = 1e5 + 10; // 数据范围
int e[N], ne[N], h, id; // 数据域、指针域、哨兵结点、新分配单元位置

// 头插
void push_front(int data) {
    e[++id] = data;
    ne[id] = ne[h];
    ne[h] = id;
}

// 尾插
void push_back(int data) {
    int cur = 0;
    while (ne[cur])
        cur = ne[cur];
    e[++id] = data;
    ne[cur] = id;
}

// 中间插入
void insert_back(int data, int pos) {
    id++;
    e[id] = data;
    ne[id] = ne[pos];
    ne[pos] = id;
}

void erase_back(int pos) {
    if (ne[pos]) {
        // 判断不是最后一个元素
        // 若使用了mp数组，则此处还需要把mp数组内的标记清空：mp[e[ne[pos]]] = 0;

        // 让指向pos位置的指针域，改成原pos位置的下一个元素
        ne[pos] = ne[ne[pos]];
    }
}

// 按值查找，找不到则返回0
int find(int data) {
    for (int cur = ne[0]; cur; cur = ne[cur])
        if (e[cur] == data)
            return cur;
    return 0;
}

void print() {
    // 打印链表
    int cur = 0;
    for (cur = ne[h]; cur; cur = ne[cur])
        cout << e[cur] << " ";
    cout << endl;
}

静态链表（含mp[]版本）

const int N = 1e5 + 10;
int e[N], pre[N], ne[N], h, id;
int mp[N]; // mp[i]表示i的位置

void push_front(int data) {
    e[++id] = data;
    pre[id] = h; // 新来结点的左指针
    ne[id] = ne[h]; // 新来结点的右指针

    mp[data] = id;

    pre[ne[h]] = id; // 修改原来第一个结点的左指针
    ne[h] = id; // 修改头结点的右指针
}

int find(int data) {
    // 按值查找，使用mp优化
    return mp[data];
}

void insert_back(int data, int pos) {
    e[++id] = data;
    ne[id] = ne[pos];
    pre[id] = pos;

    mp[data] = id;

    ne[pos] = id; // 修改pos位置的后继
    pre[ne[id]] = id; // 修改ne[id]的前驱
}

void insert_front(int data, int pos) {
    e[++id] = data;
    ne[id] = pos;
    pre[id] = pre[pos];

    mp[data] = id;

    ne[pre[pos]] = id; // 修改pre[pos]位置的后继
    pre[pos] = id; // 修改pos位置的前驱
}

void erase(int pos) {
    mp[e[pos]] = 0;

    ne[pre[pos]] = ne[pos]; // 修改pre[pos]的后继
    pre[ne[pos]] = pre[pos]; // 修改ne[pos]的前驱
}

静态数组 - 不带哨兵位单向非循环链表

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int e[2 * N], ne[2 * N], id, h[N];

// 头插
void push_front(const int& list, const int& data) {
    e[++id] = data;
    ne[id] = h[list];
    h[list] = id;
}

// 遍历
void print(const int& list) {
    int cur = 0;
    for (int cur = h[list]; cur; cur = cur = ne[cur])
        cout << e[cur] << " ";
    cout << endl;
}

// 树、图中，常常这样加入一条边
void addEdge(const int& a, const int& b) {
    e[++id] = b;
    ne[id] = h[a];
    h[a] = id;

    e[++id] = a;
    ne[id] = h[b];
    h[b] = id;
}

int main() {
    push_front(1, 1);
    push_front(1, 2);
    print(1);
    print(2);
    return 0;
}

动态扩容无头单向非循环链表

• 定义链表数据结构

  • 数据类型定义

    typedef int data_type; // 定义元素的数据类型
    typedef struct {
        data_type data;
        struct node* next;
    } node;
    
    typedef struct {
        node* phead;
    } list;

    说明：

    • 节点类型：含数据、下一个节点的指针
    • 链表类型：含第一个节点指针，并用于维护链表

  • 节点的创建

    static node* new_node(data_type data) {
        // 生成一个新结点
        node* newnode = (node*)malloc(sizeof(node));
        if (newnode == NULL)
            exit(0);
        else {
            newnode->next = NULL;
            newnode->data = data;
        }
        return newnode;
    }

    注：

    • 使用了static关键字，表示只在链表实现中使用
    • 销毁节点的代码不写，因为只由销毁链表删除所有节点（以及删除元素时释放节点内存）

  • 初始化函数

    list* init() {
        list* ret = (list*)malloc(sizeof(list));
        ret->phead = NULL;
        return ret;
    }

  • 销毁函数

    void destory(list* ptr) {
        assert(ptr && ptr->phead);
    
        // 从头节点出发，依次释放所有节点内存
        node* cur = ptr->phead;
        if (cur) {
            node* next = cur->next;
            while (cur != NULL) {
                free(cur);
                cur = next;
                if (cur)
                    next = cur->next;
            }
        }
        free(ptr);
    }

• 接口实现

  • insert_front()

    void insert_front(list* ptr, node* pos, data_type data) {
        assert(ptr);
    
        if (ptr->phead == NULL || ptr->phead == pos) {
            // 为第一个结点的情况
            node* newnode = new_node(data);
    
            newnode->next = ptr->phead;
            ptr->phead = newnode;
        }
        else {
            node* prev = ptr->phead;
            while (prev->next != pos)
                prev = prev->next;
    
            node* newnode = new_node(data);
            newnode->next = prev->next;
            prev->next = newnode;
        }
    }

  • erase()

    void erase(list* ptr, node* pos) {
        assert(ptr && ptr->phead && pos);
    
        if (pos == ptr->phead) {
            // 为第一个结点的情况
            node* newhead = ptr->phead->next;
            free(ptr->phead);
            ptr->phead = newhead;
        }
        else {
            node* prev = ptr->phead;
            while (prev->next != pos)
                prev = prev->next;
    
            prev->next = pos->next;
            free(pos);
        }
    }

  • 头插、头删

    void push_front(list* ptr, data_type data) {
        insert_front(ptr, ptr->phead, data);
    }
    
    void pop_front(list* ptr) {
        erase(ptr, ptr->phead);
    }

  • 其他接口

    int size(list* ptr) {
        assert(ptr);
    
        int ret = 0;
        node* cur = ptr->phead;
        while (cur) {
            cur = cur->next;
            ret++;
        }
        return ret;
    }
    
    node* find(list* ptr, data_type data) {
        // 按值查找，返回地址，未找到则返回空指针
        assert(ptr);
    
        node* cur = NULL;
        for (cur = ptr->phead; cur; cur = cur->next) {
            if (cur->data == data)
                return cur;
        }
        return NULL;
    }
    
    data_type at(list* ptr, int loc) {
        // 按位查找
        assert(ptr);
    
        int i = 0;
        node* cur = ptr->phead;
        for (i = 0; i < loc; i++) {
            assert(cur);
            cur = cur->next;
        }
        return cur->data;
    }

动态扩容有头双向循环链表

• 定义链表数据结构

  • 数据类型定义

    typedef int data_type;
    typedef struct node {
        struct node* prev; // 上一个结点指针
        data_type data; // 数据
        struct node* next; // 下一个结点指针
    } node;

  • 生成新结点

    static node* new_node(data_type data) {
        // 生成新结点
        node* newnode = (node*)malloc(sizeof(node));
        if (newnode == NULL)
            exit(0);
    
        newnode->data = data;
        newnode->prev = NULL;
        newnode->next = NULL;
    
        return newnode;
    }

  • 链表的初始化

    node* init() {
        // 链表的初始化，返回哨兵位的头结点
        node* newnode = new_node(0);
        newnode->next = newnode;
        newnode->prev = newnode;
        return newnode;
    }

  • 销毁函数

    void destory(node* plist) {
        assert(plist);
    
        node* cur = plist->next;
        node* next = cur->next;
        while (cur != plist) {
            free(cur);
            cur = next;
            next = cur->next;
        }
        free(plist);
    }

• 接口实现

  • insert_front()、erase()

    void insert_front(node* pos, data_type data) {
        assert(pos);
    
        node* newnode = new_node(data);
    
        node* prev = pos->prev;
        prev->next = newnode;
        newnode->prev = prev;
        newnode->next = pos;
        pos->prev = newnode;
    }
    
    void erase(node* pos) {
        assert(pos);
    
        // 链接新的链表顺序
        (pos->prev)->next = pos->next;
        (pos->next)->prev = pos->prev;
    
        // 释放空间
        free(pos);
        pos = NULL;
    }

  • 尾插、头插、尾删、头删

    void push_back(node* plist, data_type data) {
        insert_front(plist, data);
    }
    
    void push_front(node* plist, data_type data) {
        insert_front(plist->next, data);
    }
    
    void pop_back(node* plist) {
        assert(plist);
    
        if (plist->prev != plist)
            erase(plist->prev);
    }
    
    void pop_front(node* plist) {
        assert(plist);
    
        if (plist->next != plist)
            erase(plist->next);
    }

  • 其他接口

    node* find(node* plist, data_type data) {
        // 按值查找，未找到则返回空指针
        assert(plist);
    
        node* cur = NULL;
        for (cur = plist->next; cur != plist; cur = cur->next) {
            if (cur->data == data)
                return cur;
        }
        return NULL;
    }