Linked Lists : When adding a element why is current.Next pointing to the new Node, and why do we overwrite the Current Node

Question

I am a beginner to C# and I am picking it up by solving data structures case scenarios. I need help visualizing what is happening in the following code snippet

public void AddAtLast(object data)
{
   Node newNode = new Node();
   newNode.Value = data;
   current.Next = newNode;
   current = newNode;
   Count++;
}

What part I have understood

I am aware that a new node is being added at the end of the linked list. Also, the new node is getting its value from the function argument.

What I need help with

I am particularly thinking why current.Next is pointing to newNode, shouldn't it point to NULL since my newNode will be placed at the end of the linked list and so it should point to NULL.

Also, why are we doing current=newNode ?

I understand why count++ is present probably because that want to keep track of position at which the new element is added but correct me if my understanding is wrong with this.

Answer 1

current is the candidate position for next AddAtLast operation, that is the end node of the linked list.

I understand why count++ is present probably because that want to keep track of >position at which the new element is added but correct me if my understanding >is wrong with this .

For the linked list structure you showed here, while the count is used to keep track of the number of nodes, the current is to keep track of current to-be-add-at-last position(that is old last node in the linked list before adding newNode) to facilitate AddAtLast operation. After adding newNode at old current by AddAtLast method, your current will be moved and refer to updated last node(that is newNode which was added just now).

Answer 2

So let's see what's happening line-by-line in the AddAtLast(object data) method of the Linked List Class

1. Node newNode = new Node();

Create a new Node, this is the AddAtLast methods goal in life

2. newNode.Value = data;

Assign some data to the Node

3. current.Next = newNode;

Assign the newNode that was created to Current. This is the Linked part of a Linked List

4. current = newNode;

Overwrite Current (this must seem strange); I'll explain about this more later.

5. Count++

Increment the Count of the Linked List, Its nice to know the size of a list, without having to traverse all its elements. This is just a short hand way of always knowing the count.

---

The first thing you have to remember

Is in C# (and many other languages), objects/Classes are a Reference Type. When you create Current (or any other object/class) you are doing 2 things.

1. Reserving a physical part of memory and filling it with your new Object
2. Creating a Reference (aka Address, aka Pointer) to that memory. Think of addresses just like a Post-It-Note to something that exists somewhere in your house.

When you overwrite a reference, you actually don't destroy the memory, just like if you scribbled out the address on a Post-It-Note and wrote something else. Your shoes still live in the cupboard. The only exception to this in .Net is if there are no more references left to you object/class the Garbage Collector (your mum) will come and clean it up and throw it away.

By calling current = newNode; it seems like we just lost overwrote it, and lost all references to that node (we were tracking last time), but we didn't.

---

The second thing to remember

The Clever-Clogs who invented the Linked List knew we had to keep track of the items somehow, so they envisaged when a Node gets added, somewhere some other node needs to have a Link to it.

This is what this line of code (current.Next = newNode) was all about. Make sure its actually linked in the list. Yeah so we overwrote it, but we now know that while someone else is Referencing the Node its not going to be cleaned up. Additionally, if we want to find it again, all we have to do is find the first Node and traverse the linkages.

---

Another way of thinking about it

Think of Current as a bucket, in that bucket you have a Node, and on that Node is a piece of paper called next.

1. Someone hands you a new Node.
2. You studiously write the name of this new node (that someone gave us) on the Node you currently have in the bucket (the Next/Link Post-It-Note every node has)
3. You tip the bucket out on the floor and your put your new Node in the bucket.

But you have to remember, the Node you tipped out is still around somewhere (in-fact, there is likely another Node around with its name on it too, just like you wrote your new Nodes new name on it). Although, we cant access them easily, they are still there if we traverse the Linkages

In essence, this is how a Linked List works, its just a bunch of Nodes with other nodes names written on it.

We keep track of the list with tools like Current/Temp, and First/Head (Buckets) in the class that encapsulates this logic. Sometimes we have a Count to make it easier to know how many nodes we are tracking. Though truly, the most important part of a Linked List is the First/Head bucket. Without it we cannot traverse the list.

Current/Temp in your original method just makes us easy for us to find the last node, so you don't have to traverse the list to find it

Example