I have a Node class as follows:-
namespace LinkedListDS
{
public class Node
{
public object data;
public Node next;
public Node(object data, Node next)
{
this.data = data;
this.next = next;
}
public object Data
{
get { return this.data; }
set { this.data = value; }
}
public Node Next
{
get { return this.next; }
set { this.next = value; }
}
}
}
My LinkedList class is as follows:-
namespace LinkedListDS
{
public class LinkedList
{
private Node head;
private int count;
public LinkedList()
{
this.head = null;
this.count = 0;
}
public bool Empty
{
get { return this.count == 0; }
}
public int Count
{
get { return this.count; }
}
public object Add(int index, object o)
{
if (index < 0)
throw new ArgumentOutOfRangeException();
if (index > count)
index = count;
Node current = this.head;
if (this.Empty || index == 0)
{
this.head = new Node(o, this.head);
}
else
{
for (int i = 0; i < index - 1; i++)
current = current.Next;
current.Next = new Node(o, current.Next);
}
count++;
return o;
}
}
}
When using the Add method as follows:-
class Program
{
static void Main(string[] args)
{
LinkedList a = new LinkedList();
a.Add(2, "first");
a.Add(77, "second");
a.Add(66, "third");
a.Add(32, "fourth");
Console.WriteLine();
Console.ReadLine();
}
}
The ints im passing in for the index are showing as
2 = 0
77 = 1
66 = 2
32 = 3
So its using the zero based index rather than the values Im passing in?
Also im not sure how the Next property is working to show the next item?
Regards
VulpesPosted Aug 14, 2013, 6:50 PM
for (int i = 0; i < index - 1; i++)
current = current.Next;
current is successively set to the Next node until it finishes up pointing to the node at index - 1.
In other words, when i reaches the final value of index - 2, current is set to the next node which is the one at index - 1.
Notice also that when you insert a node in the chain at 'index', the Next property of that node is set to what the Next property of the node at 'index - 1' pointed to before the insertion of the new node. So, the chain is broken to insert the new node but otherwise is maintained as it was before.
VulpesPosted Aug 25, 2013, 12:14 PM
If you insert a node after the current node, then you set current.Next to the new node.
However, the next node after the inserted node must then be what current.Next previously was.
This is why you have the old value of current.Next on the RHS whilst you're setting the new value on the LHS of the assignment statement.
Guest UserPosted Aug 25, 2013, 12:03 PM
Going by the video link I sent you, the prof states as a rule of thumb...
RHS have the old value, an operation and assignment to update the LHS with a new value, im just trying to visualise that.
Guest UserPosted Aug 25, 2013, 11:52 AM
http://www.youtube.com/watch?v=htzJdKoEmO0
Fast forward to 21.51 onwards.
Could you confirm this is the case?
VulpesPosted Aug 25, 2013, 11:45 AM
So, the new node is inserted in the chain before what was the next node if there is one or is otherwise just added at the end of the list (current.Next will then have been null).
Guest UserPosted Aug 25, 2013, 9:04 AM
Just to clarify, given the following expression:-
current.Next = new Node(data, current.Next);
The current.Next on the RHS of the assignment is a reference holding the previous Node's Next value to the new Node im adding? it then updates the current.Next to this newly added Node?
Thanks in advance!
Guest UserPosted Aug 15, 2013, 4:35 PM
VulpesPosted Aug 15, 2013, 4:28 PM
The 'for' statement is simply acting as a counter to iterate through the nodes from 'head' to the one at 'index - 1'.
It doesn't matter that the statement:
current = current.Next;
doesn't depend on the loop variable 'i' at all.
Guest UserPosted Aug 15, 2013, 3:20 PM
Given something you said earlier:-
for (int i = 0; i < index - 1; i++)
current = current.Next;
current is successively set to the Next node until it finishes up pointing to the node at index - 1.
Forgive my denseness here but how is the for loop actually setting current.Next to current? as it isnt referenced in the actual for loop itself?
Regards
VulpesPosted Aug 15, 2013, 3:24 AM
When it gets to index - 2, current will be set to the next Node after that which will be the one at index - 1.
The statement after the 'for' statement:
current.Next = new Node(o, current.Next);
then sets the node after that (i.e. the one at 'index') to the newly added node.
Note that the new node's Next property is set to the previous value of current.Next and will therefore point to the next node in the chain, if there is one.
Incidentally, this code is for a singly-linked list.
It's also possible to have a doubly-linked list where each node has both a next and prev property so you can traverse the collection in either direction, add nodes at either end or insert nodes either before or after the current node. The LinkedList in the .NET framework is of the doubly-linked type.
Guest UserPosted Aug 15, 2013, 2:24 AM
Regards to
"In other words, when i reaches the final value of index - 2, current is set to the next node which is the one at index - 1."
Where does the index - 2 come from? I assume this would be the 2nd to last index once the last value was inserted?
Regards
Guest UserPosted Aug 14, 2013, 6:38 PM
Stepping through the code I couldnt see where it adds to index -1, could you demo in the code ive listed please?
VulpesPosted Aug 14, 2013, 6:27 PM
So when a new Node is added at a certain index it's assigned to the Next property of the Node at (index - 1).
Guest UserPosted Aug 14, 2013, 6:07 PM
VulpesPosted Aug 14, 2013, 5:59 PM
So, this line:
resets the index to 0.
When you the add the second node with an index of 77, count is 1 and so the above line resets the index to 1.
Similarly, when you add the third and fourth nodes, the indices are reset to 2 and 3 respectively.
The above line is therefore making sure that there are no gaps in the indices of the linked list nodes.