CODEWITHSUNDEEP
c++linked-list
hello
hello

Reputation: 1228

Understanding Linked List in C++

I am trying to understand the concept of linked lists. So far this is what I know and where I'm having problems to understand.

//create node
struct list
{
int id; //member var
list* next; //pointer to link next list item
}

//int main()

//create list head and set it to NULL
list* head = NULL;

//instantiate list node
list* newList = new list;

//insert a list
newList->id = 20;
newList->next = NULL;

This I do not really understand what's going on.

newList->next = head;
head = newList;

Upvotes: 0

Views: 282

Answers (2)

Brandon Buck
Brandon Buck

Reputation: 7181

NOTE: The memory "locations" I will reference in this answer are there purely for example are not meant to mimic the actual location these pointers might or might not ever point to.

Draw these relationships out on paper to visualize the results. Let's break it down by lines.

list *head = NULL;

And here is our visualization:

 *head (0x00)
+-----------+
|           |
|   NULL    |
|           |
+-----------+

Now, we follow these next lines:

list *newList = new list;
newList->id = 20;
newList->next = NULL;

And that visualization:

 *head (0x00)      *newList (0x3a)
+-----------+     +----+------+
|           |     | id | next |
|   NULL    |     +----+------+
|           |     | 20 | NULL |
+-----------+     +----+------+

And finally we end with your last bit:

newList->next = head;

And that alters the visualization thusly (reordered for clarity):

 *newList (0x3a) +->*head (0x00)
+----+------+    | +-----------+
| id | next |    | |           |
+----+------+    | |   NULL    |
| 20 | head------+ |           |
+----+------+      +-----------+

This has created the "link" that gives a LinkedList it's name. You link nodes together by some form of a reference. So what you've done is created a "head" or beginning of the list, and then you've created a secondary node in the list and placed it (logically) before head. Normally you'd then reassign your reference to newList to head since it's the new beginning of the list.

The next step would likely be (and I'm sure this what you meant with the erroneous bit that I ask about at the end of this question):

head = newList;

Which now changes the visualization to this:

 *head (0x3a)  +---> (0x00)
+----+------+  |   +-----------+
| id | next |  |   |           |
+----+------+  |   |   NULL    |
| 20 | 0x00----+   |           |
+----+------+      +-----------+

Also, what about the following line?

head = n; // What is 'n'? Where did you get it from? It doesn't appear anywhere else in your sample

EDIT

I altered the visualization to more accurately reflect what would be realistic. I wasn't paying attention to what I was doing when I posted the original answer so many thanks to José and his comment for bringing it to my attention the visualization was inaccurate.

In addition to altering the visuals I added a bit more information and wanted to take it a step further in saying that here's how you would use this linked list to loop over it's records.

list *node = head;
while (node != NULL) {
    std::cout << "The id is " << node->id << std::endl;
    node = node->next;
}

Upvotes: 6

R Sahu
R Sahu

Reputation: 206607

newList->next = head;
head = newList;

You start out with head set to NULL.
Then, you create a new node and let its next point to head, which is NULL.
Then, you set head to be the new node. Now, head points to a list that has one item in it.

Upvotes: 1

Related Questions