Introduction

雙向鏈結串列與單向鏈結串列相比，雙向鏈結串列多了一個指向前一個節點的指標

並且最後一個節點會重新指回head節點，head節點也會指向最後一個節點

Methods

以下為雙向鏈結串列常見的操作

Insertion：加入節點
Deletion：刪除節點
Search：查詢該節點是否存在於雙向鏈結串列
Reverse：反轉雙向鏈結串列

Time Complexity

Operation	Time Complexity	Worst Time Complexity	Space Complexity
Insertion	O(1)	O(n)	O(1)
Deletion	O(1)	O(n)	O(1)
Search	O(1)	O(n)	O(1)
Reverse	O(n)	O(n)	O(1)

Doubly Circular Linked List Implementation

結構定義

Insertion()

找到需要插入的位置後，需要改變更改ptr、prev、current指標的指向

Deletion()

找到要刪除的節點後，先判斷是否有找到資料，之後才改變prev和current指標

假設我們要刪除儲存Peter的節點：

Search()

判斷是否有合適的節點

Reverse()

為了交換每個節點的prev和next節點，我們可以先將prev指向next所指向的節點，而next指向暫時新增的節點，這樣就可以完成每個節點的交換，最後因為一開始current是設為head->next，所以並沒有修改到head的prev和next節點，因此最後再修改head的prev和next節點

完整的程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void initFunction(void);     /* 初始化串列，建立一空節點為HEAD */
void insertFunction(void);   /* 插入函數 */
void sortFunction(void);     /* 排序函數 */
void deleteFunction(void);   /* 刪除函數 */
void displayFunction(void);  /* 輸出函數 */
void modifyFunction(void);   /* 修改函數 */
void flushBuffer(void);      /* 清空緩衝區函數 */
void insertAt(void);
int search(char*);
void reverseList(void);
struct student* CreateList(void);
struct student* Concat(struct student*);

struct student {
    char name[20];          /* 姓名 */
    int score;              /* 分數 */
    struct student* llink;  /* 節點左鏈結 */
    struct student* rlink;  /* 節點右鏈結 */
};

struct student* ptr, * head, * tail, * currentN, * prev;

int main()
{
    char option1;
    char name[20];
    int position;

    initFunction();
    while (1) {
        printf("\n ****************************************\n");
        printf("              1.insert\n");
        printf("              2.Insert node at a particular position\n");
        printf("              3.delete\n");
        printf("              4.display\n");
        printf("              5.Search for an element in the list\n");
        printf("              6.Reverse the list\n");
        printf("              7.Concate Two Linked Lists\n");
        printf("              8.modify\n");
        printf("              9.quit\n");
        printf(" ****************************************\n");
        printf("   Please enter your choice (1-9)...");
        option1 = getchar();
        while (getchar() != '\n')
            continue;
        switch (option1) {
        case '1':
            insertFunction();
            break;
        case '2':
            insertAt();
            break;
        case '3':
            deleteFunction();
            break;
        case '4':
            displayFunction();
            break;
        case '5':
            printf("\nEnter name: ");
            scanf_s("%s", name, 20);
            position = search(name);
            if (position == -1)
            {
                printf("\nElement not found\n");
            }
            else
            {
                printf("\nElement found at position %d\n", position);
            }
            break;
        case '6':
            reverseList();
            printf("\nList reversed\n");
            break;
        case '7':
            head = Concat(head);
            displayFunction();
            break;
        case '8':
            modifyFunction();
            break;
        case '9':
            printf("\n");
            return 0;
        }
    }
}

void initFunction(void)  /* 設一HEAD，將左右鏈結皆指向本身 */
{
    ptr = (struct student*)malloc(sizeof(struct student));
    strcpy_s(ptr->name, "0");
    ptr->llink = ptr;
    ptr->rlink = ptr;
    head = ptr;
    tail = ptr;
}

void insertFunction(void)
{
    char sTemp[4];
    ptr = (struct student*)malloc(sizeof(struct student));
    printf("\n Student name : ");
    scanf_s("%s", ptr->name, 20);
    printf(" Student score: ");
    scanf_s("%d", &ptr->score);
    flushBuffer();
    sortFunction();
}

void sortFunction(void)
{
    prev = head;
    currentN = head->rlink;
    while ((currentN != head) && (currentN->score >= ptr->score)) {
        prev = currentN;
        currentN = currentN->rlink;
    }
    ptr->rlink = currentN;
    ptr->llink = prev;
    prev->rlink = ptr;
    currentN->llink = ptr;
}

void deleteFunction(void)
{
    char delName[20];
    int count = 0;

    if (head->rlink == head)
        printf(" No student record\n");
    else {
        printf("\n Delete student name: ");
        scanf_s("%s", delName, 20);
        flushBuffer();
        prev = head;
        currentN = head->rlink;
        while ((currentN != head) && (strcmp(currentN->name, delName) != 0)){
            prev = currentN;
            currentN = currentN->rlink;
        }
        if (currentN != head) {
            prev->rlink = currentN->rlink;
            currentN->rlink->llink = prev;
            free(currentN);
            printf(" Student %s has been deleted\n", delName);
        }
        else
            printf(" Student %s not found\n", delName);
    }
}

