Part 23, two-way circular linked list model.

One 、 Traditional linked list model ？
A detailed reference ： Traditional linked list model .jpg

One way linked list ：     There is only one pointer in the node , The last node pointer field points to NULL.
One way circular list ： There is only one pointer in the node , The last node pointer field points to the head node .
Double linked list ：     There are two pointers in the node , The head node points forward NULL, The last node points back NULL.
Bidirectional circular linked list ： There are two pointers in the node , The head node points forward to the last node , The last node points back to the head node .

Two 、 One way circular list .
1、 After analysis , One way circular linked list only needs a pointer , Therefore, the node model is consistent with the one-way linked list .

struct list_node{
    int data;
    struct list_node *next;
};

2、 Suppose there is a one-way circular linked list , Each node is a storage node int Data of type , So how to write the addition, deletion, modification and query of the linked list ？

#include <stdio.h>
#include <stdlib.h>

struct list_node{
    int data;
    struct list_node *next;
};

struct list_node *init_list_head()
{
    //1. Apply for space for the head node
    struct list_node *head = malloc(sizeof(struct list_node));
    if(head == NULL)
        printf("malloc error!\n");
    
    //2. Assign a value to the header node .
    head->next = head;
    
    return head;
}

void list_add_tail(struct list_node *head,int num)
{
    //1. Apply for space for the new node
    struct list_node *new = malloc(sizeof(struct list_node));
    if(new == NULL)
        printf("malloc new error!\n");
    
    //2. Assign a value to the new node
    new->data = num;
    new->next = head;
    
    //3. Find the last node
    struct list_node *p = NULL;
    for(p=head;p->next!=head;p=p->next);
    
    //p->next == head
    //p The last node is now
    
    //4. Let the last node point to the new node
    p->next = new;

    return;
}

void show_list_node(struct list_node *head)
{
    struct list_node *p = NULL;
    for(p=head->next;p!=head;p=p->next)
    {
        printf("p->data:%d\n",p->data);
    }
    
    return;
}

struct list_node *search_list_node(struct list_node *head,int num)
{
    struct list_node *p = NULL;
    for(p=head->next;p!=head;p=p->next)
    {
        if(p->data == num)
        {
            return p;
        }
    }
    return NULL;
}

int delete_list_node(struct list_node *head,int num)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    
    for(q=head,p=head->next;p!=head;q=p,p=p->next)
    {
        if(p->data == num)
        {
            q->next = p->next;
            free(p);
            return 0;
        }
    }
    return -1;
}

void delete_list(struct list_node *head)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    
    for(p=head;p->next!=head;p=p->next);
    p->next = NULL;
    
    for(p=q=head;p!=NULL;p=q)
    {
        q = p->next;
        free(p);
    }    
}

int main(int argc,char *argv[])
{
    //1. Initializing the header node
    struct list_node *head = NULL;
    head = init_list_head();
    
    //2. Tail insertion
    list_add_tail(head,10);
    list_add_tail(head,20);
    list_add_tail(head,30);
    list_add_tail(head,40);
    list_add_tail(head,50);
    
    //3. Traverse
    show_list_node(head);
    
    //4. Search for
    struct list_node *p = search_list_node(head,30);
    if(p != NULL)
    {
        printf("p->data:%d\n",p->data);
    }
    
    //5. Delete node
    delete_list_node(head,20);
    show_list_node(head);
    
    //6. Delete the whole linked list
    delete_list(head);
    
    return 0;
}

3、 ... and 、 Double linked list .
1、 Bidirectional linked list node model ？
Because the pointer field of the bidirectional linked list node has two pointers , So the node model should be written like this ：
struct list_node{
    int data;  // Data fields
    struct list_node *prev; // Precursor pointer
    struct list_node *next; // Subsequent pointer
};

2、 Suppose there is a two-way linked list , Every node in it is storage int Data of type , Please realize the addition, deletion, modification and query of this linked list ？

#include <stdio.h>
#include <stdlib.h>

