can you help me with linked lists? im close, so very close to grasping it.

Pages: 123... 5
im new to the keyword new, i got the impression there would be an easier more dynamic way of creating new nodes and linking them, while trying to create my own linked list i feel i have just created a struct then pointer to pointer struct and so on rather than little nodes of info.

either way somethings missing in there(thas what my mummah always said )



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

struct node
{
    int num;
    node* link;
};


int main ()

{
  node *base;
  base = new node;

  base->num = 5;
  node *second;
  second = new node;
  second->num = 10;
  second->link = base;
  cout<< second->link->num<<endl;
  cout<< second->num;
  return 0;
}
Last edited on
please tell me i havnt been struggling to grasp this, its the most simple example of a linnked list isnt it.
is there a more elegant way to link the lists and initialize the ints or do i go;
1
2
node *base;
base = new node [//however many nodes//]; 


am i grasping it? where do i go from here??
Yeah this is a simple example of a linked list but i think you linked it the wrong way.

Try:

1
2
3
4
5
6
7
8
9
10
11
  node *base;
  base = new node;

  base->num = 5;
  node *second;
  second = new node;
  second->num = 10;
  base->link = second;
  second->link=null;   //this is the end of the list.
  cout<< base->num<<endl;
  cout<< second->num;


HTH,
Aceix.
Also, in your second post,

It is right to do: node *base; base = new node;
It assigns memory to the new node pointer.

Thanks,
Aceix.
oh yeah is backwards strange, why does this mixed up naive Frankencode not work?
the debugger thinksnode is no longer a pointer!?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>

using namespace std;

struct node
{
    int num;
    node* link;
};


int main ()

{
  node *base;
  base = new node[10];
  for (int a = 1; a <10;a++)
  {
      base[1]->num=a;
      base[1]->link=base [a+1];

  }

  cout << base->link->link->link->num;
  return 0;
}


Last edited on
this made my compiler flip out...makes sense to me, why it not work?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>

using namespace std;

struct node
{
    string word;
    node* link;
};

int main ()
{

 node *base; base = new node;
 node *thing; thing = new node;
 node *otherthing; otherthing = new node;
 node *lastthing; lastthing = new node;

base->word = "i am the first word";
 base->link = thing;
 base->link->word = "i am the second word";
 base->link->link = otherthing;
 base->link->link->word = "i am the third word";
 base->link->link->link = lastthing;
 base->link->link->link->word = "i am the fourth and final word";



cout << lastthing->link->link->link->word<<endl;
 cout<< lastthing->link->link->word<<endl;
 cout<<lastthing->link->word<<endl;
 cout<<lastthing->word;

   return 0;
}
Last edited on
lasthing should be base
oh thank you devonrevenge you are so amazing could you help me further with linked lists, how could i dynamicly create nodes and iterate through them, the internet doesnt realy explain in a way i understand.
what about this, why cant i have instances of base?? and why does it compile??

1
2
3
4
5
6
7
node *base [3];
 for (int a = 0; a>3; a++)
 {
    base[a] = new node;
 }

base[1]->link = base[2];
OK. It seems like you are getting close to seeing what the link member is for.
You have it working in your 4th previous post right?
The one that starts with:
this made my compiler flip out...


Your observation that all lastthings should be bases was spot on, but you only changed it where the assignments are made, not where the cout-ing is being done.

You have asked:

...how could i dynamicly create nodes and iterate through them...

Doing this would be the logical next step.
I'll try guiding you here.

Let's start with the simplest function I can think of for adding nodes. Lets call this function push_front because we will be using it to push new nodes onto the front of the list. Each new node becomes the first in the list. The node which was first becomes second (ie newFirst->link = oldFirst) and so on.

Here's some code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
using namespace std;

struct node
{
    string word;
    node* link;
};

// returns a pointer to the new front of the list
node* push_front( node* front, string Word )
{
    node* temp = new node;// this will become the new front node (1st in the list)
    temp->word = Word;// copy the data over
    temp->link = front;// the new node points to the old front node
    return temp;// new front node
}

int main()
{
    node* base = NULL;// this will ALWAYS point to the FIRST node in the list
                    // (or = NULL if there are none)

    //  add a few nodes to the list
    base = push_front(base, "first word");
    base = push_front(base, "second word");
    base = push_front(base, "third word");

    // display the list contents
    cout << base->word << endl;
    cout << base->link->word << endl;
    cout << base->link->link->word << endl;

    cout << endl;
    return 0;
}

The only thing new to you here should be the push_front(). Play around with this code and ask if you don't see how the function works.

I'll save a function to iterate through the list and display the words for next time (ie, if we don't get stuck here - at push_front ).
Last edited on
thank you so much fun2code, ive been trying soo hard to grasp this my concentration started waning (thas why i wind up chatting on this) fiddling with my compiler then getting distracted looking at the tuts online then getting distracted looking at facebook and th news, i have plenty to get on with now:)
Last edited on
kay i understood that and played with it, i added num in the struct, so now they have values, ive just started thinking about sorting them.
Good.

