0

I'm currently implementing a LinkedList in C out of didactic reasons. I am almost finished, but am now struggling because it does not quite do what its intended to do.

Long story short, the output is not what I expect from my code - and now I'm a little exhausted from circling around this in my brain.

Here is the whole implementation:

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

/********** GLOBALS *******************************/
#define DEBUG 0

/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
    int key;
    char string[1024];
    struct Node *next;  // pointer to next node
} Node;

/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
    struct Node *first;
    struct Node *last;
    int size;
} LinkedList;

/********** FUNCTION HEADERS **********************/
LinkedList init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);

/*********** FUNCTION DEFINITIONS ***************/
/* init_list Returns an appropriately (for an empty list) initialized struct List*/
LinkedList init_list() {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    LinkedList list;

    list.first = NULL;
    list.last = NULL;
    list.size = 0;

    return list;
}

/* Given a List, a key and a string adds a Node containing this
information at the end of the list*/
void insert_end(LinkedList *list, int key, char string[]) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    list->size++;                    // increment size of list

    // intialize the new Node
    Node* newN = malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string, string);
    newN->next = NULL;

    Node* oldLast = list->last;      // get the old last
    oldLast->next = newN;          // make new Node the next Node for oldlast
    list->last = newN;              // set the new last  in the list

    printf("new Node at end: %d %s %p \n", newN->key, newN->string, newN->next);

}

/* Given a List, a key and a string adds a Node, containing
this information at the beginning of the list */
void insert_beginning(LinkedList *list, int key, char string[]) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    list->size++;                    // increment size of list
    Node* oldFirst = list->first;    //get the old first node

    // intialize the new Node
    Node* newN = malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string,string);
    newN->next = oldFirst;

    list->first = newN;              // set the new first

    //special case: if list size == 1, then this new one is also the last one
    if(list->size == 1)
        list->last = newN;

    printf("new Node at beginning: '%d' '%s' '%p' \n", newN->key, newN->string, newN->next);

}

/* Removes the first Node from the list*/
int remove_beginning(LinkedList *list) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    if(list->size <= 0)
       return -1;

    list->size--;

    Node * oldFirst = list->first;
    list->first = oldFirst->next;
    oldFirst = NULL;

    return 0;

}

/* Removes the last Node from the list.*/
int remove_end(LinkedList *list) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    if(list->size <= 0)
        return -1;

    list->size--;                    // decrement list size
    //Node * oldLast = list->last;     // get ref to old last
    //oldLast = NULL;                  // set it null
    //free(oldLast);
    Node * startNode = list->first;
    list->last = NULL;               // set listref last to null

    //find the now new last node..
   Node * newLast = NULL;
   while(startNode->next != NULL) {
        newLast=startNode;
   }

    // if list is not empty now..
    if(list->size > 0)
        list->last = newLast;

    return 0;

}

/* Given a List prints all key/string pairs contained in the list to
the screen*/
int print_list(LinkedList *list) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);


    if(list->size <=0)
        return -1;

    printf("List.size = %d \n", list->size);

    Node *startN = list->first;  //get first

    printf("Node#%d.string = '%s', .next = '%d' \n",list->first->key, list->first->string, list->first->next->key);

    //iterate through list
    while(startN->next != NULL) {
        printf("Node#%d.string = '%s', .next = '%d' \n",startN->key, startN->string, startN->next->key);
        startN = startN->next;
    }

    return 0;
}

/* Given a List, frees all memory associated with this list. */
void free_list(LinkedList *list) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

    if(list != NULL)
        free(list);
}

/* Given a List and a key, iterates through the whole List and returns
the string of the first node which contains the key */
char * get_string(LinkedList *list, int key) {

    if(DEBUG)
        printf("%s:%d called \n", __FUNCTION__, __LINE__);

     Node *startN = list->first;  //get first

    //iterate through list
    while(startN->next != NULL) {
        if(startN->key == key)
            return startN->string;
        else
            startN = startN->next;
    }

    return NULL;

}

