数据结构-链表

前情提要：数据结构-线性表 | 4FGR の Blog

单链表

​ 线性表的链式存储，其存储并非是一段连续的存储空间，为了能够访问链表中的元素，每个链表节点不仅存储了元素信息，还需要存放一个指向其后继的指针。（本文所有链表实现均有头节点）

结构体定义

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

基本操作的实现

初始化

// 初始化链表
bool initList(LinkedList &L){
    L = (LNode*)malloc(sizeof(LNode));
    if(L == NULL){
        return false;
    }
    L->next = NULL;
    return true;
}

检查空表

即检查头节点的后继是否为空

//检查链表是否为空
bool isEmpty(LinkedList L){
    return L->next == NULL;
}

查找

//查找元素
LNode* Find(LinkedList L, int taget){
    LNode *p = L->next;
    int i = 1;
    while(p && p->data != taget){
        p = p->next;
    }
    return p;  //找到返回指针，否则返回NULL
}

插入

对于插入节点后继非空的情况下，插入方式如图

插入方法的代码如下:

//在位置postion后插入元素
void Insert(LinkedList L, LNode *position, int e){
    LNode *p = (LNode*)malloc(sizeof(LNode));
    p->data = e;
    p->next = position->next; //改变p的后继
    position->next = p;	//改变position的后继
}

删除

对于删除节点后继非空的情况下，删除方式如图

删除方法的代码如下:

//删除元素target
void Delete(LinkedList L, int target){
    LNode *p = L;
    LNode *q = p;
    while(p && p->data != target){
        q = p;
        p = p->next;
    }
    if(p){
        q->next = p->next;
        free(p);
    }else{
        printf("未找到目标元素");
    }
}

销毁

//销毁链表
void DeleteList(LinkedList &L){
    LNode *p = L;
    LNode *q = p;
    while(p){
        q = p;
        p = p->next;
        free(q);
    }
    L = NULL;
}

建立单链表

头插法

//前插法建立链表
void CreateListFront(LinkedList &L, int n){
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    for(int i = 0; i < n; i++){
        int data;
        scanf("%d", &data);
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->data = data;
        p->next = L->next;
        L->next = p;
    }
}

尾插法

//尾插法建立链表
void CreateListRear(LinkedList &L, int n){
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r = L;
    for(int i = 0; i < n; i++){
        int data;
        scanf("%d", &data);
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->data = data;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

双链表

相比于单链表而言，双链表（双向链表）的定义中多了前驱pre，这对于任意一个非头节点而言，都可以直接访问其前驱节点。

结构体定义

typedef struct DNode{
    int data;
    struct DNode *prior, *next;
}DNode, *DLinkedList;

基本操作实现

相比于单链表而言，差异在于对前驱和后继的处理，这里仅对插入和删除方法作出具体实现:

插入

//在位置p后插入元素
void Insert(DLinkedList l, DNode *position, int e){
    DNode *p = (DNode*)malloc(sizeof(DNode));
    p->data = e;
    p->next = position->next; //注意改变指针域的顺序
    p->prior = position;
    position->next = p;
    if(p->next){
        p->next->prior = p;
    }
}

删除

//删除元素target
void Delete(DLinkedList L, int target){
    DNode *p = L;
    DNode *q = p;
    while(p && p->data != target){
        q = p;
        p = p->next;
    }
    if(p){
        q->next = p->next;
        if(p->next){
            p->next->prior = q;
        }
        free(p);
    }
    else{
        printf("未找到目标元素");
    }
}

循环链表

单链表和双链表都有循环链表形式，对比之前链表的差异在于其最后节点的后继非空，而是指向头节点或第一个节点(无表头时)。特别地，对于双链表，还得注意头节点或第一个节点的前驱指向最后一个节点。

此时，对于类似查找、插入、删除等方法的实现，

应当遍历链表的条件不再为p->next != NULL

而是 p->next != L (p从L->next开始时)

扩展

链表求表长

对于求出链表的表长，我们有两种方式，一种是通过简单的遍历得出，还有一种我们可以在链表的定义中加入表长信息，例如

typedef struct LNode{
    int data;
    struct LNode;
}LNode;
typedef struct{
    LNode *head; //存储链表头节点
    int length;  //存储链表的表长
}LinkedList;

当然，这会导致基本操作的实现要发生一定的变化，还需要记住基本操作中使表长改变的操作中，length需要被改变。

其他

与上述添加length类似，我们还可以往LinkedList添加我们想要的成员，

例如，我们可以通过添加尾节点rear，使得对尾部节点的访问更便利。

因此，从实际需求出发，出于便利的需要，我们可以往链表中添加理想的成员。