数据结构02-链表

数据结构与算法 2022年8月1日
0

单链表

链表的概念

上一节介绍了线性表的概念，同时使用数组实现顺序存储方式的线性表。使用顺序存储方式的线性表的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此元素的存储与访问都比较简单，各种操作也很直观。

然而，顺序存储结构也存在一定缺点，例如：

  • 在表的中间插入或删除时，后面的元素会被频繁地移来移去，产生线性开销，浪费大量时间；
  • 表的尺寸是有限值的，当达到尺寸限值时若还需要插入元素，需要重新申请内存空间并移动所有元素

为了避免以上缺点，这就要求插入元素时元素的位置可以任意存放，这样就无需移动元素，也无需在尺寸不够时需要重新申请一大块内存并移动所有元素。

然而，为了能够将表项关联为一个整体，需要有一种方法能找到表的每项元素的位置。这里提出了链表(linked list)的概念。链表的实现是一种非连续的存储，在每项元素中都指出下一项元素的位置。

下图表达了链表的思想：

linked list

从上图可以看到，链表的每一个结构都由两部分组成：

  1. 数据域：数据元素本身
  2. 指针域：指针 next 指向该元素的后继元素结构

特别地，最后一个单元的 next 指针指向 NULL ，代表链表的结束。

因此，链表节点结构的定义如下：

typedef struct linkedlist_node {
    elemtype elem;
    struct linkedlist_node* next;
} linkedlist_node, * linkedlist;

为了执行打印表或查找等遍历操作，只需要用一个指针记录该表的第一个元素，然后不断用 next 指针获取后继元素即可访问链表的每一项。

链表在插入和删除时表的整体或部分无需全部移动，避免了线性开销。删除命令只需要通过修改一个指针实现：

在遍历表时，\\( A_3 \\) 元素由于没有指针指向它，不会被访问到，便会直接忽略，达到删除的效果。

插入命令只需要通过一次 malloc() 调用从系统中获得一个新节点结构，并调整周围的指针：

仔细研究上图可以发现，以上实现仍然存在一些问题，主要涉及首节点元素：它的插入和删除方式都比较特殊，因为不涉及修改调整前指针。

为了方便起见，需要留出一个标志节点元素，称为表头节点。通过表头可以很容易地管理表元素：

接下来演示链表的具体操作。

链表的具体操作

根据链表的定义，测试一个链表是否是空链表是很容易的：

bool LinkedList_IsEmpty(linkedlist list) {
    return list->next == NULL;
}

该函数也可以用于测试一个节点位置是否已经位于链表的末尾。线性表作为一个整体拥有表示长度的成员信息，但链表没有。在遍历时为了防止越界，必须不断判断是否遍历到链表的末尾。

线性表在查找元素时必须一个个元素挨个判断过去，链表也不例外。只需要从表头或任意链表位置开始，不断向后查询节点，直到找到所需要的元素即可。链表的查找操作如下：

linkedlist_node* LinkedList_GetNode(linkedlist_node* node, elemtype value) {
    linkedlist_node* nxt = node->next;
    while (nxt != NULL && nxt->elem != value)
        nxt = nxt->next;
    return nxt;
}

while 判断条件利用了 && 运算符的短路原理，一旦发现到达结尾，就不再判断值的存在性。

上面介绍过链表的删除和插入原理，接下来尝试使用代码实现。删除节点的操作相对容易实现，只需要找到节点的前驱节点 previous ，再通过调整一个指针指向：

previous->next=previous->next->next;

即可完成删除。不过该操作的难点在于节点只保存下一个节点的位置，因此无法通过一个现有节点简单获取前一个节点的位置。为了找到前驱元素，需要额外编写一个函数来寻找它：

linkedlist_node* LinkedList_GetPrevNode(linkedlist list, elemtype value) {
    linkedlist_node* prev = list;
    while (prev->next != NULL && prev->next->elem != value)
        prev = prev->next;
    return prev;
}

两种查找整体实现类似，只不过它直接跨节点查找，以确保不丢失上一个节点的信息。

配合该例程以及上文的介绍，可以很容易编写出删除链表元素的函数：

status LinkedList_Remove(linkedlist list, elemtype value) {
    linkedlist_node* prev = LinkedList_GetPrevNode(list, value);
    if (!LinkedList_IsLast(prev)) {
        linkedlist_node* temp = prev->next;
        prev->next = temp->next;  // bypass deleted cell
        free(temp);
        return 0;
    }
    return 1;
}

在查找前驱节点时，可能发生找不到的情况，此时返回的是最后一个节点，要对这种情况加以判断。

插入比删除略复杂。观察以上插入图示可以看出，为了保证链表在任何时候不断裂，插入的步骤需要按以下顺序进行：

  1. 将新节点的 next 指针顺着旧节点指向下一个元素
  2. 断开旧节点的 next 指针，指向新节点

这两个步骤不能反过来，否则后续节点的位置信息就丢失了。相应的C语言实现如下：

