我们继续讲链表……(‘-ωก̀ )

链表

链表是一种用来储存元素集合的数据结构，它具有以下特性：

  • 节点由两部分组成，我称之为数据域和指针域，数据域存放你想通过链表储存的数据，而指针域存放指针
  • 元素通过指针依次相连，即通过指针来指向其他元素
  • 最后一个元素的指针为空（NULL）
  • 在执行过程中，链表的长度可以自由伸缩
  • 链表的长度可以是要求的任意长度，除非系统内存耗尽
  • 它不会浪费内存空间（相对于开辟数组来说），但是需要额外的空间存放指针。

链表的抽象数据类型/ADT

主要的操作：

  • 插入（Insert）：将一个元素插入链表中
  • 删除（Delete）：删除并返回链表中指定位置上的元素

辅助的操作：

  • 撤销链表（Delete List）：删除链表中的所有元素
  • 计数（Count）：返回链表的元素个数（即链表长度）
  • 查找（Search)：从链表的表尾开始查找第n个节点

为什么需要链表？

在学习链表之前，我们一般使用数组来储存数据集合，那么，为什么我们需要链表呢？

我们首先来回顾一下数组。

数组

数组是指一片连续的内存块被分配给用户以储存数组元素，即数组是在内存中占据一组连续地址的储存单元。通过输入数组的下标，我们可以快速的访问数组中的任何元素。其时间复杂度为常数O(1)。

为了访问数组元素，元素的储存地址通常以相对其起始地址的偏移量计算得到，而这个计算需要通过一个乘法运算，即根据数据类型确定一个元素的大小乘以其被访问元素的下标以得到其偏移量，最后将偏移量与起始地址相加。整个过程包括一个乘法计算和加法计算，故数组的访问只需要一个常数时间即可完成。

优势
  • 简单、易使用。直接声明即可创建数组
  • 访问元素速度快
缺点
  • 固定大小：数组是静态的，在使用数组前就需要给它分配一个固定的大小
  • 占据一个连续的储存空间，有时候可能无法获得一个足够大的连续内存去储存创建的数组
  • 复杂的定位插入运算：在数组中插入或删除元素的操作十分麻烦，需要把在插入位置后的所有元素都向后移动一位，最坏的结果时间复杂度达到了O(n)。

链表的优势

链表的最大优势是在常数时间内实现扩张。如果使用数组，有时候会出现内存不够的情况，这个时候你可以一开始分配一个内存很大的数组，但是如果你没有把数组全部塞满就会造成内存的浪费。所以这时候我们引入链表，我们首先为一个元素分配储存空间，然后轻松添加新元素。

链表的缺点

链表的主要缺点是单个元素的访问时间。

数组具有随机性，可以实现随机访问，访问每个数组元素所花费的时间相同。但是链表只能实现顺序访问，最坏的情况下访问链表中一个元素要花费O(n)的时间。尽管动态分配的储存分配是链表的一个强大优势，但与此伴随的是高储存开销。

最后链表还需要额外储存指针参数，浪费了储存空间。

单链表

我们常说的链表是指单链表。单链表包括一组节点，一个头节点和一个指向NULL的尾节点，每个节点有一个数据域和指针域。

下面我们声明一个简单的整形链表。

struct ListNode{
    int data;
    struct ListNode* next;
}

链表的基本操作

主要有：

  • 遍历链表
  • 在链表中插入一个元素
  • 在链表中删除一个元素

下面我们来依次介绍对应的操作要怎么实现。

遍历

遍历涉及的操作很简单，我不多介绍了。遍历的作用主要就是用来计算数组长度或者依次显示数据，进而可以用来查找特定的节点。当遍历的节点指向的下一个节点为NULL时，遍历结束。

以下是代码的实现。

int ListLength(struct ListNode*head){
    //这里新定义了一个指针指向头节点，是为了不改变头节点的值，相当于拷贝了一份头节点的副本
    struct ListNode*current=head;
    int count=0;
    
    while(current!=NULL){
        count++;
        current=current->next;
    }
    return count;
}

扫描大小为n的列表，时间复杂度是O(n)。只创建了两个临时变量，空间复杂度为O(1)。

插入

对于单链表的插入有三种情况。

  • 在链表首元节点前插入一个新节点
  • 在链表尾元节点后插入一个新节点
  • 在链表中间部分插入一个新节点
在头部插入节点

这时只需要更新一个节点的指针域，即申请一个新节点并修改其指针域指向原头结点，然后更新头指针指向新首元节点皆可以了。

在尾部插入节点

这个时候我们需要修改两个节点的指针域。

首先申请一个新节点，将其指针域的指针修改为NULL，然后修改原尾元节点使其指针指向新节点即可。

