数据结构自学Day5--链表知识总结

链表结构

常见的链表结构包括以下几种：

1.单向，双向

2.带头，不带头  （哨兵位的头节点，不存储有效数据，或者称为“哑节点”） 

3. 循环、非循环

常用链表以下两种：

       无头单向非循环链表：1、 oj题中常出现 2、基本不会单独作为链表使用 3、使用：其他数据结构的一部分：哈希表

        带头双向循环链表：特点结构复杂，操作简单！

那么关于这里带头双向循环链表的增删查改如何实现呢？

首先我们要初始化一个双向链表，这个链表只有一个节点，节点的next指向自己，prev也指向自己，当然我们得先产生一个节点！

产生一个新的节点：BuyNewNode

SListNode* BuyNewNode(SLDataType val){
    SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
    NewNode->Next = NULL;
    NewNode->Prev = NULL;
    NewNode->Val = val;
    return NewNode;
}

双向链表的初始化：SList_Init

void SList_Init(SListNode** Pphead,SLDataType val){
    assert(Pphead);
    SListNode* NewNode = BuyNewNode(val);
    *Pphead = NewNode;
    (*Pphead)->Next = *Pphead;
    (*Pphead)->Prev = *Pphead;
}

双向链表的打印：SList_Print

void SList_Print(SListNode** Pphead){
    assert(Pphead);
    SListNode* copy_head = *Pphead;
    while (copy_head)
    {
        printf("%d ->",copy_head->Val);
        copy_head =copy_head->Next;
        if(copy_head == *Pphead){
            break;
        }
    }
    printf("NULL\n");
}

然后就是我们对链表结构的常用操作：

链表的尾插：

1、链表为空，初始化链表

2、链表不为空，尾插新节点，旧节点指向新节点，新节点指向头节点，头节点指向新节点

尾插 PushBack函数 代码实现：

void PushBack(SListNode** Pphead,SLDataType val){
    assert(Pphead);
    if(*Pphead == NULL){
        SList_Init(Pphead,val);
    }
    else{
        SListNode* NewNode = BuyNewNode(val);
        SListNode* tail = (*Pphead)->Prev;
        tail->Next = NewNode;
        NewNode->Prev = tail;
        NewNode->Next = (*Pphead);
        (*Pphead)->Prev = NewNode;
    }
    return;
}

链表的头插：

1、链表为空，初始化链表

2、链表不为空，头插新节点，头节点变为新插入的节点，尾节点需要指向新节点！新节点指向尾节点

头插 PushFront函数 代码实现：

//头插
void PushFront(SListNode** Pphead,SLDataType val){
    assert(Pphead);
    if(*Pphead == NULL){
        SList_Init(Pphead,val);
    }
    else{
        SListNode* copy_head = *Pphead;
        SListNode* NewNode = BuyNewNode(val);
        NewNode->Prev = copy_head->Prev;
        (copy_head->Prev)->Next = NewNode;
        copy_head->Prev = NewNode;
        NewNode->Next = copy_head;
        *Pphead = NewNode;
    }
    return;
}

链表的尾删：

1、链表为空，或者链表只有一个节点，直接返回空指针

2、链表不为空，删除尾节点，头节点指向尾节点的前一个节点，尾节点的前一个节点指向头节点

尾删 PopBack 函数 代码实现：

//尾删

void PopBack(SListNode** Pphead){
    assert(Pphead);
    if(*Pphead == NULL || (*Pphead)->Next == *Pphead){
        *Pphead  =NULL;
        return;
    }
    else{
        SListNode* tail = (*Pphead)->Prev;
        (tail->Prev)->Next = *Pphead;
        (*Pphead)->Prev = tail->Prev;
        free(tail );
    }
    return;
}

链表的头删：

1、链表为空，或者链表只有一个节点，直接返回空指针。

2、链表不为空，删除投节点，头节点的下一个节点指向尾节点，尾节点的指向头节点的下一个节点。

头删 PopFrront 函数 代码实现：

//头删
void PopFront(SListNode** Pphead){
    assert(Pphead); 
    if(*Pphead == NULL || (*Pphead)->Next == *Pphead){
        *Pphead = NULL;
        return;
    }
    else{
        SListNode* copy_head = *Pphead;
        (copy_head->Prev)->Next = copy_head->Next;
        (copy_head->Next)->Prev = copy_head->Prev;
        *Pphead = copy_head->Next;
        free(copy_head);
    }
    return;
}

链表任意位置的删除和插入：

        我们已经考虑两种特殊情况的插入和删除，剩下就是中间节点的插入和删除，思路很简单：

要删除的节点的前一个节点和删除节点的后一个节点相连。

要插入的节点的前一个节点和插入节点的后一个节点相连

任意位置的插入代码实现如下：

//任意位置的插入！

void SListInsert(SListNode** Pphead,SLDataType pos,SLDataType val){
    assert(Pphead); 
    if(*Pphead == NULL){
        PushBack(Pphead,pos);
        return;
    }
    SListNode* copy_head = *Pphead;
    while (copy_head->Val != pos)
    {
        copy_head =copy_head->Next;
        if(copy_head == *Pphead){
            return;
        }
    }
    SListNode* NewNode = BuyNewNode(val);
    (copy_head->Next)->Prev = NewNode;
    NewNode->Next = (copy_head->Next);
    copy_head->Next = NewNode;
    NewNode->Prev = copy_head;
    return;
}

任意位置的删除代码：

void SListDelete(SListNode** Pphead,SLDataType pos){
    assert(Pphead); 
    if(*Pphead == NULL || (*Pphead)->Val == pos){
        PopFront(Pphead);
        return;
    }
    SListNode* copy_head = *Pphead;
    while (copy_head->Val != pos)
    {
        copy_head =copy_head->Next;
        if(copy_head == *Pphead){
            return;
        }
    }
    (copy_head->Prev)->Next = copy_head->Next;
    (copy_head->Next)->Prev = copy_head->Prev;
    free(copy_head);
    return;
}

链表查找指定的节点，SListFind函数实现：

SListNode* SListFind(SListNode** Pphead,SLDataType val){
    assert(Pphead); 
    if(*Pphead == NULL){
        printf("空链表\n");
        return NULL;
    }
    SListNode* copy_head = *Pphead;
    while (copy_head->Val != val)
    {
        copy_head =copy_head->Next;
        if(copy_head == *Pphead){
            return NULL;
        }
    }
    return copy_head;
}

链表的回收：最后链表不再使用之后我们要回收内存：

        这里非常需要注意双向链表的节点回收时，头节点需要最后进行回收，因为尾节点指向了头节点！

代码实现：

void SListDestroy(SListNode** Pphead){
    if (Pphead == NULL || *Pphead == NULL) {
        return;
    }

    SListNode* head = *Pphead;
    SListNode* cur = head->Next;

    // 如果只有一个节点
    if (cur == head) {
        free(head);
        *Pphead = NULL;
        return;
    }

    // 有多个节点，循环释放直到回到 head
    while (cur != head) {
        SListNode* next = cur->Next;
        free(cur);
        cur = next;
    }

    free(head);
    *Pphead = NULL;
}