How to delete an element from a linked list of linked lists

Question

I have a linked list of linked lists in C which is a library of categories and each category has a list of books and I need to delete a category with all the books in it the problem is after I delete all the books I'm left with the category node and to delete it I need a pointer to the previous category which I do not have how can I get around this problem?

Answer 1

the problem is after I delete all the books I'm left with the category node and to delete it I need a pointer to the previous category which I do not have how can I get around this problem?

The function that deletes a given category has to be passed two arguments:

1. A pointer to the list/head
2. A pointer to the category node to delete

The list/head pointer is necessary so that we can loop through the list to find the pointer to the previous category

---

There are a number of ways to structure this.

But, basically, we need a struct for a category. And, a struct for a book.

When adding/deleting to/from a list, we can have the list be a "double star" pointer to the head node:

void catadd(struct cat **head,struct cat *cat);

Or, we can do:

struct cat *catadd(struct cat *head,struct cat *cat);

But, for lists, I prefer a separate list struct:

void catadd(struct list *list,struct cat *cat);

By doing this, we can have a uniform first argument to a function that takes a pointer to a [category] list. That is, we don't have to worry whether the argument is struct cat **head for something that modifies the list (e.g.) catnew or just struct cat *head for something that just traverses the list (e.g.) catprint

---

Here is some code. It is [well] annotated.

Note that [where possible] it's good to be self protective.

For example, the catnew function that creates a new category struct must scan the entire list to find the previous/tail node of the list.

So, with a little extra effort (the strcmp) it can find a potential duplicate and just reuse the already created category node.

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

// book control
typedef struct book book_t;
struct book {
    book_t *book_next;                  // next book in the list
    char *book_title;                   // book title
    // other data (e.g. author, date, etc) ...
};

// category control
typedef struct cat cat_t;
struct cat {
    cat_t *cat_next;                    // next category in category list
    char *cat_name;                     // category name
    book_t *cat_book;                   // pointer to linked list of books
};

// list of categories
typedef struct catlist catlist_t;
struct catlist {
    cat_t *list_head;                   // head of list
};

catlist_t catlist;                      // list of categories

// booknew -- allocate a new book
book_t *
booknew(const char *title)
{
    book_t *book = calloc(1,sizeof(*book));

    book->book_title = strdup(title);

    return book;
}

// bookprint -- print a single book
void
bookprint(book_t *book)
{

    printf("  TITLE: %s\n",book->book_title);
}

// bookdel -- destroy a single book
void
bookdel(book_t *del)
{

    free(del->book_title);
    free(del);
}

// bookdelall -- destroy all books in a list
void
bookdelall(cat_t *cat)
{
    book_t *cur;
    book_t *next;

    for (cur = cat->cat_book;  cur != NULL;  cur = next) {
        next = cur->book_next;
        bookdel(cur);
    }
}

// catnew -- create a category and add to list of categories
// RETURNS: pointer to category found/created
cat_t *
catnew(catlist_t *list,const char *name)
{
    cat_t *cur;
    cat_t *prev;

    // find end of list categories
    prev = NULL;
    for (cur = list->list_head;  cur != NULL;  cur = cur->cat_next) {
        if (strcmp(cur->cat_name,name) == 0)
            break;
        prev = cur;
    }

    do {
        // category already exists
        if (cur != NULL)
            break;

        // create the new category node
        cur = calloc(1,sizeof(*cur));
        cur->cat_name = strdup(name);

        // add to end of list of categories
        if (prev != NULL)
            prev->cat_next = cur;

        // set as head of empty list
        else
            list->list_head = cur;
    } while (0);

    return cur;
}

// catfind -- find an existing category
// RETURNS: pointer to category found
cat_t *
catfind(catlist_t *list,const char *name)
{
    cat_t *cur;

    // find end of list categories
    for (cur = list->list_head;  cur != NULL;  cur = cur->cat_next) {
        if (strcmp(cur->cat_name,name) == 0)
            break;
    }

    return cur;
}

// catappend -- append book to a category
// RETURNS: 1=book already in category
int
catappend(cat_t *cat,book_t *book)
{
    book_t *cur;
    book_t *prev;
    int err;

    // find end of list of books for this category
    prev = NULL;
    for (cur = cat->cat_book;  cur != NULL;  cur = cur->book_next) {
        if (cur == book)
            break;
        prev = cur;
    }

    do {
        // book already exists in category -- caller should [maybe] do bookdel
        // on the book pointer
        err = (cur != NULL);
        if (err)
            break;

        // append to end of list
        if (prev != NULL)
            prev->book_next = book;

        // add to empty list
        else
            cat->cat_book = book;
    } while (0);

    return err;
}

