链表

杂

养成了开篇说废话的好习惯， 啊，写之前没想到要用指针来着，_指针废qwq

链表

+++

认识一下

链表 & 数组都可用于存储数据，链表通过 指针 来连接元素， 而数组是把所有元素按次序存储

各自优势：

链表 ： 方便地删除、插入数据 —— (O(1)) ，但随机访问数据 —— (O(n))

数组 ： 随机访问数据 —— (O(1)) ， 删除、插入数据 —— (O(n))

---

构建

单向链表

• 数据域 ： 存放数据
• 指针域 ： 连接当前节点和下一节点

struct Node {
    int value;
    Node *nxet;
}

双向链表

不同于单向 ： 指针域 ： 连接当前节点和下一节点

struct Node {
    int value;
    Node *left, *right;
}

---

向链表中插入（写入）数据

单向链表

void insert(int i, Node *p) {
    Node *node = new Node;
    node->value = i;
    node->nxet = p->nxet;
    p->nxet = node;
}

单向循环链表

将链表的头和尾连接起来

void insert(int i, Node) {
    Node *node = new node;
    node->value = i;
    node->nxet = NULL;
    if(p == NULL) { //判断原链表是否为空，空则自身循环
        p = node;
        node->nxet = node;
    } else { //不空则正常插入
        node->nxet = p->nxet;
        p->nxet = node;
    }
}

双向循环链表

void insert(int i, Node *p) {
    Node *node = new Node;
    node->value = i;
    if(p == NULL) {
        p = node;
        node->left = node;
        node->right = node;
    } else {
        node ->left = p;
        node->right = p->right;
        p->right->left = node;
        p->right = node;
    }
}

---

从链表中删除数据

单向（循环）链表

将 p->nxet 的值覆盖给 p ，同时更新 p 的下下个节点

void deletenode(Node *p) {
    p->value = p->nxet->value;
    Node *t = p->nxet;
    p->nxet = p->nxet->nxet;
    delete t;
}

双向循环链表

画个图自行理解一下就好啦(￣▽￣)／

void deletenode(Node *p) {
    p->left->right = p->right;
    p->right->left = p->left;
    Node *t = p;
    p = p->right;
    delete t;
}

撒花✿✿ヽ(°▽°)ノ✿

还是数组香 ↓ 我直接搬书

struct Node{
    int value;
    int pre, next;
} node[SIZE];
int head, tail, tot;

int init(){
    tot = 2;
    head = 1; tail = 2;
    node[head].next = tail;
    node[tail].pre = head;
}

void insert(int p, int val){
    q = ++ tot;
    node[q].value = val;
    node[node[p].next].pre = q;
    node[q].next = node[p].next;
    node[p].next = q;
    node[q].pre = p;
}

void remove(int p){
    node[node[p].pre].next = node[p].next;
    node[node[p].next].pre = node[p].pre;
}

void clear(){
    memset(node, 0, sizeof(node));
    head = tail = tot = 0;
}

❀ ❀

​ ❀