/*************** MAIN **************/
int main(void)
{

    LinkedList list = init_list();

    insert_beginning(&list, 1,"im the first" );
    insert_beginning(&list, 2,"im the second" );
    insert_beginning(&list, 3,"im the third" );
    //insert_end(&list, 2, "im the second");
    //insert_end(&list, 3,"im the third");
    //insert_end(&list, 4, "forth here");
    //insert_end(&list, 5, "...and i am last");
    //insert_end(&list, 6, "END");

    print_list(&list);

   // remove_end(&list);
   // remove_beginning(&list);

   // print_list(&list);

   // free_list(&list);

}

and here is the output, which is not as expected (but the code compiles just fine): 

new Node at beginning: '1' 'im the first' '00000000' 
new Node at beginning: '2' 'im the second' '00762EF8' 
new Node at beginning: '3' 'im the third' '00764330' 
List.size = 3 
Node#3.string = 'im the third', .next = '2' 
Node#3.string = 'im the third', .next = '2' 
Node#2.string = 'im the second', .next = '1'

As you can see print_list either doesn't print the list correctly, or the list itself isn't correct.

  • Where have I failed?

As always, Best-Practice hints are very welcome and the source is Public Domain.

Improve this question
2
  • 1
    Btw, you may consider to use circular double-linked list, which makes things simplier. Here is an example: pastebin.com/mScMkkdy Commented May 22, 2017 at 21:03
  • thanks @0andriy, but it was intentional to implement a singly-linkedList instead of a bidirectional one. Commented May 24, 2017 at 9:48

4 Answers 4

Reset to default
1

Your queue is really a stack as you're pushing things onto the head First in last out order.

I just changed your print_list function as follows;

//iterate through list
do {
    printf("Node#%d.string = '%s', .next = '%p' \n",startN->key, startN->string, startN->next);
    startN = startN->next;
}while(startN != NULL);

The output I'm getting with this change is;

new Node at beginning: '1' 'im the first' '0x0'
new Node at beginning: '2' 'im the second' '0x2003ac40'
new Node at beginning: '3' 'im the third' '0x2004b088'
List.size = 3
Node#3.string = 'im the third', .next = '0x2004b088'
Node#2.string = 'im the second', .next = '0x2003ac40'
Node#1.string = 'im the first', .next = '0x0'
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Your problem is that you print the first element twice.

Here:

Node *startN = list->first;

printf("Node#%d.string = '%s', .next = '%d' \n",list->first->key, list->first->string, list->first->next->key);
                                                ^^^^^^^^^^^
                                           //   Same as startN->key !    
//iterate through list
while(startN->next != NULL) {
    printf("Node#%d.string = '%s', .next = '%d' \n",startN->key, startN->string, startN->next->key);
                                                    ^^^^^^^^^^^
                                              //    So in first loop you print the same again.

    startN = startN->next;
}

I guess your second printf should be:

    printf("Node#%d.string = '%s', .next = '%d' \n",startN->next->key, startN->next->string, startN->next->key);
                                                           ^^^^^^              ^^^
Improve this answer

Comments

1

Simply change the print_list function as follows to get an expected result

int print_list(LinkedList *list) {

if(DEBUG)
    printf("%s:%d called \n", __FUNCTION__, __LINE__);


if(list->size <=0)
    return -1;

printf("List.size = %d \n", list->size);

Node *startN = list->first;  //get first

// This line is not needed because linked list getting traversed in while loop only 
//printf("Node#%d.string = '%s', .next = '%d' \n",list->first->key, list->first->string, list->first->next->key);

//iterate through list
// Here use startN != NULL because last node should also be retrieved.
/* while(startN->next != NULL) {
    printf("Node#%d.string = '%s', .next = '%d' \n",startN->key, startN->string, startN->next->key);
    startN = startN->next;
}*/

while(startN != NULL) {
    printf("Node#%d.string = '%s', .next = '%d' \n",startN->key, startN->string, startN->next->key);
    startN = startN->next;
 }

return 0;}
Improve this answer

