链表3: 双链表

双链表的结构

双链表与单链表最大的不同就是不仅存储了结点的后继, 还存储了结点的前驱.

创建双链表的数据结构

typedef struct Node{
    struct Node *preNode; //前驱
    int data; //数据域
    struct Node *nextNode; //后继
} Node;

双链表初始化

//返回头结点
Node* initHeader(Node *header){
    if(header){
        cout << "链表已存在, 无需创建" << endl;
        return header;
    }
    header = (Node*)malloc(sizeof(Node));
    header->preNode = NULL;
    header->data = -1;
    header->nextNode = NULL;
    return header;
}

后插法添加元素

void addNode(Node *header, Node *roar, int &length){ //(后插法添加元素)
    if(!header){
        cout << "链表为空" << endl;
        return;
    }
    roar = header; //寻找尾结点
    while(roar->nextNode != NULL){
        roar = roar->nextNode;
    }

    int val;
    cout << "请输入值: ";
    cin >> val;

    Node *newNode = (Node*)malloc(sizeof(Node));
    //为新结点赋值 
    newNode->data = val;
    //新结点的前驱更新为roar    
    newNode->preNode = roar;
    //新结点的后继指向NULL
    newNode->nextNode = NULL; 
    //roar后继指向新结点    
    roar->nextNode = newNode; 

    //链表长度++
    length++;
}

双链表的输出

void display(Node *header){
    if(!header){
        cout << "链表为空" << endl;
        return;
    }
    Node *curNode = header->nextNode;
    while(curNode!=NULL){
        cout << curNode->data << " ";
        curNode = curNode->nextNode;
    }   
    cout << endl;
}

测试

int main(){
    Node *header = NULL;
    Node *roar = (Node*)malloc(sizeof(Node));
    int length = 0; //链表长度
    int choice; //选项
    do{
        cout << "------------------------------" << endl;
        cout << "1.创建" << endl;
        cout << "2.在尾部插入新节点" << endl;
        cout << "3.输出链表" << endl;
        cout << "0.退出" << endl;
        cout << "输入选项:";
        cin >> choice;
        switch(choice){
            case 1:
                header = initHeader(header);
                break;
            case 2:
                addNode(header, roar, length);
                break;
            case 3:
                display(header);
                break;
            default:
                break;
        }
    }while(choice!=0);
    
    system("pause");
    return 0;
}