struct list_node{
    int data;
    struct list_node *prev;  // Precursor pointer
    struct list_node *next;  // Subsequent pointer
};

struct list_node *init_list_head()
{
    //1. Apply for space for the head node
    struct list_node *head = malloc(sizeof(struct list_node));
    if(head == NULL)
        printf("malloc head error!\n");
    
    //2. Assign a value to the header node
    head->prev = NULL;
    head->next = NULL;
    
    //3. Return the header node to .
    return head;
}

void list_add_tail(struct list_node *head,int num)
{
    //1. Apply for space for the new node
    struct list_node *new = malloc(sizeof(struct list_node));
    if(new == NULL)
        printf("malloc new error!\n");
    
    //2. Assign a value to the new node
    new->data = num;
    new->next = NULL;
    
    //3. Find the last node
    struct list_node *p = NULL;
    for(p=head;p->next!=NULL;p=p->next);
    
    //4. Let the subsequent pointer of the last node point to the new node
    // Let the new node precursor pointer point to the last node
    p->next = new;
    new->prev = p;
    
    return;
}

void forward_show_list_node(struct list_node *head)
{
    struct list_node *p = NULL;
    for(p=head->next;p!=NULL;p=p->next)
    {
        printf("p->data:%d\n",p->data);
    }
    return;
}

void backward_show_list_node(struct list_node *head)
{
    struct list_node *p = NULL;
    for(p=head;p->next!=NULL;p=p->next);  //p The last node is now
    
    for(;p!=head;p=p->prev)
    {
        printf("p->data:%d\n",p->data);
    }
    return;
}

void list_add_head(struct list_node *head,int num)
{
    //1. Apply for space for the new node
    struct list_node *new = malloc(sizeof(struct list_node));
    if(new == NULL)
        printf("malloc new error!\n");
    
    //2. Assign a value to the new node
    new->data = num;
    
    new->next = head->next;
    new->prev = head;
    
    if(head->next!=NULL)  // It means someone behind
    {
        head->next->prev = new; // Just let the man in the back point at me
    }
    
    head->next = new;
    
    return;
}

int delete_list_node(struct list_node *head,int num)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    
    for(q=head,p=head->next;p!=NULL;q=p,p=p->next)
    {
        if(p->data == num)
        {
            q->next = p->next;
            
            if(p->next != NULL)
            {
                p->next->prev = q;
            }
            
            free(p);
            return 0;
        }
    }
    return -1;
    
}

void delete_list(struct list_node *head)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    
    for(p=q=head;p!=NULL;p=q)
    {
        q = p->next;
        free(p);
    }    
}

int main(int argc,char *argv[])
{
    //1. Initializing the header node
    struct list_node *head = NULL;
    head = init_list_head();
    
    //2. Tail insertion
    list_add_tail(head,10);
    list_add_tail(head,20);
    list_add_tail(head,30);
    list_add_tail(head,40);
    
    //3. Head insertion
    list_add_head(head,8);
    list_add_head(head,5);
    
    //4. Traverse
    forward_show_list_node(head); // Go back and forth
    printf("-------------------\n");
    backward_show_list_node(head); // Traversing
    
    //5. Delete node
    delete_list_node(head,20);
    
    forward_show_list_node(head); // Go back and forth
    printf("-------------------\n");
    backward_show_list_node(head); // Traversing
    
    //6. Delete the whole linked list .
    delete_list(head);  // The two-way linked list deletes the whole linked list, which is consistent with the one-way linked list .

    return 0;
}

1、 Use the linked list to store the following data , And output the desired content as required . Use a two-way linked list to achieve .
      Title           Total number of pages       Cover color
-------------------------------------------
   C    language     428        red
   C++  language     352        yellow
   java language     569        blue
   C#   language     245        red
-------------------------------------------

  After the procedure is required , Displays information for printing the first book , At this time, if you enter next, Just print the information of the next book , If input prev, Just print the information of the last book , If input quit, Then the program ends .