Comments

0

I've weeded out the errors/flaws. Thanks for the advices, it helped me a lot to get this working. I had logic-flaws in int remove_end(LinkedList *list) aswell as in print_list (thanks to you guys for pointing out!)

..here the whole (working and tested(hopefully clean)) Implementation:

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

/********** GLOBALS *******************************/
#define OK 0
#define ERROR -1

/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
    int key;
    char string[1024];
    struct Node *next;  // pointer to next node
} Node;

/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
    struct Node *first;
    struct Node *last;
    int size;
} LinkedList;

/********** FUNCTION HEADERS **********************/
LinkedList* init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);

/*********** FUNCTION DEFINITIONS ***************/

/**
 * init_list Returns an appropriately (for an empty list) initialized struct List
 *
 * @return LinkedList *         ..ptr to the newly initialized list
 */
LinkedList * init_list() {
    printf("initializing list...\n");

    LinkedList *list = (LinkedList*) malloc(sizeof(LinkedList));

    list->first = NULL;
    list->last = NULL;
    list->size = 0;

    return list;
}

/**
 * Given a List, a key and a string adds a Node containing this
 * information at the end of the list
 *
 * @param list      LinkedList *    ..ptr to LinkedList
 * @param key       int             .. key of the Node to be inserted
 * @param string    char[]          .. the string of the Node to be inserted
 */
void insert_end(LinkedList *list, int key, char string[]) {
    printf("----------------------\n");

    list->size++;                    // increment size of list

    // intialize the new Node
    Node* newN = (Node*) malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string, string);
    newN->next = NULL;

    Node* oldLast = list->last;      // get the old last
    oldLast->next = newN;          // make new Node the next Node for oldlast
    list->last = newN;              // set the new last  in the list

    printf("new Node(%p) at end: %d '%s' %p \n", newN, newN->key, newN->string,newN->next);
}

/**
 * Given a List, a key and a string adds a Node, containing
 * this information at the beginning of the list
 *
 * @param list      LinkedList *    ..ptr to LinkedList
 * @param key       int             .. key of the Node to be inserted
 * @param string    char[]          .. the string of the Node to be inserted
 */
void insert_beginning(LinkedList *list, int key, char string[]) {
    printf("----------------------\n");

    list->size++;                    // increment size of list
    Node* oldFirst = list->first;    //get the old first node

    /* intialize the new Node */
    Node* newN = (Node*) malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string, string);
    newN->next = oldFirst;

    list->first = newN;              // set the new first

    /* special case: if list size == 1, then this new one is also the last one */
    if (list->size == 1)
        list->last = newN;

    printf("new Node(%p) at beginning: %d '%s' %p \n", newN, newN->key,newN->string, newN->next);
}

/**
 * Removes the first Node from the list
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_beginning(LinkedList *list) {
    printf("----------------------\n");

    if (list->size <= 0)
        return ERROR;

    list->size--;

    Node * oldFirst = list->first;

    printf("delete Node(%p) at beginning: '%d' '%s' '%p' \n", oldFirst,oldFirst->key, oldFirst->string, oldFirst->next);

    free(list->first);          //free it
    list->first = oldFirst->next;
    oldFirst = NULL;

    return OK;
}

/**
 * Removes the last Node from the list.
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_end(LinkedList *list) {
    printf("----------------------\n");

    /* special case #1 */
    if (list->size <= 0)
        return ERROR;

    /* special case #2 */
    if (list->size == 1) {
        free(list->first);
        list->first = NULL;
        list->last = NULL;
        return OK;
    }

    printf("delete Node(%p) at end: '%d' '%s' '%p' \n", list->last,list->last->key, list->last->string, list->last->next);

    list->size--;           // decrement list size
    Node * startNode = list->first;

    /* find the new last node (the one before the old last one); list->size >= 2 at this point!*/
    Node * newLast = startNode;
    while (newLast->next->next != NULL) {
        newLast = newLast->next;
    }

    free(newLast->next);    //free it
    newLast->next = NULL;   //set to NULL to denote new end of list
    list->last = newLast;   // set the new list->last

    return OK;
}

