认识链表

1.创建链表

Node* createList()
{
    Node* head = (Node*)malloc(sizeof(Data));
    if (!head)
    {
        cout << "head malloc failed" << endl;
        return nullptr;
    }
    //初始化为NULL
    memset(head, 0, sizeof(Node));

    return head;
}

其实这块就是创建了链表的head节点

链表的内存空间是不连续的，这块和顺序表有区别

2.创建节点

Node* createNode(Data val)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode)
    {
        cout << "newNode malloc failed" << endl;
        return nullptr;
    }

    newNode->data = val;
    newNode->next = NULL;
    return newNode;
}

3.插入数据

3.1头插

void push_front(Node* list, Data val)
{
    Node* newNode = createNode(val);
    newNode->next = list->next;//先让新节点接上首元节点
    list->next = newNode;//头节点连上新节点
}

3.2尾插

void push_back(Node* list, Data val)
{
    Node* curNode = list;
    while (curNode->next)
    {
        curNode = curNode->next;
    }//找到最后一个节点
    Node* newNode = createNode(val);//尾节点指向新节点
    curNode->next = newNode;//连接

}

3.3指定位置插入

void insert_pos(Node* list, int pos, Data val)
{
    Node* curNode = list;
    //先找到pos的前一个元素
    for (int i = 0; i < pos && curNode->next; i++)
    {
        curNode = curNode->next;
    }

    Node* newNode = createNode(val);
    newNode->next = curNode->next;
    curNode->next = newNode;
}

3.4指定元素插入

void insert_item(Node* list, Node* item, Data val)
{
    Node* newNode = createNode(val);
    newNode->next = item->next;
    item->next = newNode;
}

4.删除数据

4.1头删

void pop_front(Node* list)
{
 
    Node* delNode = list->next;
    list->next = delNode->next;
    free(delNode);
} 

4.2尾删

void pop_back(Node* list)
{
   //如果链表为空直接退出
    if (empty(list)) return;

    Node* curNode = list;
    while (curNode->next && curNode->next->next)
    {
        curNode = curNode->next;//是倒数第二个节点
    }
    free(curNode->next);
    curNode->next = NULL;

}

4.3删除指定元素

void removeOne(Node* list, Data val)
{
    //如果链表为空直接退出
    if (empty(list)) return;

    Node* preNode = list;
    Node* curNode = list->next;
    while (curNode)
    {
        if (curNode->data == val)
        {
            break;
        }
        preNode = curNode;
        curNode = curNode->next;
    }
    if (curNode)
    {
         preNode->next = curNode->next;
         free(curNode);

    }
 
}

void removeAll(Node* list, Data val)
{
    if (empty(list)) return;

    Node* preNode = list;
    Node* curNode = list->next;
    Node* delNode = NULL;
    while (curNode)
    {
        if (curNode->data == val)
        {
            preNode->next = curNode->next;
            delNode = curNode;
        }
        else {
            preNode = curNode;//不是要删除的元素就移动preNOde
        }
 
        curNode = curNode->next;
        //根据情况来释放
        if (delNode)
        {
            free(delNode);
            delNode = NULL;
        }
    }
}

5.其他

5.1排序

void sort(Node* list)
{
    if (empty(list)) return;

    for (Node* i = list->next; i->next; i=i->next)
    {
        for (Node* curNode = list->next; curNode->next; curNode = curNode->next)
        {
            if (curNode->data > curNode->next->data)
            {
                Data t = curNode->data;
                curNode->data = curNode->next->data;
                curNode->next->data = t;
            }
        }
    }

5.2 反转

void reverse(Node* list)
{
    if (empty(list)) return;

    Node* preNode = NULL;
    Node* curNode = list->next;
    Node* nextNode = NULL;

    while (curNode)
    {
        nextNode = curNode->next;
        curNode->next = preNode;
        preNode = curNode;
        curNode = nextNode;
    }
    list->next = preNode;
}

5.3清空

void clear(Node* list)
{
    Node* curNode = list->next;
    Node* delNode = NULL;
    while (curNode)
    {
        delNode = curNode;
        curNode = curNode->next;
        free(delNode);
    }
    list->next = NULL;
}

5.4销毁

void destroy(Node** list)
{
    clear(*list);
    free(*list);
    (*list) = NULL;
}

5.5判断是否为空

bool empty(Node* list)
{

    return list->next==NULL;
}

6.输出

void showlist(Node* list)
{
    if (list == NULL) return;
    Node* curNode = list->next;
    while (curNode)
    {
        cout << curNode->data << " ";
        curNode = curNode->next;
    }
    cout << endl;
}