链表2: 动态单链表

定义数据结构

// 定义链表数据结构
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;

初始化链表

// 初始化链表
LNode *Init_LinkList(){ //返回头指针
    // 创建头结点
    LNode *header = (LNode*)malloc(sizeof(LNode));
    header->data = -1;
    header->next = NULL;
    // 创建尾部指针
    LNode *pEnd = header;
    // 插入数据
    int val = -1;
    while(true){
        cout << "input value: ";
        cin >> val;
        // 判断输入结束
        if(val==-1){
            cout << "input end" << endl;
            break;
        }
        // 创建新节点
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = val;
        newNode->next = NULL;
        // 将新节点放入链表中
        pEnd->next = newNode;
        // 更新尾部指针指向
        pEnd = newNode;
    }
    // 返回头指针
    return header;
}

通过值删除结点

// 删除值为val的节点
void deleteValue(LNode *header){
    if(!header->next) return;
    LNode *preNode = header;
    LNode *pCurrent = preNode->next;

    int val;
    cout << "input val: ";
    cin >> val;

    while(pCurrent){
        if(pCurrent->data==val) break;
        preNode = pCurrent;
        pCurrent = preNode->next;
    }

    if(!pCurrent){
        cout << "Node doesn't exist" << endl;
        return;
    } 

    // 如果值相等,将当前前趋的next指向当前后继的地址
    preNode->next = pCurrent->next;
    // // 将当前next指向null
    // pCurrent->next = NULL;
    // 释放当前结点
    free(pCurrent);
}

在链表的末尾插入新数据

输出链表

// 遍历
void ForeachValue(LNode *header){
    // 空表
    if(!header->next) {
        cout << "null" << endl;
        return;
    }            
    // 第一个元素无需遍历
    LNode *pCurrent = header->next;
    while(pCurrent){
        cout << pCurrent->data << endl;
        pCurrent = pCurrent -> next;
    }
}

清空链表

//(保留了头指针)
void Clear_LinkList(LNode *header){
    if(!header) return; // 空链表
    LNode *pCurrent = header->next;
    while(pCurrent){
        LNode *pBackup = pCurrent->next;
        free(pCurrent);
        pCurrent = pBackup;
    }
    header->next = NULL;
}

销毁链表

// 销毁
void Destory_LinkList(LNode *header){
    if(!header) return; // 如果链表为空
    LNode *pCurrent = header;
    while(pCurrent){
        LNode *pBackup = pCurrent->next;
        cout << pCurrent->data << " Node was destoried" << endl;
        free(pCurrent);
        pCurrent = pBackup;
    }
    free(header);
}

测试

int main(){
    LNode *header = Init_LinkList();
    ForeachValue(header); //遍历
    insertValue(header); //插入数据
    ForeachValue(header);
    // // 清空
    // Clear_LinkList(header);
    deleteValue(header);
    ForeachValue(header);

    Destory_LinkList(header);

    system("pause");
    return 0;
}