Linked list, really need some basic help!

[Simon342]

Hi so I'm trying to create a linked list. Have been trying to watch youtube clips, wikipedia etc but I'm just getting more and more confused. I do however grasp the idea behind the list that the first "box" will link to the next which will contain some sort of data and so on. Don't just know how to create some c++ code of it.

First of all i start whit:

struct Node  
{
 int data;
 node *next; // this will be the thing that points to my next box, right? 
};

Then I'm really confused what to type in the main.

[KyleMiles]

Think of it like a chain, you need to use one link to get to the next, and you can't get to that one before getting to the one before it.

struct Node  
{
 int data;
 Node * next; //Yes
};

Now you can make some instances of it:

Node a;
Node * b;
Node * c;
Node * d;

Link them:

a.next = b;
b->next = c;
c->next = d;
d->next = NULL;

And that should work... It may have some syntax errors though, sorry.

- Kyle

[D80DSL3A]

I think we just had a 4 page thread on the subject pass through here:

http://www.cplusplus.com/forum/beginner/85296/

[toum]

I don't know about syntax errors, but I can guarantee you'll segfault.

Node a;
Node * b = new Node;
Node * c = new Node;
Node * d = new Node;

[Simon342]

Thanks a lot Kyle!

It makes a lot more sense now :)

But if i also would like to put in some data into my Node and not just link it, how can you do that on a good way? :)

Edit:Toum do you know why it will be segfault? :/

Thanks for the link fun2code! Will read it now!

[maeriden]

Structs members are public by default, so you can just do

Node a;
a.data = 0;

You can also create a constructor to set 'data' when a Node is created

struct Node  
{
 Node(int n) {data = n;}
 int data;
 node *next;
};

Node a(0);
Node* b = new Node(0);

The segfault happens because when b, c and d are defined they point to some memory location in which you don't have permission to read/write, so you can't set 'next'. 'new' returns the location of a memory block in which you have those permissions.

[Simon342]

Thanks Maeriden! Will try this code :)

One question thought since i haven't found any good answers on it.
Node* b = new Node(0);

Node* b declares a new refernece object called b, right? But what does "new node(0)" do? Is new a function or just some name that you did pick?

[toum]

Node* b declares that b will hold the address of a Node object.
new is a C++ operator that is used to allocate memory.

The line
Node* b = new Node(0);
allocates memory for a Node object, calls its constructor with 0 as parameter, and returns the address of the constructed object into b.

[maeriden]

Node* b declares a new refernece object called b, right?

Not exactly. It's a pointer. in C++ a "reference" is another type of data, but conceptually you're there: it's a variable that is not a Node, but refers to (points to) a Node existing somewhere in memory.

But what does "new node(0)" do? Is new a function or just some name that you did pick?

'new' is an operator of C++. It is used to obtain valid memory in which to store data (read previous post). The reason for this is that when you run a program it uses an area of memory, called 'stack', which isn't exactly large (IIRC it's usually 1MB, while computers now are around 4GB of total memory). Now, if you tried to create ten millions of ints on the stack (int n[10000000];) you wouldn't have enough memory for that, the program tries to write beyond the stack limit and that causes a crash (stack overflow). So you need more memory, and you obtain it using 'new'

You can read about 'new' here http://www.cplusplus.com/doc/tutorial/dynamic/

[Simon342]

Thanks alot for the help! Have been reading and thanks to evryone that have helped me i think i start to understand little of the linked list.

Working right now on a program that will add the highes value as the first value, second highest value as nummber 2 in the list etc. Although it does the opposite right now. Anyone that has any ideas? :) It does work if i remove my if-statements in the bool insert functions, so i guess its something wrong there? Thanks!

#include <iostream>
using namespace std;

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

  bool insert(List_Type *&list,int value);
int main()
{
  bool run = true;
  string name;
  int value = 0;
  List_Type *list;
  list = nullptr;

  while (run == true)
    {

      cout << "Vilken funktion vill du anvanda?";
      cin >> name;
      
      if (name == "insert")
	{
	  cout << "varde";
	  cin >> value;
	  insert(list, value);
	}
      else if (name == "quit")
	{
	  run = false;
	}

    }
  List_Type *te = list;
  while (te != nullptr)
    {
      cout << te->data << endl;
      te=te->next;
    }
  return 0;
}


bool insert(List_Type *&list,int value)
{
 
   if (list == nullptr)
    {
      List_Type *temp;
      temp = new List_Type;
      temp->data = value;
      temp->next = list;
      list = temp;
       }
  else if(list->data < value)
    {
      insert(list->next,value);
      }
}

[maeriden]

Suppose you call insert() for the first time with 'value' = 4. The list is created and 'data' become 4. Then you call insert(list, 3). Since 'data' < 'value' (4 < 3) is false, the value is not inserted.
Suppose you call insert(list, 5) the second time. (4 < 5) is true, so the second element in the list becomes 5, giving the reverse order you see.
Note that if any 'value' you input is smaller than any 'data' already in the list, it will not inserted at all.

Notes:
- I'd change line 55 to be temp->next = nullptr. You want it to be null, not to point to the list (which is null at that point, but it makes the code more readable)
- You don't deal with 'value' == 'data'. Is it supposed to ignore the input if it is already present in the list?
- Just changing the code to (list->data > value) won't solve the issue. You need to implement a mechanism to make the values in the list "slide" when a new value has to be inserted in the middle of it. And a way to assign 'data' to 'value' even when 'list' is not nullptr
- insert() is declared as returning a bool, but it does not return anything at all. If you don't care to verify if an item is successfully inserted change it to void

[devonrevenge]

seriously if fun2codes link doesnt have the answer to your question i will eat my own head and post it on youtube