1 list

单链表-带头结点.png 单链表-带头结点.png 不带 头结点.png 不带 头结点.png 不带头结点 + 删除 重构 为 去 if-else.png 不带头结点 + 删除 重构 为 去 if-else.png

1   单链表

1.1 带头结点

// 单链表-带头结点
#include <stdio.h>
#include <stdlib.h> // malloc / free

typedef struct node
{
    int data;
    struct node* next;
}node;

void init_empty_list(node** p)
{   
    *p = (node*)malloc( sizeof(node) );
    // blank_node
    (*p)->next = NULL;
}

node* createNode(int _data)
{
    node* pnode = (node*)malloc( sizeof(node) );
    pnode->data = _data;
    pnode->next = NULL;

    return pnode;
}

void insert_head(node* head, node* p)
{
    p->next = head->next;
    head->next = p;
}

void delete_node(node* head, int _elem)
{
    // (1) find the specified elem
    // NULL <=> tail_off_one_node
    node* current = head->next;
    node* prev = head;
    while(current != NULL && current->data != _elem) 
    {
        prev = current;
        current = current->next;
    }
    // (2) delete_node if found
    if(current != NULL) // found
    {
        prev->next = current->next;
        free(current);
    }
}

void print_list(node* head)
{
    for(node* p = head->next; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

clear_list(node* head)
{
    node* prev = head;
    while(head != NULL)
    {   
        head = head->next;
        free(prev);
        prev = head;
    }
}

int main()
{
    node* head = NULL;
    
    //(1) modify head => &head is passed
    // => para: node**
    init_empty_list(&head);

    //(2) create a list with 3 nodes: 2<-1<-0
    node* pnode = NULL;
    for(int i = 0; i < 3; ++i)
    {
        pnode = createNode(i);  
        //(3) head insert
        insert_head(head, pnode);
    }
    print_list(head); // 2 1 0

    //(4)
    delete_node(head, 1);

    print_list(head); // 2 0
    //(5) 
    clear_list(head);       
}

1.2 不带 头结点

//  单链表-不带 头结点
#include <stdio.h>
#include <stdlib.h> // malloc / free

typedef struct node
{
    int data;
    struct node* next;
}node;

void init_empty_list(node** p)
{   
    *p = NULL;
}

node* createNode(int _data)
{
    node* pnode = (node*)malloc( sizeof(node) );
    pnode->data = _data;
    pnode->next = NULL;

    return pnode;
}

void insert_head(node** phead, node* p)
{
    if (*phead == NULL)
        *phead = p;
    else
    {
        p->next = *phead;
        *phead = p;
    }
}

void delete_node(node** phead, int _elem)
{
    node* current = *phead;
    node* prev = current;
    while(current != NULL && current->data != _elem) 
    {
        prev = current;
        current = current->next;
    }
    if(current != NULL) // found
    {
        if (current == *phead)
            *phead = current->next;
        else
            prev->next = current->next;
        free(current);
    }
}

void print_list(node* head)
{
    for(node* p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

clear_list(node* head)
{
    node* prev = head;
    while(head != NULL)
    {   
        head = head->next;
        free(prev);
        prev = head;
    }
}

int main()
{
    node* head = NULL;
    
    //(1) modify head => &head is passed
    // => para: node**
    init_empty_list(&head);

    //(2) create a list with 3 nodes: 2<-1<-0
    node* pnode = NULL;
    for(int i = 0; i < 3; ++i)
    {
        pnode = createNode(i);  
        //(3) head insert
        insert_head(&head, pnode);
    }
    print_list(head); // 2 1 0

    //(4)
    delete_node(&head, 1);

    print_list(head); // 2 0
    //(5) 
    clear_list(head);       
}

1.3 不带头结点 + 删除 重构 为 去 if-else

// 1.3 delete_node 去 if-else
#include <stdio.h>
#include <stdlib.h> // malloc / free

typedef struct node
{
    int data;
    struct node* next;
}node;

void init_empty_list(node** p)
{   
    *p = NULL;
}

node* createNode(int _data)
{
    node* pnode = (node*)malloc( sizeof(node) );
    pnode->data = _data;
    pnode->next = NULL;

    return pnode;
}

void insert_head(node** phead, node* p)
{
    if (*phead == NULL)
        *phead = p;
    else
    {
        p->next = *phead;
        *phead = p;
    }
}

void delete_node(node** phead, int _elem)
{
    node** indirect;
    indirect = phead;
    
    while (*indirect != NULL && (*indirect)->data != _elem )
    {
        indirect = &(*indirect)->next;
    }

    if(*indirect != NULL) // found
    {
        node* tmp = *indirect;
        *indirect = (*indirect)->next;
        free(tmp);
    }
}

void print_list(node* head)
{
    for(node* p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

clear_list(node* head)
{
    node* prev = head;
    while(head != NULL)
    {   
        head = head->next;
        free(prev);
        prev = head;
    }
}

int main()
{
    node* head = NULL;
    
    //(1) modify head => &head is passed => para: node**
    init_empty_list(&head);

    //(2) create a list with 3 nodes: 2<-1<-0
    node* pnode = NULL;
    for(int i = 0; i < 3; ++i)
    {
        pnode = createNode(i);  
        
        //(3) head insert
        insert_head(&head, pnode);
    }
    print_list(head); // 2 1 0

    //(4)
    delete_node(&head, 1);

    print_list(head); // 2 0
    //(5) 
    clear_list(head);       
}