void LinkedList_InsertAfter(linkedlist_node* prev, elemtype value) {
    linkedlist_node* temp = malloc(sizeof(linkedlist_node));
    if (temp == NULL) {
        /* fail to allocate memory for node */
        return;
    }
    temp->elem = value;
    temp->next = prev->next;
    prev->next = temp;
}

从以上代码可以看出，链表在增删时需要不断调用 malloc() 和 free() 来管理内存，因此链表是动态的，它无需一次性分配一大段内存，可以在需要的时候再申请一小部分。

除去查找外，链表的插入和删除的时间复杂度是常数级 \\( O(1) \\) 的。不过链表的缺点只记录下一个元素的信息，因此如果只是访问特定位置的元素时，顺序存储结构可以直接偏移地址，但链表需要一个个按线索找出后续元素，因此链表的随机访问具有线性时间消耗。

尽管链表之间是单向连接的，不过可以使用一种很简单的算法反转单向链表：顺序遍历该链表，并将每个元素依次插入反转表的开头。这样的反转算法只需要消耗线性时间，并且无需额外的存储空间：

linkedlist LinkedList_Reverse(linkedlist list) {
    linkedlist_node* header = malloc(sizeof(linkedlist_node));
    if (!header)
        return NULL;
    header->next = NULL;
    while (list = list->next) {
        LinkedList_InsertAfter(header, list->elem);
    }
    return header;
}

静态链表(游标实现)

静态链表的概念

并不是所有语言都支持指针。如果想不使用指针或引用实现链表，就需要使用静态链表。这种链表是通过游标访问元素的。

链表的指针实现中有两个必须实现的特性：

  1. 每个节点都是一个结构，一个结构包含数据以及指向下一个结构体的指针
  2. 一个新的节点可以调用 malloc() 从内存中得到，并可以通过 free() 释放

游标方法必须能够模仿这两条特性。

下图展示了游标方法实现静态链表的原理：

满足条件 1 的逻辑方式是要有一个全局的结构体数组，对于该数组中的单元，其数组下标可以用来代表一个地址，从而模拟指针。

下面给出了静态链表的游标实现的声明：

typedef struct slinkedlist_node {
    elemtype elem;
    int cursor;
} slinkedlist_node;

#define  SLINKEDLIST_SIZE 1024
slinkedlist_node linkedspace[SLINKEDLIST_SIZE];

模拟条件 2 的方法是，除了数据本身通过游标组成的链表外，在静态链表空间中还需要有一条连接各个空闲位置的链表，称为备用链表。

备用链表 freedspace 数组中的闲置单元可以执行 malloc() 和 free() 。对于 cursor 游标，0 的值等价于 NULL 指针。

  • 为了执行 malloc() 功能，将表头后面的第一个元素从 freedspace 表中删除
  • 为了执行 free() 功能，将该单元放在 freedspace 表的前段

通常将 linkedspace[0] 作为备用链表的表头使用，linkedspace[1] 作为数据链表的表头使用。这样，对应的C语言代码为：

int SLinkedList_Alloc(void) {
    int pos = linkedspace[0].cursor;
    linkedspace[0].cursor = linkedspace[pos].cursor;
    return pos;
}
void SLinkedList_Free(int pos) {
    linkedspace[pos].cursor = linkedspace[0].cursor;
    linkedspace[0].cursor = pos;
}

注意，如果没有可分配的空间，它会正确返回位置 0 以供判断。下图展示了某一时刻的静态链表：

由于静态链表的游标充当后向指针，判断一个静态链表是否为空，或一个节点是否位于静态链表末尾和普通链表相似：

bool SLinkedList_IsEmpty(int list) {
    return linkedspace[list].cursor == 0;
}
bool SLinkedList_IsLast(int pos) {
    return linkedspace[pos].cursor == 0;
}

静态链表的操作

静态链表的操作和普通链表具有相似性。例如查找例程，它通过从数据链表的表头逐个遍历 cursor 指向的静态链表空间位置来访问下一个元素：

int SLinkedList_Find(int list, elemtype elem) {
    int pos = linkedspace[list].cursor;
    while (pos && linkedspace[pos].elem != elem)
        pos = linkedspace[pos].cursor;
    return pos;
}

删除的原理和指针链表一致，即找出前驱元素的位置 prev ，通过跨越节点：

linkedspace[prev].cursor = linkedspace[linkedspace[prev].cursor].cursor

即可完成删除。删除后还需要释放节点占用的空间。

查询前驱元素节点的函数实现为：

int SLinkedList_FindPrevPos(int list, elemtype elem) {
    int prev = linkedspace[list].cursor;
    while (prev && linkedspace[linkedspace[prev].cursor].elem != elem)
        prev = linkedspace[prev].cursor;
    return prev;
}

那么删除的程序实现为：

status SLinkedList_Remove(int list, elemtype elem) {
    int temp;
    int pos = SLinkedList_FindPrevPos(list, elem);
    if (!SLinkedList_IsLast(pos)) {
        temp = linkedspace[pos].cursor;
        linkedspace[pos].cursor = linkedspace[temp].cursor;
        SLinkedList_Free(temp);
        return 0;
    }
    return 1;
}

注意比较与指针链表的异同点。指针链表的 this->next 等价于静态链表的 linkedspace[this].cursor 。

