基于链表的直接插入排序实现

基于链表的直接插入排序实现可以参考以下步骤：

1. 定义一个链表节点结构体，包含数据域和指向下一个节点和上一个节点的指针。

2. 定义一个链表类，包含头节点和尾节点指针，以及插入节点、删除节点等操作函数。

3. 定义一个直接插入排序函数，该函数接受一个链表对象作为参数，实现链表的直接插入排序。

4. 在直接插入排序函数中，首先将链表的第一个节点作为有序序列，然后从第二个节点开始遍历链表。

5. 对于每个遍历到的节点，将其从链表中删除，并在有序序列中找到合适的位置插入该节点。

6. 插入完成后，继续遍历链表，直到所有节点都被插入到有序序列中。

以下是一个基于链表的直接插入排序的示例代码：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode* prev;
    ListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

// 定义链表类
class LinkedList {
public:
    LinkedList() {
        head = new ListNode(0);
        tail = new ListNode(0);
        head->next = tail;
        tail->prev = head;
    }

    void insert(ListNode* node) {
        node->next = tail;
        node->prev = tail->prev;
        tail->prev->next = node;
        tail->prev = node;
    }

    void remove(ListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    ListNode* getHead() {
        return head->next;
    }

private:
    ListNode* head;
    ListNode* tail;
};

// 定义直接插入排序函数
void insertionSortList(LinkedList& list) {
    ListNode* cur = list.getHead()->next;
    while (cur != list.tail) {
        ListNode* next = cur->next;
        list.remove(cur);
        ListNode* p = list.getHead();
        while (p != list.tail && p->val < cur->val) {
            p = p->next;
        }
        cur->next = p;
        cur->prev = p->prev;
        p->prev->next = cur;
        p->prev = cur;
        cur = next;
    }
}

int main() {
    // 创建链表并插入节点
    LinkedList list;
    list.insert(new ListNode(3));
    list.insert(new ListNode(1));
    list.insert(new ListNode(4));
    list.insert(new ListNode(2));

    // 输出排序前的链表
    cout << "Before sorting: ";
    ListNode* p = list.getHead();
    while (p != list.tail) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 对链表进行直接插入排序
    insertionSortList(list);

    // 输出排序后的链表
    cout << "After sorting: ";
    p = list.getHead();
    while (p != list.tail) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    return 0;
}