Add to linked list via tail pointer without 3 leve

问题:

I am working on a project that requires an implementation of a linked list. Before I started the project, I was reviewing the classic method of creating a linked list.

I realized that in the past, I had been adding elements to a linked list via the head pointer that traverses the list until it reaches the null pointer.

I figured out that there is no need to do it this way, and to implement it in a way that involves a tail pointer, but the only way I could think of is a one that involves a triple pointer or a global pointer. I was wondering, is there an easier approach that uses less levels of indirection?

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


typedef struct list {
    int val;
    struct list *next;
} list;


void printlist(list *head);
void freelist(list *head);

void AddList(list ***tail, int val);


int main(void)
{
    /* create first node */
    list *head = (list *)malloc(sizeof(*head));

    /* assign members of first node */
    head->val = 1;
    head->next = NULL;

    /* create tail */
    list **tail = &head->next;

    /* add values to list */
    AddList(&tail, 2);
    AddList(&tail, 3);
    AddList(&tail, 4);
    AddList(&tail, 5);
    AddList(&tail, 6);
    AddList(&tail, 7);
    AddList(&tail, 8);
    AddList(&tail, 9);

    /* print list */
    printlist(head);

    /* free list */
    freelist(head);

    /* exit program */
    system("pause");
    return 0;
}


void AddList(list ***tail, int val)
{
    list *node = (list *)malloc(sizeof(*node));

    node->val = val;
    node->next = NULL;

    **tail = node;

    *tail = &node->next;
}

void printlist(list *head)
{
    while (head) {
        printf("%d\n", head->val);
        head = head->next;
    }
}

void freelist(list *head)
{
    list *tmp = head;
    while (head) {
        head = head->next;
        free(tmp);
        tmp = head;
    }
}

回答1:

The tail pointer should point to the last node, not the next pointer of the last node:

In main:

/* create tail */
list *tail = head;

In AddList:

void AddList(list **tail, int val)
{
    list *node = malloc(sizeof(*node));

    node->val = val;
    node->next = NULL;

    (*tail)->next = node;
    *tail = node;
}

回答2:

You can do:

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

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

typedef struct node NODE;

struct llist {
    unsigned int count;
    NODE *head;
    NODE *tail;
};

typedef struct llist LLIST;

LLIST *create_list() {
    LLIST *llist = malloc(sizeof(LLIST));
    if (llist == NULL)
        exit(EXIT_FAILURE);

    llist->head = NULL;
    llist->tail = NULL;
    llist->count = 0;
    return llist;
}

NODE *create_ll_node(int data) {
    NODE *node = malloc(sizeof(NODE));
    if (node == NULL)
        exit(EXIT_FAILURE);

    node->data = data;
    node->next = NULL;
    return node;
}

void add_list_head(LLIST *llist, int data) {
    NODE *node = create_ll_node(data);
    if (llist->head == NULL) {
        llist->head = node;
        llist->tail = node;
    } else {
        node->next = llist->head;
        llist->head = node;
    }
    llist->count++;
}

void add_list_tail(LLIST *llist, int data) {
    NODE *node = create_ll_node(data);
    if (llist->tail == NULL) {
        llist->head = node;
        llist->tail = node;
    } else {
        llist->tail->next = node;
        llist->tail = node;
    }
    llist->count++;
}

void delete_list_elements(NODE *llist_head) {
    NODE *node, *tmp;
    if (llist_head == NULL) {
        printf ("List is empty.\n");
        return;
    }

    node = llist_head;
    while(node) {
        tmp = node->next;
        free(node);
        node = tmp;
    }
}

void delete_list(LLIST *llist) {
    if (llist == NULL) {
        printf ("Invalid list.\n");
        return;
    }

    delete_list_elements(llist->head);
    free(llist);
}

void display_list(const LLIST *llist) {
    if (llist == NULL) {
        printf ("Invalid list.\n");
        return;
    }
    if (llist->head == NULL) {
        printf ("List is empty.\n");
        return;
    }

    NODE *node = llist->head;
    while(node) {
        printf ("data: %d\n", node->data);
        node = node->next;
    }
}

unsigned int get_list_element_count(const LLIST *llist) {
    if (llist == NULL) 
        return 0;

    return llist->count;
}

int main() {
    LLIST *llist = create_list();

    add_list_head(llist, 5);
    add_list_head(llist, 4);
    add_list_head(llist, 3);
    add_list_head(llist, 2);
    add_list_head(llist, 1);
    add_list_tail(llist, 6);
    add_list_tail(llist, 7);
    add_list_tail(llist, 8);
    add_list_tail(llist, 9);
    add_list_tail(llist, 10);

    display_list(llist);

    printf ("Total elements in list : %u\n", get_list_element_count(llist));

    delete_list(llist);

    return 0;
}