void modifyFunction(void)
{
    int count = 0;
    char nTemp[20], sTemp[4];

    if (head->rlink == head)
        printf(" No student recond\n"); /* 無資料顯示錯誤 */
    else {
        printf("\n Modify student name: ");
        scanf_s("%s", nTemp, 20);
        flushBuffer();
        prev = head;
        currentN = head->rlink;
        while ((currentN != head) && (strcmp(currentN->name, nTemp) != 0)) {
            prev = currentN;
            currentN = currentN->rlink;
        }
        if (currentN != head) {
            printf(" **************************\n");
            printf("  Student name : %s\n", currentN->name);
            printf("  Student score: %d\n", currentN->score);
            printf(" **************************\n");
            printf(" Please enter new score: ");
            scanf_s("%s", sTemp, 20);
            flushBuffer();
            prev->rlink = currentN->rlink;
            currentN->rlink->llink = prev;
            free(currentN);
            //重新加入
            ptr = (struct student*)malloc(sizeof(struct student));
            strcpy_s(ptr->name, nTemp);
            ptr->score = atoi(sTemp);
            ptr->rlink = head;
            prev = head;
            currentN = head->rlink;
            while ((currentN != head) && (currentN->score > ptr->score)) {
                prev = currentN;
                currentN = currentN->rlink;
            }
            ptr->rlink = currentN;
            ptr->llink = prev;
            prev->rlink = ptr;
            currentN->llink = ptr;
            printf("%s student record(s) modified\n", nTemp);
        }
        else     // 找不到資料則顯示錯誤
            printf(" Student %s not found\n", nTemp);
    }
}

void displayFunction(void)
{
    int count = 0;

    if (head->rlink == head)
        printf(" No student record\n");
    else {
        printf("\n  NAME                SCORE\n");
        printf(" ---------------------------\n");
        currentN = head->rlink;
        while (currentN != head) {
            printf("  %-20s %3d\n", currentN->name, currentN->score);
            count++;
            currentN = currentN->rlink;
        }
        printf(" ---------------------------\n");
        printf(" Total %d record(s) found\n", count);
    }
}

void insertAt(void) {
    int position;
    printf("\n Enter position to insert: ");
    scanf_s("%d", &position);

    /* 檢查位置的合法性 */
    if (position < 1) {
        printf(" Error: Invalid position\n");
        return;
    }

    /* 移動到指定位置的前一個節點 */
    prev = head;
    currentN = head->rlink;
    int count = 1;
    while (currentN != head && count < position) {
        prev = currentN;
        currentN = currentN->rlink;
        count++;
    }

    /* 檢查是否到達指定位置 */
    if (currentN == head && count < position) {
        printf(" Error: Position out of range\n");
        return;
    }

    /* 創建新節點並插入到指定位置 */
    struct student* newNode = (struct student*)malloc(sizeof(struct student));
    printf("\n Student name : ");
    scanf_s("%s", newNode->name, 20);
    printf(" Student score: ");
    scanf_s("%d", &newNode->score);
    flushBuffer();
    newNode->rlink = currentN;
    newNode->llink = prev;
    prev->rlink = newNode;
    currentN->llink = newNode;
}

int search(char* name) {
    struct student* temp = head;
    int count = 0;
    if (temp == NULL)
    {
        return -1;
    }
    while (temp != NULL)
    {
        if (strcmp(temp->name, name) == 0)
        {
            return count;
        }
        count++;
        temp = temp->rlink;
    }
    return -1;
}

void reverseList(void) {
    struct student* temp = NULL;
    struct student* current = head->rlink; // 从链表第一个有效节点开始
    while (current != head) // 当前节点不是头节点时
    {
        temp = current->llink; // 交换当前节点的左右链
        current->llink = current->rlink;
        current->rlink = temp;
        current = current->llink; // 移动到下一个节点
    }
    temp = head->llink; // 交换头节点的左右链
    head->llink = head->rlink;
    head->rlink = temp;
}

struct student* CreateList(void) {
    int num;
    printf("\n Enter the number of students you want to add to the list: ");
    scanf_s("%d", &num);
    flushBuffer();
    for (int i = 1; i <= num; i++) {
        printf("\n=======================================");
        printf("\nEnter Data for Node %d : ", i);
        printf("\n Student name: ");
        ptr = (struct student*)malloc(sizeof(struct student));
        scanf_s("%s", ptr->name, 20);
        printf(" Student score: ");
        scanf_s("%d", &ptr->score);
        flushBuffer();
        sortFunction();
    }
    printf("\nList Created");
    return ptr;
}

struct student* Concat(struct student* L1) {
    struct student* L2, *ptr, *temp;
    if (L1->rlink == head) {
        printf("\n------- Insertion for List 1 --------\n");
        L1 = CreateList();
    }
    printf("\n------- Insertion for List 2 ---------\n");
    L2 = CreateList();
    printf("\n-------- After Concatenation ---------\n");
    if (L1->rlink != head)
    {
        if (L2 != NULL)
        {
            ptr = L1->rlink;
            while (ptr->rlink != head)
            {
                ptr = ptr->rlink;
            }
            ptr->rlink = L2;
            L2->llink = ptr;
            temp = L2;
            while (temp->rlink != L2)
            {
                temp = temp->rlink;
            }
            temp->rlink = head;
        }
    }
    else
    {
        L1 = L2;
    }
    return L1;
}

void flushBuffer()
{
    while (getchar() != '\n')
        continue;
}

雙向鏈結串列的優點

可以查詢每個節點的前一個節點以及後一個節點

雙向鏈結串列的缺點

實現更複雜，應該會需要處理兩個指標
因為有兩個指標，所以需要更多空間

Doubly Circular Linked List

Table of contents