链表

2022-02-12

线性表的链式表示

单链表的定义

对于每个链表节点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针

typedef struct LNode{
    ElemType data;  // 数据域
    LNode *next;    // 指针域
}LNode, *LinkList;

单链表可以解决顺序表需要大量连续存储空间的缺点，但附加的指针域存在浪费空间的缺点，也无法随机存取

通常用头指针标识一个单链表

为了操作方便，在单链表前可以增加一个头节点，可以使空表和非空表的操作得到统一，链表第一个节点和其他节点的操作也得到统一

单链表上基础操作的实现

头插法建立单链表

新节点插入链表表头。最后读入数据的顺序和生成的链表的元素的顺序是相反的

void HeadInsert(LinkList &L){
    LNode* node = (LNode*) malloc(sizeof(LNode));
    // 关键
    node->next = L->next;
    L->next = node;
}

尾插法建立单链表

新节点插入链表表尾，最后读入数据的顺序和生成的链表的元素的顺序相同

void TailInsert(LinkList &L){
    LNode* node = new LNode;
    // tail为尾指针，指向链表L的最后一个元素
    node->data = /* you want */;
    node->next = nullptr;
    // 关键
    tail->next = ndoe;
    tail = node;
}

按序号查找节点

不断沿着next域找到第i个节点即可

LNode* GetElem(LinkList& L, int i){
    int j = 1;
    LNode p = L;
    while(j < i){
        if(!p)  return p;   // 链表长度小于i，返回nullptr
        p = p->next;
    }
    return p;
}

按值查找节点

从链表头开始查找，找到满足要求的节点值则返回

LNode* LocateElem(LinkList& L, ElemType e){
    LNode* p = L->next; // 假设带头节点
    while(p && p->data != e){
        p = p->next;
    }
    return p;
}

插入节点

假设将节点s插入p之后

扩展：O(1)前插？

// 实现后插的代码
s->next = p->next;
p->next = s;

// 实现O(1)前插
s->next = p->next;
p->next = s;
swap(s->data, p->data); // 交换节点的值

删除节点

假设欲删除节点p的后继节点

扩展：O(1)删除当前节点？

// 实现删除后继节点的代码
auto q = p->next;
p->next = q->next;
free(q);

// 删除当前节点的代码
auto q = p->next;
auto data = q->data;
p->next = q->next;
p->data = data; // 交换节点的值