因此，类比一下指针链表的插入，静态链表的插入实现为：

status SLinkedList_InsertAfter(int prev, elemtype elem) {
    int temp = SLinkedList_Alloc();
    if (temp == 0) {
        /* fail to allocate memory */
        return 1;
    }
    linkedspace[temp].elem = elem;
    linkedspace[temp].cursor = linkedspace[prev].cursor;
    linkedspace[prev].cursor = temp;
}

指针链表的核心是 node* 指针，用来在内存中找出下一个节点所在的位置。静态链表的核心是 int 值，用来在 linkedspace 中找出下一个节点所在的位置。因此可以认为静态链表在程序中维护了自己的一段“内存”，进而自行制造了指针这一概念。理解了这一点，便不难理解指针链表与静态链表的关系了。

更多链表模型

链表是一种非常经典的数据结构，它提供了一种非顺序的关联结构，借由一个指针可以指向其关联的任意元素。从链表开始，数据结构的两个项之间的关系开始变得语义化。

通过增加节点指针的个数，可以使节点之间拥有一对多的关系。

链表有几种典型的扩展，使链表可以适应更多场景。接下来简要介绍。

双链表

有时需要倒序扫描链表或局部倒序后退节点，但是普通链表的实现却非常复杂。这里提出双链表(doubly linked list)的概念，本质上就是在链表的基础上增加了一个前向指针 prev ，使链表节点间可以双向连接。

下图展示了双链表的原理：

双链表可以使向前检索变得更便利，但代价是一个附加的链，增加了空间的需求，同时也增加了插入和删除的开销，因为有更多指针需要调整。

首先看双链表的插入。如果需要向双链表中插入元素，需要完成以下几个工作：

  • 调整前一节点的 next 指针和后一节点的 prev 指针
  • 为当前节点的 next 和 prev 指针建立连接
操作的图示为：

双链表的插入只需要给出前面或后面的节点作为定位即可。这里以给出前面的节点为例编写代码：

status DuLinkedList_InsertAfter(dulinkedlist_node* previous, elemtype value) {
    dulinkedlist_node* next = previous->next;
    dulinkedlist_node* temp = malloc(sizeof(dulinkedlist_node));
    if (temp == NULL)
        return 1;
    temp->elem = value;
    temp->next = next;  // adjusting between this and next
    next->prev = temp;
    temp->prev = previous;   // adjusting between this and prev
    previous->next = temp;
    return 0;
}

双链表在删除时，需要调整的指针个数比单链表更多。但是双链表的删除操作比单链表简单，因为前驱元素的信息是现成的。

下图展示了双链表的删除操作：

可以正序扫描双链表以找出所需元素，也可以倒序扫描。以下示例使用倒序扫描删除链表的最后一个找出的节点。为了判断倒序扫描结束，需要不断判断当前位置是否为表头：

bool DuLinkedList_IsHeader(dulinkedlist_node* node) {
    return node->prev == NULL;
}
void DuLinkedList_DeleteLast(dulinkedlist_node* last, elemtype value) {
    dulinkedlist_node* tmp = last;
    while (tmp && tmp->elem != value)
        tmp = tmp->prev;
    if (tmp && !DuLinkedList_IsHeader(tmp)) {
        tmp->prev->next = tmp->next;
        tmp->next->prev = tmp->prev;
        free(tmp);
    }
}

双链表是一种特殊的链表，除了原生支持倒序查找外，其余的操作例如查找或遍历，都与普通的单链表并没有太大区别。

循环链表

链表的后继指针可以指向任何符合语义的节点元素，这也就意味着一个修改后的链表可以不是线性的，而是拥有各种不同的形态。

例如，可以让链表的最后一个元素指向第一个元素或表头，由此整个链表会发生闭合，形成循环链表(circular linked list)。下图展示了一个有表头的单链循环链表：

循环链表的操作和普通链表一致，差别仅在于判断遍历终止的条件为是否回到表头或首元素而不是遇到 NULL 。

循环链表也可以和双链表组合在一起，形成双向循环链表。下图展示了一个没有表头的双链循环链表：

由此可见，链表只需要对节点做一些调整，就能适应多种多样的场景。有些时候需要经常获取链表的长度，但遍历链表显然是个低效的做法，此时可以为表头提供一个特殊的节点定义，它包含链表的长度信息，并在增加或删除结点时实时更新长度。

又或是有时需要频繁地在链表的结尾位置增加或删除数据，由于链表不能直接通过地址偏移找到末尾节点的位置，那么可以在表头添加一个指向尾部节点的指针域，通过该域可以快速访问链表的末尾位置。

下图展示了修改后的链表模型：

这样并没有为单次操作增加多少工作量，却可以很好地避免某些操作产生的线性开销。后续介绍的许多数据结构，例如树和图，都与链表的思想密不可分。

Tags:

You may also like...

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

近期文章

活动日历

2024 年 4 月
一 二 三 四 五 六 日
1234567
891011121314
15161718192021
22232425262728
2930  

音频

京ICP备2021034974号
contact me by hello@frozencandles.fun