2、 In the root directory of the development board, there is a directory called bmp_dir, It's all there 800*480 Of bmp Format picture , But how many pictures are there , What's the name , We don't know .
It is required to use a linked list to store the name of the picture , When the program is executed , Show the first picture first , Click on the left area of the screen and let go , Just show the previous one , Click on the right side of the screen to display the next , Click in the middle of the screen , It will display full black to exit the program . Use a two-way linked list to achieve .

Four 、 Bidirectional circular linked list .
1、 Bidirectional circular linked list node model ？
Consistent with the two-way linked list .
struct list_node{
    int data;
    struct list_node *prev;
    struct list_node *next;
};

2、 Suppose there is a linked list , Every node in it is storage int Data of type , We will increase, delete, and change inspections .

#include <stdio.h>
#include <stdlib.h>

struct list_node{
    int data;
    struct list_node *prev;
    struct list_node *next;
};

struct list_node *init_list_head()
{
    //1. Apply for space for the head node
    struct list_node *head = malloc(sizeof(struct list_node));
    if(head == NULL)
        printf("malloc head error!\n");
    
    //2. Assign a value to the header node
    head->prev = head;
    head->next = head;
    
    //3. Return the header node to
    return head;
}

void list_add_tail(struct list_node *head,int num)
{
    //1. Apply for space for the new node
    struct list_node *new = malloc(sizeof(struct list_node));
    if(new == NULL)
        printf("malloc new error!\n");
    
    //2. Assign a value to the new node
    new->data = num;
    new->next = head;
    
    //3. Find the last node
    struct list_node *p = head->prev;
    
    p->next = new;
    new->prev = p;
    head->prev = new;
    
    return;
}

void forward_show_list(struct list_node *head)
{
    struct list_node *p = NULL;
    for(p=head->next;p!=head;p=p->next)
    {
        printf("p->data:%d\n",p->data);
    }
    return;
}

void backward_show_list(struct list_node *head)
{
    struct list_node *p = NULL;
    for(p=head->prev;p!=head;p=p->prev)
    {
        printf("p->data:%d\n",p->data);
    }
    return;
}

void list_add_head(struct list_node *head,int num)
{
    //1. Apply for space for the new node
    struct list_node *new = malloc(sizeof(struct list_node));
    if(new == NULL)
        printf("malloc new error!\n");
    
    //2. Assign a value to the new node
    new->data = num;
    new->next = head->next;
    new->prev = head;
    head->next->prev = new;
    head->next = new;

    return;
}

int delete_list_node(struct list_node *head,int num)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    
    for(q=head,p=head->next;p!=head;q=p,p=p->next)
    {
        if(p->data == num)
        {
            q->next = p->next;
            p->next->prev = q;
            free(p);
            return 0;
        }
    }
    
    return -1;
}

void delete_list(struct list_node *head)
{
    struct list_node *p = NULL;
    struct list_node *q = NULL;
    head->prev->next = NULL;
    
    for(p=q=head;p!=NULL;p=q)
    {
        q = p->next;
        free(p);
    }
    
    return;
}

int main(int argc,char *argv[])
{
    //1. Initializing the header node
    struct list_node *head = NULL;
    head = init_list_head();
    
    //2. Tail insertion
    list_add_tail(head,10);
    list_add_tail(head,20);
    list_add_tail(head,30);
    list_add_tail(head,40);
    
    //3. Head insertion
    list_add_head(head,8);
    list_add_head(head,5);
    
    //4. Traverse
    forward_show_list(head);
    printf("--------------------\n");
    backward_show_list(head);
    
    //5. Delete node
    delete_list_node(head,30);
    
    printf("=============================================\n");
    //4. Traverse
    forward_show_list(head);
    printf("--------------------\n");
    backward_show_list(head);
    
    //6. Delete the whole linked list
    delete_list(head);
    
    return 0;
}

    practice ： Use a two-way circular linked list to do the second 2 topic .