假如给定了我们一个想要插入节点的位置，我们仍然只需要修改两个指针的指针域。

  • 如果我们想要在第3个节点前插入新节点，那么我们首先要找到第2个节点。这意味着我们需要遍历两个节点后才能进行插入操作。为了便于描述，我们将第2个节点称为位置节点。新节点的指针域指向位置节点的下一个节点（即目标节点）
  • 首先创建一个新节点，使新创立的节点指针域指向目标节点。
  • 然后修改位置节点的指针域，使其指向新节点，这样我们便完成了中间节点的插入。

下面我们根据以上三种情况编写代码。

void InsertInLinkedList{struct ListNode**head, int data, int position}{
    //这里用到了指针的指针，是为了更改头指针指向的节点
    int k=1;
    struct ListNode*p,*q,*newNode;
    newNode=(ListNode*)malloc(sizeof(struct ListNode));
    if(!newNode){
        //如果新节点申请失败则报错，检查合法性，增强健壮性
        printf("Memory Error!");
        return;
    }
    newNode->data=data;
    p=*head;//p设置为头指针
    //在头部插入节点
    if(position==1){
        newNode->next=p;
        *head=newNode;
    }
    else{
        //遍历链表直到达到我们想要插入的位置为止
        while((p!=NULL)&&(k<position)){
            k++;
            q=p;
            p=p->next;
        }
        q->next=newNode;//这里有更好的方法实现这一点
        newNode->next=p;
    }
}

当然，我们也可以根据三种不同的情况实现三种不同的函数。

删除

与插入类似，链表的删除也有三种情况。

  • 删除首元节点
  • 删除尾元节点
  • 删除中间部分的一个节点

现在我们三种情况来讨论。

删除头节点

删除头节点一共需要两步。

  • 创建一个临时变量指向要删除的头节点。
  • 修改头指针指向下一个节点，然后撤销临时指针变量指向的首元节点（free操作）。
删除尾节点

同样的，我们删除尾节点时需要找到它的前驱节点。其实现分为三步。

  • 遍历列表找到前驱节点地址。我们需要两个指针变量指向尾元节点和尾元节点的直接前驱节点。
  • 更新前驱节点的指针域，将其置为NULL。
  • 撤销尾节点。
删除中间节点

删除中间节点和前面的步骤类似，具体体现为更新前驱节点的指针域为待删除节点所指向的下一个节点，其余步骤相同。

现在我们用代码来实现删除节点。

void DeleteNodeFromLinkedList(struct LinkNode**head, int position){
    int k=1;
    struct ListNode*p,*q;
    if(*head==NULL){
        //检查链表是否为空链表，此时仅一个节点
        print("List Empty");
        return;
    }
    p=*head;
    //删除首元节点
    if(position==1){
        *head=(*head)->next;
        free(p);
        return;
    }
    else{
        //遍历链表直到找到我们要删除的节点为止
        while ((p!=NULL)&&(k<position)){
            k++;
            q=p;
            p=p->next;
        }
        if(p==NULL){
            //到达表尾
            printf("Position does not exist.");
        }
        else{
            //被删除的元素位于表中
            q->next=p->next;
            free(p);
        }
    }
}

以上算法的时间复杂度为O(n)，空间复杂度为O(1)。

以上是单链表的介绍。

双链表

双链表是指指针域上包含两个分别指向左右两边的前后驱节点指针的链表。相比单链表，双链表拥有更多优势。我们只需要得到双链表的一个节点，就可以访问整条链表上的所有元素。比如在单链表中得到一个节点，我们无法删除这个单个节点，因为这需要单节点的前驱节点才可以操作。而双链表则不然，我们可以通过元素的左指针找到它的直接前驱。

双链表也存在不足，主要体现在：

  • 每个节点都要求增加一个指针域，即需要更多的空间资源。
  • 插入和删除节点需要花费的时间更长（因为新增了一个另一个方向的指针）

除此之外，双链表的操作基本和单链表类似。如果掌握了单链表的操作，双链表也不是什么难事。

下面我们来创建一个简单的双链表模板。

struct DLLNode{
    int data;
    struct DLLNode*next;
    struct DLLNode*prev;
}
双链表的插入

双链表的插入操作与单链表一样可分为三种，即在头部、尾部和中间分别插入新节点。

在头部插入节点

双链表插入的步骤与单链表大致相同，唯一不同的地方就是此时多了一个左指针。我们也可以将插入步骤分为两步。

  • 申请一个新节点，把新节点的左指针置为NULL，右指针指向原头结点。
  • 修改原首元节点使其左指针指向新节点，并把头指针指向新节点即可。
