【資料結構】 雙鏈表的簡單理解和基本操作

前言：本章主要內容是雙向回圈鏈表（即雙鏈表）的概念，和其基本操作：包括定義、創建、初始化、判空、尾插、頭插、尾刪、頭刪、插入、查找、銷毀等操作的具體實作，

1.為什么需要雙鏈表？

單鏈表的中間結點、尾結點查找麻煩，如果想對這些結點進行修改，就不得不進行遍歷操作，增加了演算法復雜度，

1.1雙鏈表的概念

第一個結點屬于多開辟的空間，為了方便頭插頭刪，后續結點為真正的鏈表內容，

1.2雙鏈表一個結點的內容

一個指向前面結點的指標

一個存盤資料的空間

一個指向后面結點的指標

2.雙鏈表的專案實作

2.1 雙鏈表的定義

代碼實作

typedef int LTDataType; 

typedef struct ListNode
{
    struct ListNode* prev;
    LTDataType data;
    struct ListNode* next;
}LTNode; 

思考下為何使用typedef？

如果一開始我們就確定了結構體中的變數型別，后續在專案程序中如果需要對這個變數型別進行調整，那么所需的操作是很繁瑣的，故使用typedef，后續若是需要修改，改動typedef就足夠了，

2.2 雙鏈表的創建

代碼實作

LTNode* BuyListNode(LTDataType elem)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if(newnode == NULL)
    {
        perror("錯誤原因:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

2.3 雙鏈表的初始化

需要改變phead，因為實參是一個一級指標，如果形參也只是一級指標，就屬于值傳遞了,函式內pphead的值改變并不會影響外面的實參，而初始化是需要修改實參的，所以傳二級指標

代碼實作

void ListInit(LTNode** pphead)
{
    assert(pphead); //pphead一定不能是空指標
    
    (*pphead) = BuyListNode(1); //隨機給一個值用來創建結點
    
    (*pphead)->prev = *pphead;
    (*pphead)->next = *pphead;
}

2.4 雙鏈表的判空操作

頭結點放的是無效資料，不需要判斷，只需要判斷就是頭結點之后(phead->next)的結點值是不是phead,原因:

當鏈表為空時候,就只剩下一個無效頭結點，即phead->next = phead(自己指向自己)，

當鏈表不為空時候,就有有效結點，即phead->next != phead，

代碼實作

bool ListEmpty(LTNode* phead)
{
    assert(phead); //phead不能為空
    
    return phead->next == phead; 
}

2.5 雙鏈表的元素數量查詢操作

代碼實作

size_t ListSize(LTNode* phead)
{
    assert(phead);
    size_t sum = 0;
    LTNode* cur = phead->next; //從頭結點之后開始遍歷(頭結點不存放資料)
    
    while(cur != phead) //當cur再次為phead時候,說明鏈表已經遍歷完畢.
    {
        sum++;
        cur = cur->next;
    }
    
    return sum;
}

2.6 雙鏈表的列印操作

結束條件就是到了最后一個元素，而最后一個元素的next指向首元素

代碼實作

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;

	while (cur != phead)//到了最后就是指向首元素
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("|完畢|\n");
}

2.7 雙鏈表的尾插

在尾插方面雙鏈表擁有對比單鏈表而言極大的優勢，不需要進行遍歷，只需通過改變**phead->prev**的指向即可，仔細看下圖理解一下為什么？

因為在雙向回圈鏈表結構中，**phead->prev**指向的就是尾結點的data，所以不需要遍歷！

實作思路：

1.創建新結點存盤資料

2.原尾結點與新結點進行相互鏈接

3.新結點與頭結點相互鏈接

代碼實作

void ListPushBack(LTNode* phead, LTDataType* elem)
{
    assert(phead);
    
    LTNode* tail = phead->prev;  //找到尾結點
    LTNode* newnode  = BuyListNode(elem); //創建新結點
    
    //原來尾結點和現在新結點鏈接
    tail->next = newnode;
    newnode->prev = tail;
    
    //新結點和頭結點鏈接
    phead->prev = newnode;
    newnode->next = phead;
}

2.8 雙鏈表的尾刪

有了尾插的基礎，思考尾刪就更容易了，步驟如下：

1.找到尾結點和倒數第二個結點

2.釋放尾結點

3.頭結點和倒數第二個結點鏈接

代碼實作

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(ListEmpty(phead)); //如果鏈表為空就不能洗掉.
    
    LTNode* tail = phead->prev;//尾結點
    LTNode* tail_prev = tail->prev;//倒數第二個結點
    
    free(tail);//釋放尾結點
    tail = NULL;
    
    tail_prev -> next = phead; //頭結點和倒數第二個結點連接
    phead->prev = tail_prev;
}

