如何修复双向链表的display函数？头插后显示顺序与预期不符

这事儿其实很好理解——你写的inserthead()就是专门往链表头部插元素的，而你的display()是从头部开始顺着next指针往后遍历，结果自然和你期望的插入顺序反过来啦！

咱们拆解下插入过程就懂了：

• 插10：链表是 10（head和tail都是10）
• 插20：20变成新head，next指向10，链表变成 20 -> 10
• 插30：30变成新head，next指向20，链表变成 30 -> 20 -> 10
• 插40：40变成新head，next指向30，链表变成 40 -> 30 -> 20 -> 10

这时候从head开始遍历，输出肯定是40 30 20 10，完全符合inserthead的设计逻辑，但和你想要的插入正序不符。下面给两种靠谱的解决方案：

方案1：改用尾部插入（推荐，贴合你的输出预期） #

把inserthead改成inserttail，每次往链表末尾加元素，这样display从head遍历就能得到插入顺序的正序：

#include <iostream>
using namespace std;

struct doublelinklist {
    int data;
    doublelinklist* pre;
    doublelinklist* next;
};

struct doublelinklist* head = NULL;
struct doublelinklist* tail = NULL;

// 改为尾部插入函数
void inserttail(int x) {
    doublelinklist* newnode = new doublelinklist;
    newnode->data = x;
    newnode->next = NULL;
    newnode->pre = NULL;
    
    if (tail != NULL) {
        tail->next = newnode;
        newnode->pre = tail;
        tail = newnode;
    } else {
        head = newnode;
        tail = newnode;
    }
}

void display() {
    doublelinklist* position = head;
    cout << "\nDOUBLE LINK LIST: ";
    while (position != NULL) {
        cout << position->data << " ";
        position = position->next;
    }
    cout << endl;
}

int main() {
    inserttail(10);
    inserttail(20);
    inserttail(30);
    inserttail(40);
    display();
    return 0;
}

修改说明：

• 新增inserttail函数，把新节点挂在当前tail的next上，再更新tail为新节点
• 主函数调用inserttail替代原inserthead
• 给所有函数补全了返回类型（原代码没写返回类型是C++不规范写法，建议养成好习惯）

方案2：保留头部插入，修改display为从尾部往前遍历 #

如果一定要保留inserthead的逻辑，那可以改display函数，从tail开始顺着pre指针往前遍历，同样能得到插入顺序的正序：

#include <iostream>
using namespace std;

struct doublelinklist {
    int data;
    doublelinklist* pre;
    doublelinklist* next;
};

struct doublelinklist* head = NULL;
struct doublelinklist* tail = NULL;

void inserthead(int x) {
    doublelinklist* newnode = new doublelinklist;
    newnode->data = x;
    newnode->next = NULL;
    newnode->pre = NULL;
    
    if (head != NULL) {
        newnode->next = head;
        head->pre = newnode;
        head = newnode;
    } else {
        head = newnode;
        tail = newnode;
    }
}

// 修改display函数，从tail往前遍历
void display() {
    doublelinklist* position = tail;
    cout << "\nDOUBLE LINK LIST: ";
    while (position != NULL) {
        cout << position->data << " ";
        position = position->pre;
    }
    cout << endl;
}

int main() {
    inserthead(10);
    inserthead(20);
    inserthead(30);
    inserthead(40);
    display();
    return 0;
}

修改说明：

• 把display的遍历起点改成tail，循环里用position = position->pre替代原next
• 同样补全了所有函数的返回类型，让代码更规范

两种方案运行后，都能得到你期望的输出：DOUBLE LINK LIST: 10 20 30 40

内容的提问来源于stack exchange，提问作者POKA