// catprint -- print a single category
void
catprint(cat_t *cat)
{
    book_t *book;

    printf("CATEGORY: %s\n",cat->cat_name);
    for (book = cat->cat_book;  book != NULL;  book = book->book_next)
        bookprint(book);
}

// catprintall -- print all categories
void
catprintall(catlist_t *list)
{
    cat_t *cur;

    printf("\n");
    for (cur = list->list_head;  cur != NULL;  cur = cur->cat_next)
        catprint(cur);
}

// catdelete -- delete a category
void
catdelete(catlist_t *list,cat_t *del)
{
    cat_t *cur;
    cat_t *prev;

    // find a matching entry
    // we _must_ do this to find the pointer to the _previous_ category
    prev = NULL;
    for (cur = list->list_head;  cur != NULL;  cur = cur->cat_next) {
        if (cur == del)
            break;
        prev = cur;
    }

    do {
        // node not found -- category is _not_ in the list
        if (cur == NULL)
            break;

        // delete all books in this category
        bookdelall(cur);

        // free the category name
        free(cur->cat_name);

        // remove this category from middle/end of list
        if (prev != NULL)
            prev->cat_next = cur->cat_next;

        // this category is the head of the list -- advance the head pointer
        else
            list->list_head = cur->cat_next;

        free(cur);
    } while (0);
}

// tstdel -- test adding book to category
void
tstadd(const char *catname,const char *title)
{
    cat_t *cat;
    book_t *book;

    cat = catnew(&catlist,catname);
    book = booknew(title);

    // append book to category -- delete book if it's a dup
    if (catappend(cat,book))
        bookdel(book);
}

// tstdel -- test category deletion
void
tstdel(const char *name)
{
    cat_t *cat;

    printf("\n");
    printf("Deleting category: %s\n",name);

    // find the category
    cat = catfind(&catlist,name);

    // delete the category if we found a valid one
    if (cat != NULL)
        catdelete(&catlist,cat);

    // show what is left
    catprintall(&catlist);
}

int
main(void)
{
    cat_t *cat;

    tstadd("Fiction","True Grit");
    tstadd("SciFi","Andromeda Strain");
    tstadd("Propaganda","Putin");
    catprintall(&catlist);

    tstadd("Propaganda","Trump");
    tstadd("Fiction","To Kill A Mockingbird");
    tstadd("SciFi","Independence Day");
    catprintall(&catlist);

    tstadd("SciFi","The Day The Earth Stool Still");
    tstadd("Propaganda","Fox News");
    catprintall(&catlist);

    tstdel("Propaganda");
    tstdel("Fiction");
    tstdel("SciFi");

    return 0;
}

---

Here is the program output:

CATEGORY: Fiction
  TITLE: True Grit
CATEGORY: SciFi
  TITLE: Andromeda Strain
CATEGORY: Propaganda
  TITLE: Putin

CATEGORY: Fiction
  TITLE: True Grit
  TITLE: To Kill A Mockingbird
CATEGORY: SciFi
  TITLE: Andromeda Strain
  TITLE: Independence Day
CATEGORY: Propaganda
  TITLE: Putin
  TITLE: Trump

CATEGORY: Fiction
  TITLE: True Grit
  TITLE: To Kill A Mockingbird
CATEGORY: SciFi
  TITLE: Andromeda Strain
  TITLE: Independence Day
  TITLE: The Day The Earth Stool Still
CATEGORY: Propaganda
  TITLE: Putin
  TITLE: Trump
  TITLE: Fox News

Deleting category: Propaganda

CATEGORY: Fiction
  TITLE: True Grit
  TITLE: To Kill A Mockingbird
CATEGORY: SciFi
  TITLE: Andromeda Strain
  TITLE: Independence Day
  TITLE: The Day The Earth Stool Still

Deleting category: Fiction

CATEGORY: SciFi
  TITLE: Andromeda Strain
  TITLE: Independence Day
  TITLE: The Day The Earth Stool Still

Deleting category: SciFi