Slow down though.
Can you iterate through the list from the front (base) to the end in a while loop?
How about a displayList() function first?

Sorting the list will require this and other skills.
Keep it simple.
Ive made a primitive bubble sorting algorithm function, is there a more elegant way to cycle through the code.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <string>

using namespace std;

struct node
{
    int num;
    string word;
    node* link;
};




node* Add_Node (node *front, string word, int number)
{
    node* temp = new node;
    temp->num = number;
    temp->word = word;
    temp->link = front;
    return temp;
}

void swap_em (node *npoint)
{
    int temp;
    if ( npoint->num > npoint->link->num)
    {
        temp=npoint->num;
        npoint->num=npoint->link->num;
        npoint->link->num = temp;

    }


}

int main ()
{
node *base = NULL;
base = Add_Node (base, "coo coo cachoo",8);
base = Add_Node (base, "i am the eggman",9);
base = Add_Node (base, "i am the wallrus",5);
base = Add_Node (base, "i dont know the rest",4);



cout<<base->num<<endl;
cout<<base->link->num<<endl;
cout<<base->link->link->num<<endl;
cout<<base->link->link->link->num<<endl;
cout<<endl;

swap_em(base);
swap_em(base->link);
swap_em(base->link->link);

cout<<base->num<<endl;
cout<<base->link->num<<endl;
cout<<base->link->link->num<<endl;
cout<<base->link->link->link->num<<endl;


   return 0;
}
Where's your list class?
Create a list class that holds your nodes.

Incomplete example:
1
2
3
4
5
6
7
8
9
10
11
12
class List {
public:

    struct Node {
        string word;
        Node *next;
    };

private:

    Node start;
};


You can make a decent List data structure if you know how to use destructors and constructors. Hint: Nodes can have them too.
hrmm kay will look
i created a display list function, but i havnt seen the benefit of a struct being in class yet.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <string>


struct node
{
    int num;
    string word;
    node* link;
};


node* add_node (list::node* front,int number,string word )
{
    list::node* temp = new list::node;
    temp->num = number;
    temp->word = word;
    temp->link = front;
    
    return temp;
    
}


void displaylist (list::node* conductor)
{
for(int a = 0; a<6 ; a++)
{
cout<<conductor->word;
cout<<conductor->num<<endl;
conductor = conductor -> link;
cout<<endl;
}
}



int main ()
{

list::node *base=NULL;
base = add_node(base,6," Lay on the ground quite still  ");
base = add_node(base,4," Find fresh underpants to try on ");
base = add_node(base,8," Keep like that day after day  ");
base = add_node(base,2," If you're attacked by a Lion ");
base = add_node(base,7," Pretend you are very ill ");
base = add_node(base,9," Perhaps the lion will go away ");

displaylist(base);


   return 0;
}
Last edited on

i see i have to create the list in the class so i can manage it from there...
Last edited on
I will give you a bad analogy.
A list is a car, a node is its engine. What you do now is, you use the engine without a car! Put the engine in a car. Put the nodes into a list.

Then you can write the add_node() and display() functions internally to the list. Otherwise you might as well be using C instead of C++.

And then you can also use a destructor, so that you don't have memory leaks (for every new there must be a delete). You work a bit more to code your list but you work less to actually use it.
Good job on the displayList(). It will work.

There is 1 obvious problem with it though, it works for lists of 6 nodes only.

I suppose you could correct for this by passing the # of nodes to the function, but you shouldn't be relying on that.

There is a special condition which applies only at the end of the list.

What is the value of next for the last node in the list?
ie. If last = pointer to the last node in the list, what is:
last->next = ?

It's NULL !!
So you want to keep going until you get to the node with next == NULL OK?

As in:
1
2
3
4
5
6
7
8
9
10
11
void displaylist (list::node* conductor)
{
//    for(int a = 0; a<6 ; a++)
    while( conductor != NULL )
    {
        cout<<conductor->word;
        cout<<conductor->num<<endl;
        conductor = conductor -> link;// when we pass the last one
        cout<<endl;//    conductor will be NULL
    }
}

Pages: 123... 5