在尾部插入节点

同上，也可分为两个步骤。

  • 申请新节点并遍历至链表尾元节点，修改新节点的左指针指向原尾元节点，右指针置为NULL。
  • 修改原尾节点的右指针指向新节点即可。
在中间插入节点

在中间插入节点可能有些复杂，因为要涉及到三个节点和四个指针，这里我们举例来说明更好理解。

假设有中间相邻节点a和b，现在要在b节点前插入p节点，伪代码示例如下。

p.prev=a;//设置p的左右节点指向a，b
p.next=b;

a.next.prev=p;//设置b的左指针指向p
b.prev.next=p;//设置a的右指针指向p

现在我们来编写代码来实现这三种情况的插入。

void DLLInsert(struct DLLNode**head, int data, int position){
    int k=1;
    struct DLLNode*temp,*newNode;//这里多了一个临时变量
    if(!newNode){
        //如果内存判断错误就退出
        printf("Memory Error");
        return;
    }
    newNode->data=data;//装填数据
    if(position==1){
        //在头部插入节点
        newNode->prev=NULL;
        newNode->next=*head;
        
        if(*head)
            (*head)->prev=newNode;//如果头节点存在，增强健壮性
        
        *head=newNode;//修改头指针指向新节点
        return;
    }
    temp=*head;
    while((k<position-1)&&temp->next!=NULL){
        //这里没有使用else语句，因为如果触发了if判断将在if块内就进行返回
        //所以没有必要再加else
        //这里遍历到了要操作的节点，注意这里循环结束的条件是position-1
        temp=temp->next;
        k++;//k为位置节点序号
        //此时temp即为待操作元素
    }
    if(k!=position-1){
        printf("Desired position does not exist.\n");
    }//如果在k到达position-1之前就退出循环，说明已经遍历到了表尾，所以不存在
    newNode->next=temp->next;//
    newNode->prev=temp;
    if (temp->next)
        //如果temp的右指针不为空，也就是不是尾节点的话
        temp->next->prev=newNode;
    
    temp->next=newNode;//实际上是在temp及其后驱节点间插入了元素
    return;
}
双链表的删除

删除的操作也分为三种情况：

  • 删除头节点
  • 删除尾节点
  • 删除中间节点
在头部删除节点

删除头部节点，我们主要分为两步。

  • 创建一个临时声明的指针变量，指向当前头节点。
  • 然后使头节点指针向后移动一位，并置头节点的左指针域为空，最后撤销临时变量指向的节点。
在尾部删除节点

删除尾元节点，比删除首元节点稍微复杂一点，具体分为三步。

  • 遍历链表，直到找到尾元节点。注意在这个过程中需要始终保持当前所指结点和其前驱节点的地址。也就是说，我们需要定义两个临时变量来储存地址。
  • 置尾元节点的前驱节点右指针域为空。
  • 删除当前所指结点/尾元节点。
在中间删除节点

我们一样分为两步。

  • 与删除尾元节点类似，在遍历期间始终保存当前节点的前驱节点地址。一旦找到了需要删除的节点，就通过修改其前驱节点的右指针使其指向所指结点的右指针域下一个节点，再修改所指结点的下一个指向元素左指针域使其指向被删除节点的前驱节点。
  • 释放所指结点

下面是实现的代码。

#include <stdio.h>
#include <stdlib.h>
struct DLLNode{
    int data;
    struct DLLNode *prev;
    struct  DLLNode *next;
};
void DLLDelete(struct DLLNode **head,int position){
    struct DLLNode *temp1,*temp2,*temp=*head;
    int k=1;
    
    if(*head==NULL){
        printf("List is empty");
        return;
    }
    if(position==1){//如果删除的是首节点
        *head=(*head)->next;
        if(*head!=NULL)
            (*head)->prev=NULL;
        free(temp);
        return;
    }
    
    while((k<position)&&temp->next!=NULL){
        temp=temp->next;
        k++;
    }
    if(k!=position-1){
        printf("Desired position does not exist.");
        return;
    }
    temp2=temp->prev;
    temp2->next=temp->next;
    if(temp->next)//如果删除的是中间的一个点
        temp->next->prev=temp2;
    
    free(temp);
    return;
}

循环链表

循环链表和前面的两种形式不同，它没有NULL指针域，即每个节点都有其后继节点。在循环链表中，头节点可以访问其所有链表。当几个进程正在轮流使用相同的计算机资源相同的时间时，我们必须确保在它们完成前没有其他进程访问该资源（轮询算法）。下面是一个循环链表的类型声明。

struct CLLNode{
    int data;
    struct CLLNode* Next;
}

（待更新……）

300470