2.9 雙鏈表的頭插

這里注意一點，頭插，仍然不改變之前的phead，頭插是從第二個結點開始（即雙鏈表中第一個有效存盤資料的結點開始），

1.創建新結點存盤資料

2.新結點與頭結點后的第一個結點鏈接

3.第三步,新結點與頭結點鏈接

代碼實作

void ListPushFront(LTNode* phead, LTDataType* elem)
{
    assert(phead);
    
    LTNode* newnode  = BuyListNode(elem); //創建新結點存盤資料
    LTNode* Second_first = phead->next; //頭結點后的首結點.
    
    //新結點 與 頭結點后的首結點 鏈接
    Second_first ->prev = newnode;
    newnode->next = Second_first;
    
    //新結點與頭結點鏈接
    phead->next = newnode;
    newnode->prev = phead;
}

2.10 雙鏈表的頭刪

這里注意一點，頭刪，仍然不改變之前的phead，頭刪是從第二個結點開始（即雙鏈表中第一個有效存盤資料的結點開始），

1.頭結點與頭刪結點后的結點鏈接

2.釋放頭刪結點

代碼實作

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(!ListEmpty(phead)); //如果為空就無法洗掉
    LTNode* Front_second = phead->next->next;//頭刪結點后的結點
    LTNode* front = phead->next; //頭刪結點
    
    //連接
    phead->next = Front_second;
    Front_second->prev = phead;
    
    //釋放頭刪結點
    free(front);
    front = NULL;
}

2.11 雙鏈表的查找值操作

與單鏈表類似，直接遍歷

代碼實作

LTNode* ListFind(LTNode* phead,LTDataType elem)
{
    assert(phead);
    LTNode* cur = phead->next;
    while(cur != phead)
    {
        if(cur->data == elem)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

2.12 雙鏈表的插入操作

與之前的頭插類似，只是頭插特定是在頭結點后的第一個結點前進行插入，而任意位置前插入是在給定的pos結點之前插入，

代碼實作

void ListInsert(LTNode* pos,LTDataType elem) 
{
    assert(pos);
    
    LTNode* pos_prev = pos->prev;  //保存pos結點之前的結點
    LTNode* newnode = BuyListNode(elem); //創建新結點
    
    //新結點與pos鏈接
    newnode->next = pos;
    pos->prev = newnode;
    
    //新結點與原來pos之前的結點連接
    pos_prev->next= newnode;
    newnode->prev = pos_prev;
}

2.13 雙鏈表的洗掉操作

與之前的尾刪類似，只是尾刪洗掉的是尾結點，而任意位置洗掉的是我們給的結點pos，

代碼實作

void ListErease(LTNode* pos)
{
    assert(pos);
    
    LTNode* prev = pos-> prev; //保存pos 之前結點
    LTNode* next = pos->next;  //保存pos 之后結點
    
    free(pos);
    pos = NULL;
    
    prev->next = next;
    next->prev = prev;
}

2.14 雙鏈表的銷毀操作

遍歷進行釋放就行

代碼實作

void ListDestroy(LTNode* phead)
{
    assert(phead);
    
    LTNode* cur = phead->next;
    while(cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    
    free(cur);
    cur = NULL;
}

3.原始碼鏈接

雙鏈表的代碼實作

資料結構的雙鏈表內容到此設計結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我三連（點贊、收藏、關注）——做個手有余香的人，