Linked Lists : When adding a element why is current.Next pointing to the new Node, and why do we overwrite the Current Node
So let's see what's happening line-by-line in the AddAtLast(object data)
method of the Linked List Class
Node newNode = new Node();
Create a new Node, this is the AddAtLast
methods goal in life
newNode.Value = data;
Assign some data to the Node
current.Next = newNode;
Assign the newNode
that was created to Current
. This is the Linked part of a Linked List
current = newNode;
Overwrite Current
(this must seem strange); I'll explain about this more later.
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.
- Reserving a physical part of memory and filling it with your new Object
- 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.
- Someone hands you a new Node.
- 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) - 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