/**
 * Given a List prints all key/string pairs contained in the list to
 * the screen
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return  OK | ERROR
 */
int print_list(LinkedList *list) {

    printf("----------------------\n");

    if (list->size <= 0)
        return ERROR;

    printf("List.size = %d \n", list->size);

    Node *startN = list->first;  //get first

    /* iterate through list and print contents */
    do {
        printf("Node#%d.string = '%s', .next = '%p' \n", startN->key,startN->string, startN->next);
        startN = startN->next;
    } while (startN != NULL);

    return OK;
}

/**
 * Given a List, frees all memory associated with this list.
 *
 * @param list      LinkedList *        ..ptr to the list
 */
void free_list(LinkedList *list) {
    printf("----------------------\n");
    printf("freeing list...\n");

    if (list != NULL && list->size > 0) {
        Node * startN = list->first;
        Node * temp = list->first;

        do {
            free(temp);
            startN = startN->next;
            temp = startN;
        } while (startN != NULL);

        free(list);
    }
}

/**
 * Given a List and a key, iterates through the whole List and returns
 * the string of the first node which contains the key
 *
 * @param list      LinkedList *        ..ptr to the list
 * @param key       int                 .. the key of the Node to get the String from
 *
 * @return OK | ERROR
 */
char * get_string(LinkedList *list, int key) {
    printf("----------------------\n");

    Node *startN = list->first;  //get first

     /* if only one node.. */
     if(list->size == 1)
         return startN->string;

    /* iterate through list and find Node where node->key == key */
    while (startN->next != NULL) {
        if (startN->key == key)
            return startN->string;
        else
            startN = startN->next;
    }

    return NULL;
}

/*************** MAIN **************/
int main(void) {

    LinkedList *list = init_list();

    insert_beginning(list, 1, "im the first");
    insert_end(list, 2, "im the second");
    insert_end(list, 3, "im the third");
    insert_end(list, 4, "forth here");

    print_list(list);
    remove_end(list);
    print_list(list);
    remove_beginning(list);
    print_list(list);
    remove_end(list);
    print_list(list);
    printf("string at node with key %d = '%s' \n",2,get_string(list, 2));
    free_list(list);

    return OK;
}

Output: 

initializing list...
----------------------
new Node(00C31668) at beginning: 1 'im the first' 00000000 
----------------------
new Node(00C33E88) at end: 2 'im the second' 00000000 
----------------------
new Node(00C34298) at end: 3 'im the third' 00000000 
----------------------
new Node(00C346A8) at end: 4 'forth here' 00000000 
----------------------
List.size = 4 
Node#1.string = 'im the first', .next = '00C33E88' 
Node#2.string = 'im the second', .next = '00C34298' 
Node#3.string = 'im the third', .next = '00C346A8' 
Node#4.string = 'forth here', .next = '00000000' 
----------------------
delete Node(00C346A8) at end: '4' 'forth here' '00000000' 
----------------------
List.size = 3 
Node#1.string = 'im the first', .next = '00C33E88' 
Node#2.string = 'im the second', .next = '00C34298' 
Node#3.string = 'im the third', .next = '00000000' 
----------------------
delete Node(00C31668) at beginning: '1' 'im the first' '00C33E88' 
----------------------
List.size = 2 
Node#2.string = 'im the second', .next = '00C34298' 
Node#3.string = 'im the third', .next = '00000000' 
----------------------
delete Node(00C34298) at end: '3' 'im the third' '00000000' 
----------------------
List.size = 1 
Node#2.string = 'im the second', .next = '00000000' 
----------------------
string at node with key 2 = 'im the second' 
----------------------
freeing list...
Improve this answer

1 Comment

The code got reviewed on Codereview.stackexchange.com: codereview.stackexchange.com/q/164088/132855

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.