数据结构：双向链表实现与算法分析

数据结构：双向链表实现与算法分析

一、实现双向链表

1. 双向链表查找

双向链表的查找操作与单链表类似，但可利用创建一个暂时的指针实现遍历。

函数形式：

ListNode* LTFind(ListNode* h, type x);

实现：

ListNode* LTFind(ListNode* h, type x) {
    if (LTEmpty(h)) {
        return NULL;
    }
    ListNode* p = h->next;
    while (p != h) {
        if (p->data == x) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

说明： 通过遍历来实现，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空。

2. 双向链表在指定位置插入

双向链表在指定位置插入分为双向链表在指定位置之前插入与双向链表在指定位置之后插入。

双向链表在指定位置之后插入

函数形式：

void LTInsert(ListNode* pos, type x);

实现：

void LTInsert(ListNode* pos, type x) {
    assert(pos);
    ListNode* p = pos->next;
    ListNode* newnode = LTcreat(x);
    pos->next = newnode;
    newnode->prev = pos;
    newnode->next = p;
    p->prev = newnode;
}

说明： 该函数用于在双向链表的指定节点 pos 之后插入新节点，核心逻辑是通过调整指针关系实现无缝插入。需先保存后继节点，防止原链表后半部分丢失。

双向链表在指定位置之前插入

函数形式：

void LTInsertfront(ListNode* h, ListNode* pos, type x);