Linked Lists in C- adding a struct in sorted position

Question

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "Book.h"


int main(int argc, char** argv) {

    Book * dummy = newBook("dummy", "dummy", 00000);

    printf("%s %s %ld", dummy->title, dummy->author, dummy->ISBN);

    dummy->next = NULL;


    Book* newishBook = newBook("Foo", "Chris", 1234);
    insertToList(newishBook, dummy);

    Book* another = newBook("Bar", "Jim", 23344);
    insertToList(another, dummy);

    Book* yet = newBook("Derp", "Bob", 999);
    insertToList(yet, dummy);

    displayList(dummy);

    searchISBN(999);

    return (EXIT_SUCCESS);
}

Book* newBook(char* newTitle, char* newAuthor, long newISBN) {
    Book* new_book = malloc(sizeof(Book));

    strcpy(new_book->title, newTitle);
    strcpy(new_book->author, newAuthor);
    new_book->ISBN = newISBN;
    return new_book;
}



void insertToList(Book* bookToInsert, Book* dummy){
    Book* currentNode = dummy;
    Book* temp = malloc(sizeof(Book));

    if (currentNode->next == NULL){
        currentNode->next = bookToInsert;
        printf("Head");
    } else {
        currentNode= currentNode->next;        
        while(currentNode->ISBN > bookToInsert->ISBN){

            if (bookToInsert ->ISBN < currentNode->ISBN){
                // if isbn of current book more than current node, move to next current node
                //otherwise add here
                printf("Added");
                temp->next = currentNode->next;
                bookToInsert->next = currentNode->next;
                currentNode->next = temp->next;
            }
        }
    }
}

void displayList(Book* dummy){
    //start at dummy node-
    Book* currentNode = dummy;
    bool run = true;

    //print until next = null
    while(run==true){
        if (currentNode->next != NULL){
            printf("%s %s %ld \n", currentNode->title, currentNode->author, currentNode->ISBN); 
            currentNode = currentNode ->next;
        } else {
            run = false;
        }
    }    
}

This program is intended to create book structs which are the nodes of a linked list. A book is defined as follows in the header file Book.h:

#ifndef BOOK_H
#define BOOK_H

#ifdef  __cplusplus
extern "C" {
#endif


typedef struct book_t {
    char title[50];
    char author[30];
    long ISBN;
    struct Book *next;
} Book;

Book* newBook(char* newTitle, char* newAuthor, long newISBN);

#ifdef  __cplusplus
}
#endif

#endif  /* BOOK_H */

I feel like my insertToList function is close to working, but I've got code-blindness from looking at it too wrong and I'm sure there's something really basic wrong with it. Currently there is no output- just an empty terminal, I believe the loop is not exiting properly. Uncommenting the printf statments "added" and "head" causes the program to loop indefinitely, outputting "added" to the terminal.

newBook() should ensure all fields are initialized. You should not need to do dummy->next = NULL; in main() — that should be done by newBook(). — Jonathan Leffler
– Jonathan Leffler, Commented Dec 8, 2015 at 1:24
Also, your code does not compile cleanly — why are you posting code that does not compile? You (claim to) have: typedef struct book_t { …; struct Book *next; } Book;. You don't show the struct Book to which the next pointer points — it is not the struct book_t. So you should be getting warnings about pointer type mismatches. — Jonathan Leffler
– Jonathan Leffler, Commented Dec 8, 2015 at 1:26
Also, your loop while(currentNode->ISBN > bookToInsert->ISBN) will never exit because the variables used in the condition never change inside the loop. Definitely, you need to think again your insertToList function. — A.S.H
– A.S.H, Commented Dec 8, 2015 at 1:30
The allocation of temp in insertToList() is puzzling; it looks likely to leak memory. You're about to insert bookToInsert, so it isn't clear why you need temp except to confuse everyone. — Jonathan Leffler
– Jonathan Leffler, Commented Dec 8, 2015 at 1:32
Book would be contained in a header file (Book.h). I had removed irrelevant functions from the code but I will edit it to contain my exact program, which compiles. — 4oursword
– 4oursword, Commented Dec 8, 2015 at 1:33

Jonathan Leffler · Accepted Answer · 2015-12-08 07:13:45Z

The structure should be:

typedef struct Book {
    char title[50];
    char author[30];
    long ISBN;
    struct Book *next;
} Book;

The code could be:

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

Book *newBook(char *newTitle, char *newAuthor, long newISBN);
void displayList(Book *dummy);
void insertToList(Book *bookToInsert, Book *dummy);
void freeList(Book *head);

int main(void)
{
    Book *dummy = newBook("dummy", "dummy", 00000);

    printf("%s %s %ld\n", dummy->title, dummy->author, dummy->ISBN);

    printf("Newish\n");
    Book *newishBook = newBook("Foo", "Chris", 1234);
    insertToList(newishBook, dummy);
    displayList(dummy);

    printf("Another\n");
    Book *another = newBook("Bar", "Jim", 23344);
    insertToList(another, dummy);
    displayList(dummy);

    printf("Yet\n");
    Book *yet = newBook("Derp", "Bob", 999);
    insertToList(yet, dummy);
    displayList(dummy);

    //searchISBN(999);
    freeList(dummy);

    return(EXIT_SUCCESS);
}

Book *newBook(char *newTitle, char *newAuthor, long newISBN)
{
    Book *new_book = malloc(sizeof(Book));

    strcpy(new_book->title, newTitle);
    strcpy(new_book->author, newAuthor);
    new_book->ISBN = newISBN;
    new_book->next = NULL;
    return new_book;
}

void insertToList(Book *bookToInsert, Book *dummy)
{
    Book *currentNode = dummy;

    while (currentNode->next != NULL && currentNode->next->ISBN < bookToInsert->ISBN)
        currentNode = currentNode->next;
    bookToInsert->next = currentNode->next;
    currentNode->next = bookToInsert;
}

void displayList(Book *dummy)
{
    Book *currentNode = dummy;

    while (currentNode != NULL)
    {
        printf("%s %s %ld\n", currentNode->title, currentNode->author, currentNode->ISBN);
        currentNode = currentNode->next;
    }
}

void freeList(Book *head)
{
    Book *bp = head;
    while (bp != 0)
    {
        Book *bn = bp->next;
        free(bp);
        bp = bn;
    }
}

This runs leak-free under valgrind thanks to the freeList() function being added and used.

Note how the list is printed after each entry is added. This helps ensure that the list is built correctly. Also note how each line of output ends with a newline. You won't necessarily see printed data until you print the newline. For debugging in particular, make sure you include newlines — but it is generally a good idea even when not debugging.

softwarenewbie7331 · Accepted Answer · 2015-12-08 05:52:36Z

1

insertToList function is not handling all the cases.

you begin by checking if the list is empty (correct) the while loop onwards has missing logic. you should:

1) check if currentNode is larger (same as your if statement)
  a) if it is smaller, insert the book,
  b) if it is larger, you need another check:
      i) if currentNode has next !== NULL, move down and repeat loop
      ii) if next == NULL, add book at the end and return;

answered Dec 8, 2015 at 5:52

softwarenewbie7331

9676 silver badges12 bronze badges

Collectives™ on Stack Overflow

Linked Lists in C- adding a struct in sorted position

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related