Day-19 ADT与链结串列(linked list)

前言

链结串列(linked list)是由一连串的结构(由 struct 所建立的节点)所构成，每一个节点中都含有两笔资料，分别为节点的内容和下一个节点的记忆体地址。

ADT(Abstract data type)抽象资料型别

ADT可拆分为两个部分，分别为资料结构，以及对於这一些资料结构的操作的规范。而ADT所表示的就是资料结构加上对於资料结构操作所形成的集合，例如我们会将堆叠(stack)称做为一个资料结构，其中我们可以针对stack进行以下操作，分别为推入push，弹出pop，检视最顶端的资料peek，而这一些操作，我们会有对应的规范。

ADT负责对於每一个操作进行规范，而并非如何时做出这一些操作。对於这些操作的实作方面是直接在主程序内进行实作，将每一个操作写成函式，後续要重覆进行这些操作只需要透过呼叫这一些函式即可完成。

阵列(Array)的优点与缺点

在前面我们储存多笔数据时我们此用了阵列(array)进行储存，而阵列的特点在於资料和资料之间是连续记忆体分布的，也因为这这个特性我们可以使用指标的偏移(offset)，或是直接查询的方式找到阵列中的某一个数值，也可以透过这样的方式得知整个阵列的长度，最後一个数值减去第一个数值，算初期记忆体偏移即可求出阵列的长度，而这些是阵列的优点

而阵列的缺点在於当我们要插入或是删除数值时，我们需要移动阵列所有的元素来进行插入，而这麽做是十分低效率的

链结串列(Linked list)的优点与缺点

而这里要介绍的链接串列，是由一连串在记忆体中不连续的结构所组成。每一个结构包含结构中的值和指向下一个结构的指标。

他的优点即是方便我们进行资料的插入与删除，只要改变每一个节点中，指向的下一个节点可以完成插入，不需要移动整个串列就可以实现，避免删除和插入所需耗费的线性时间。

而链结串列的缺点即是他无法直接查询串列中的数值，我们也无法透过指标的偏移来查询阵列中的元素，因为不连续记忆体分布的特性，我们必须将一个连接串列由头走到尾才能够找到我们想要寻找的数值，而得到链接串列的长度也是如此。

链结串列(Linked list)的ADT

以C语言为例，一般来说会将含是ㄓ也就是.h档案中，具体节点(Node)的宣告则放在.c档案中，下面示范为链结串列的ADT。

#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);

#endif /* _List_H */

/*放入主程序中*/
struct Node
{
    ElementType Element;
    Position Next;
};

链结串列的节点(Node)表示

为了建立一个链结串列，我们首先要先建立链结列中的节点，而这里我们每一个节点中包含节点中的数值和下一个节点的记忆体地址，使用结构宣告如下。

struct node{
  int value;
  struct node *next;
};

说明:成员next指向一个型别为node型别的指标。
我们回忆一下，指标变数就是储存另外某个数据所在的记忆体的变数，因此，如果P被宣告成一个指向结构变数的指标，那麽P变数中的数值就是记忆体中的地址，在这个地址中可以找到结构变数。

这里我们完成了链结串列节点的宣告，再来我们可以开始建立链结串列了，我们宣告第一个节点名称为head来表示链结串列中的第一个节点。

struct head* first = NULL;

这里把head的指向设为空指标表示链结串列初始为空。

下图为链结串列加上指标的示意图

建立节点

在建立链结串列时，需要一个一个的建立节点，并把每一个节点和链结串列进行连结，而通常建立节点需要做三件事情

1. 分配记忆体空间给节点
2. 把数据储存到节点中
3. 把节点串连到链结串列上

为了建立节点，我们需要宣告一个临时使用的变数指向建立的节点，直到该点连接到链结串列上

struct node *new_node

我们可以使用malloc得到记忆体空间，并将malloc回传的指标储存在next_node中，而现在next_node即指向到一块由malloc所要求到的记忆体空间，并且这一个记忆体空间刚好可以放下一个node的大小

new_node = malloc(sizeof(node) * 1);

注意

sizeof为该型别所占的记忆体大小，而不是该指标所指向型别所占的记忆体大小，所以是sizeof(node)，而不是sizeof(new_node)

接下来把数据储存到新的节点中

new_node->value = 10;

或是

(*new_node).value = 10;

这里使用括号的原因为 . (结构成员运算子)的优先顺序大於 * (结构指标运算子)

接着，将new_node所指向的下一个节点设为NULL，避免不当操作导致记忆体溢位的问题发生

new_node->next = NULL;

-> 结构指标运算子(right arrow selection)

我们可以使用结构指标运算子来存取结构中的成员，利用指标存取结构是一种非常普遍的做法，以至於後来C语言针对这个做法提供了一种特殊的运算符，称为结构指标运算子，由一个减号 - 和一个 > 所构成，於是构成了上面所介绍的这种写法

new_node->value = 10;

先对new_node进行间接寻址，然後再选择成员value

测试一个链结串列是否为空

int IsEmpty(struct node* head)
{
    return head->next == NULL;
}

如果为真则回传1，表示true。

测试一个节点是否为链结串列的尾巴（最後节点）

int IsLast(struct node* p)
{
    return p->next == NULL;
}

如果为真则回传1，表示true。

搜寻链结串列

在搜寻链结串列时，我们只要将一个指到链结串列头的指标传入函式，在函式内使用next走访整个链结串列即可，时间复杂度为一个线性时间，跟随着链结串列的长度而决定。

