[数据结构与算法]数据结构考试要求-第二章 双向链表

第二章 双向链表

单向链表的缺点

• 找链表的最后一个节点的时间复杂度为O(n)，不容易
• 头插，头删操作中，找当前节点的前一个结点需要借助另一个指针辅助
  总的来说就就是操作有限制
  双向链表就解决了这些缺点

双向链表结构体中新增

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

双向链表的实现

带头结点，省去了**二级指针

LTNode * ListInit();                                // 初始化链表
void ListPrint(LTNode * phead);                     // 打印链表
void ListDestroy(LTNode* phead);                    // 销毁链表
void ListPushBack(LTNode* phead, LTDataType x);     // 尾插法
void ListPopBack(LTNode* phead, LTDataType x);      // 尾删
void ListPushFront(LTNode* phead, LTDataType x);    // 头插法
void ListPopFront(LTNode* phead, LTDataType x);     // 头删法
LTNode * ListFind(LTNode* phead, LTDataType x);     // 查找元素节点
void ListInsert(LTNode* phead, LTDataType x);       // 插入
void ListErase(LTNode* phead);                      // 删除

初始化

LTNode * ListInit() {
    LTNode * phead = (LTNode *)malloc(sizeof(LTNode));
    phead->prev = phead;
    phead->next = phead;
    return phead;
}

链表打印

void ListPrint(LTNode * phead) {
    LTNode * cur = phead->next;
    while (cur != phead) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

销毁链表

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

尾插法

void ListPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode * tail = phead->prev;
    LTNode * newNode = (LTNode* )malloc(sizeof(LTNode));
    newNode->data = x;
    newNode->prev = tail;
    newNode->next = phead;
    tail->next = newNode;
    phead->prev = newNode;
}

尾删

void ListPopBack(LTNode* phead, LTDataType x) {
    assert(phead);
    assert(phead->next != phead);
    LTNode * tail = phead->prev;
    tail->prev->next = phead;
    phead->prev = tail->prev;
    free(tail);
}

头插法

void ListPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode * newNode = CreateListNode(x);
    LTNode * cur = phead->next;
    phead->next = newNode;
    cur->prev = newNode;
    newNode->prev = phead;
    newNode->next = cur;
}

头删

void ListPopFront(LTNode* phead, LTDataType x) {
    assert(phead);
    assert(phead->next != phead);
    LTNode * cur = phead->next;
    phead->next = cur->next;
    cur->next->prev = phead;
    free(cur);
}

查找

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

插入

void ListInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode * newNode = CreateListNode(x);
    pos->prev->next = newNode;
    newNode->prev = pos->prev;
    newNode->next = pos;
    pos->prev = newNode;
}

删除

void ListErase(LTNode* pos) {
    LTNode * prev = pos->prev;
    LTNode * next = pos->next;
    prev->next = next;
    next->prev = prev;
    free(pos);
}

第二章总结

顺序表和链表各有优势，很难说谁更优
相辅相成的两个结构

顺序表

• 优点：支持随机访问，需要随机访问结构算法可以很好使用，cpu高速缓存命中率高
• 缺点：头部中部插入删除时间效率较低On，连续的物理空间，空间不够了需要扩容

链表（带头双向循环链表）

• 优点：任意位置插入删除效率高O1，按需申请释放空间
• 缺点：不支持随机访问（按照下标访问），意味着一些排序，二分查找等这些不能用。链表存储一个值的同时也要存储指针，有一定的消耗，cpu高速缓存命中率低

后续 栈和队列