-4

I'm trying to insert an entry at the start of a linked list, so if the list was empty before, the next of the last inserted node should obviously be 0/NULL. I just can't figure out why that isn't the case in my code.

I've already searched for answers but all I could find was setting list->head to 0, which I did in struct _list.

list.cpp

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

struct _node
{
    void *data;
    Node *next;
};

struct _list
{
    Node *head = nullptr;
};

List *list_create()
{ 
    List *list = (List *)malloc(sizeof(List));
    list->head = nullptr;
    return list;
}

void list_add(List *list, void *data)
{
    Node *current = (Node *)malloc(sizeof(Node));

    current->data = data;
    current->next = list->head;
    list->head = current;
}
unidentified
  • 1
  • 1
  • 1
    `malloc` does not do _anything_ with allocated memory (including initializing it to zero), so your `list_create` creates a list with undefined `head`. You should zero it manually. I suspect you're actually using C++ compiler because default values are [prohibited in C](https://stackoverflow.com/questions/13716913/default-value-for-struct-member-in-c), whilst allowed in C++ (but then you shouldn't be using C functions to allocate data). – yeputons Jan 05 '19 at 13:27
  • 2
    1. The prefix `_` is reserved for compiler implementations. 2. You never initialize `_node` instances properly with `NULL` for `data` or `next`, thus you shouldn't wonder. – πάντα ῥεῖ Jan 05 '19 at 13:27
  • 1
    You are in C++, use objects! – Matthieu Brucher Jan 05 '19 at 13:29
  • Did you just allocate a pointer in list_create, so your pointer points to an invalid pointer (which it incorrectly thinks is an invalid List)? Constructors would be a lot easier. – Kenny Ostrom Jan 05 '19 at 13:36
  • Also you should post a very short main which demonstrates the problem, so it is a [mcve] – Kenny Ostrom Jan 05 '19 at 14:27
  • You include "list.h" and use different names for the struct in this file, so I'm assuming that was a typo in creating this question. And wouldn't that be a stack, not a list? (because you insert at the front) – Kenny Ostrom Jan 05 '19 at 14:46
  • Don't use `malloc` in C++. Also don't use `NULL` or `0` for null pointers, use `nullptr`. – Jesper Juhl Jan 05 '19 at 15:05
  • Since you are using C++, why aren't you using `std::list`? – Eljay Jan 05 '19 at 15:05
  • @Eljay I'm still a beginner in C or C++ (though I have always been pretty sure I'm programming in C) and I have never used : or :: – unidentified Jan 05 '19 at 15:12
  • Ahhh, then you could probably really use a [good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) on C++. – Eljay Jan 05 '19 at 15:25

2 Answers2

1

malloc allocates memory. It does not call a constructor. So this will result in allocated memory for a "list_type" but it will contain uninitialized garbage.

Node *current = (Node *)malloc(sizeof(Node));

But that is okay for now, because you follow it up by initializing everything.

current->data = data;
current->next = list->head;

[deleted section where I lecture you about using an object for encapsulation for maintainability]

Now let's look at your list type:

struct List
{
    Node *head = 0;
};

Default values in the class (struct) declaration are applied in any constructor. But malloc is not a constructor, nor does it call a constructor. It just gets the memory needed. So if you malloc sizeof(List) you will NOT get anything initialized.

However, you don't even do that. You allocate space for another pointer to a list. So list_create gives you a pointer to some allocated memory for another pointer to random garbage (which is not a List, nor would it be valid if it were allocated). Although I suppose there is a chance that sizeof(List) and sizeof(List*) happen to be the same on your compiler, but it's UB if you just got lucky like that.

return  (List *)malloc(sizeof(List *));

You meant to do 

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

So now you have something the size of a list, and you would then have to add this (because you didn't use a constructor, default or otherwise):

list->head = nullptr; // we're supposed to use "nullptr" now for type safety
return list;

but you don't have that. You just return the invalid pointer. So those are the two errors in that function.

[deleted section where I lecture you on using an object. You can get that from Samed Kahyaoglu's answer. But basically you have to go through a constructor or default constructor in order to use that default value in the header declaration of a class.]

To demonstrate that head was initialized:

int main() {
    List * list = list_create();
    list_add(list, nullptr);
    std::cout << list->head->next << std::endl;
}

output before fix:
CDCDCDCD

output after fix:
00000000

My compiler initializes malloc'ed data with CDCDCDCD in debug builds to make it easy to spot uninitialized data. Release builds would probably just have whatever random junk was there before.

Kenny Ostrom
  • 5,639
  • 2
  • 21
  • 30
  • incidentally, "new" does call a constructor, so new/delete is way better than malloc/free, but it's still bad in modern c++, unless entirely encapsulated within your class. So you can use new/delete on Node, but your problem was with List not getting constructed. – Kenny Ostrom Jan 05 '19 at 14:25
  • Well, thanks for the detailed answer, but sadly I've already tried `list->head = nullptr` in `list_create` but that didn't change anything (and yes, I changed the `sizeof(List *)` to `sizeof(List)`). – unidentified Jan 05 '19 at 14:29
  • It does appear to fix the "why didn't it get initialized?" question, when I run it in the debugger. – Kenny Ostrom Jan 05 '19 at 14:37
0

You are completely wrong, excuse me. This is how it should look like;

//first, define DataType or change DataType as you want to use

struct Node
    {
       DataType data;
       Node* next;
    };
struct List
{
    Node *head;
    void create();
    void add();
};

void List::create()
{
    head = NULL;
}

void List:add(DataType data)
{
   Node* newNode = new Node;
   newNode -> data = data;
   newNode -> next = NULL;
   Node* traverse = head;
   while(traverse){
      traverse->next; } // goes till finding last node then goes its next which is null
   traverse = newNode;
   return;
}
Samed Kahyaoglu
  • 55
  • 5