我们上面建立了一个链结串列，我们可能会遇到需要搜寻链结串列上某一个节点的情况。虽然使用while回圈可以用来搜寻链结串列，但一般来说使用for回圈居多，对於有计数(counting)操作时，习惯使用for回圈，且使用for回圈也有利於我们对链结串列进行其他操作，下面是一种搜寻链结串列的常见方法，使用了指标p来追踪'目前'的节点。

for(NODE* p = first; p != NULL; p = p->next)

p = p->next即是移动到下一个节点。

下面我们建立一个名称为search_list的函式，这个函数为了找到某一个整数n而遍历整个链结串列，如果找到整数n，则回传整数n所在的节点的指标，否则，回传空指标，范例如下

struct node* search_list(struct node* head, int n)
{
    struct node* p;
    for(p = head; p != NULL; p = p->next)
    {
        if(p->value == n)
        {
            return p;
        }
    }
    return NULL;
}

而下面是在不使用指标p，直接使用head进行搜寻

struct node* search_list(struct node* head, int n)
{
    for(;head != NULL; head = head->next)
    {
        if(head->value == n)
        {
            return head;
        }
    }
    return NULL;
}

这里可以这样使用是因为传入函式的head是原始链结串列指标的复制品，所以在函式内改变他不会造成影响。

而使用while回圈实做搜寻链结串列的方式可以使用下面程序进行表示

LIST-SEARCH(L.k)
x = L.head
while X != NULL and x.key != k
    x = x.next
return x

struct node* search_list(struct node* L, int val)
{
    struct node* p = L;
    while (p != NULL && p->value != val)
    {
        p = p->next;
    }
    return p;
}

我们宣告一个指向节点(结构)的指标变数p，使用p用来遍历整个链结串列，当p找到我们要寻找的数值存在的节点(第一次出现的数字，有可能後面也有节点是我们要找的数字)，那麽回传该节点的指标。

删除节点(Delete)

我们在先前提到过，要删除阵列中的数据是一件非常麻烦的事情，而在链结串列中却是一件十分容易的事情，而删除节点就如同建立节点依样需要三个步骤

1. 定位要删除的节点
2. 改变前一个节点，使他绕过删除的节点
3. 呼叫free函式释放删除的节点所占用的记忆体空间

如果第一步我们使用搜寻链结串列的方法进行实作，那麽将会在指标指向要删除的节点时停止搜寻，我们就无法执行第二步，改变前一个节点了，针对这个问题，有一种解决方法。

我们使用指标追踪来实现，具体如下
在第一步搜寻整个链结串列时，保留一个指向前一个节点的指标(previous)，还有指向目前节点的指标(currrent)。如果list指向到要搜寻的链结串列的头，并且n是要删除的整数，那麽下面的回圈就可以实现第一步

for(cur = list, prev = NULL; cur != NULL && cur->value != n; prev = cur, cur = cur->next)

到这里我们也可以看出一件事情，也就是使用for回圈的方便之处，直接在回圈叙述中执行想要的操作，当循环停止时，cur指向要删除的节点，而prev指向前一个节点，下面会演示整个流程

假设有一链结串列，含有30,40,20,10

假设我们想要删除的整数为20，那麽目标就是删除第三个节点，在执行完cur = list, prev= NULL之後，cur指向链结串列中第一个节点

接着进入for回圈的条件判断，cur目前正指向节点30，因此cur != NULL成立，cur->value != n，这里cur指向节点的值为30，但目标为20，因此条件成立。两个条件皆成立，执行prev = cur, cur = cur->next後，我们会看到指标prev追踪在cur的後方。

再次进入for回圈中的条件判断，cur目前正指向节点40。因此cur != NULL成立，cur->value != n，这里cur指向节点的值为40，但目标为20，因此条件成立。两个条件皆成立，执行prev = cur, cur = cur->next

再次进入for回圈中的条件判断，cur目前正指向节点20，因此cur != NULL成立，cur->val != n，这里cur指向的节点值为20，目标为20，此条件不成立。两者条件需要皆成立才会执行for回圈的动作，因此for回圈终止。

接下来，根据步骤2，改变前一个节点，使他绕过删除的节点，为以下操作

prev->next = cur->next

使前一个节点中的指标指向了目前指标後面的节点

接着进行步骤3，释放目前节点(指向要删除的节点)的记忆体空间

free(cur);

而下面的函式所使用的策略就如同上面所演示，在给定指向链结串链的指标，和要删除的整数n，delete_from_list就会删除含有n的第一个节点(有可能很多节点都含有整数n)。如果没有结点包含整数n，则函式甚麽都不做，无论哪一种情况，皆会回传指向链结串列的指标。

struct node* delete_from_list(struct node* list, int n)
{
    struct node *cur, *prev;
    for(cur = list, prev = NULL; cur != NULL && cur->value != n; prev = cur, cur = cur->next);
    if(cur == NULL)
    {
        return list;
    }
    if(prev == NULL)
    {
        list = list->next;
    }
    else
    {
        prev->next = cur->next;
    }
    free(cur);
    return list;
}

另一种作法为使用搜寻结点的函式，可以将删除节点的函式写得更加简化，同样的，传入的链结串列第一个节点为空结点。

void list_delete(NODE *L, int val)
{
    NODE *target = search_list(L, val);
    NODE *temp = NULL;
    for (temp = L; temp->next != target; temp = temp->next);
    temp->next = target->next;
    free(target);
}

参考资料: 大话数据结构，C语言程序设计现代方法第2版，Introduction of algorithms 3rd，图片源於网路