Simple LinkedList
$begingroup$
I guess this has been made a couple of times by now, but i wanted to take my chance on creating a simple generic linked list in c#.
What do you think ?
This is the main class.
public class LinkedList<T>: IEnumerator<T>
{
private Node<T> head;
private Node<T> tail;
public T Current
{
get { return myCurrentNode.GetValue(); }
}
object IEnumerator.Current => Current;
private Node<T> myCurrentNode;
public LinkedList()
{
head = null;
tail = null;
}
public void Add(T value)
{
if (head == null && tail == null)
{
head = new Node<T>(value);
tail = head;
Reset();
return;
}
tail.SetNextNode(new Node<T>(value));
tail = tail.GetNextNode();
}
public void RemoveCurrentNode()
{
var node = new Node<T>();
node.SetNextNode(head);
while (node.GetNextNode() != myCurrentNode)
{
node = node.GetNextNode();
}
var nextNode = myCurrentNode.GetNextNode();
node.SetNextNode(nextNode);
if (head == myCurrentNode)
{
head = nextNode;
}
if (tail == myCurrentNode)
{
tail = node;
}
myCurrentNode = nextNode;
}
public bool MoveNext()
{
var nextNode = myCurrentNode.GetNextNode();
if (nextNode != null)
{
myCurrentNode = nextNode;
return true;
}
return false;
}
public void Reset()
{
myCurrentNode = new Node<T>();
myCurrentNode.SetNextNode(head);
}
public void Dispose()
{
myCurrentNode = null;
head = null;
tail = null;
}
}
Node class.
public class Node<T>
{
private T _value;
private Node<T> _nextNode;
public Node()
{
}
public T GetValue()
{
return _value;
}
public Node(T Value)
{
_value = Value;
}
public Node<T> GetNextNode()
{
return _nextNode;
}
public void SetNextNode(Node<T> nextNode)
{
_nextNode = nextNode;
}
}
And three unit tests to check my implementation.
public class LinkedListTest
{
private LinkedList.LinkedList<int> linkedList;
private List<int> initialList;
[Fact]
public void LinkedListCanBeEnumerated()
{
//arange
InitializeLinkedList(100);
//act
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
}
private void InitializeLinkedList(int howMany)
{
linkedList = new LinkedList.LinkedList<int>();
initialList = Enumerable.Range(1, howMany).ToList();
initialList.ForEach(i => linkedList.Add(i));
}
[Fact]
public void RemovingCurrentNodeShouldAlterTheList()
{
//arange
InitializeLinkedList(100);
//act
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(1));
}
[Fact]
public void RemovingTailNodeShouldResultInADifferentTailNode()
{
//arange
InitializeLinkedList(3);
//act
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[3];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(3));
}
}
c# linked-list reinventing-the-wheel
New contributor
$endgroup$
add a comment |
$begingroup$
I guess this has been made a couple of times by now, but i wanted to take my chance on creating a simple generic linked list in c#.
What do you think ?
This is the main class.
public class LinkedList<T>: IEnumerator<T>
{
private Node<T> head;
private Node<T> tail;
public T Current
{
get { return myCurrentNode.GetValue(); }
}
object IEnumerator.Current => Current;
private Node<T> myCurrentNode;
public LinkedList()
{
head = null;
tail = null;
}
public void Add(T value)
{
if (head == null && tail == null)
{
head = new Node<T>(value);
tail = head;
Reset();
return;
}
tail.SetNextNode(new Node<T>(value));
tail = tail.GetNextNode();
}
public void RemoveCurrentNode()
{
var node = new Node<T>();
node.SetNextNode(head);
while (node.GetNextNode() != myCurrentNode)
{
node = node.GetNextNode();
}
var nextNode = myCurrentNode.GetNextNode();
node.SetNextNode(nextNode);
if (head == myCurrentNode)
{
head = nextNode;
}
if (tail == myCurrentNode)
{
tail = node;
}
myCurrentNode = nextNode;
}
public bool MoveNext()
{
var nextNode = myCurrentNode.GetNextNode();
if (nextNode != null)
{
myCurrentNode = nextNode;
return true;
}
return false;
}
public void Reset()
{
myCurrentNode = new Node<T>();
myCurrentNode.SetNextNode(head);
}
public void Dispose()
{
myCurrentNode = null;
head = null;
tail = null;
}
}
Node class.
public class Node<T>
{
private T _value;
private Node<T> _nextNode;
public Node()
{
}
public T GetValue()
{
return _value;
}
public Node(T Value)
{
_value = Value;
}
public Node<T> GetNextNode()
{
return _nextNode;
}
public void SetNextNode(Node<T> nextNode)
{
_nextNode = nextNode;
}
}
And three unit tests to check my implementation.
public class LinkedListTest
{
private LinkedList.LinkedList<int> linkedList;
private List<int> initialList;
[Fact]
public void LinkedListCanBeEnumerated()
{
//arange
InitializeLinkedList(100);
//act
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
}
private void InitializeLinkedList(int howMany)
{
linkedList = new LinkedList.LinkedList<int>();
initialList = Enumerable.Range(1, howMany).ToList();
initialList.ForEach(i => linkedList.Add(i));
}
[Fact]
public void RemovingCurrentNodeShouldAlterTheList()
{
//arange
InitializeLinkedList(100);
//act
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(1));
}
[Fact]
public void RemovingTailNodeShouldResultInADifferentTailNode()
{
//arange
InitializeLinkedList(3);
//act
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[3];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(3));
}
}
c# linked-list reinventing-the-wheel
New contributor
$endgroup$
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, bothhead
andtail
arenull
), you create two nodes, one in theAdd
method, and one inReset
which is called fromAdd
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.
$endgroup$
– Abigail
3 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago
add a comment |
$begingroup$
I guess this has been made a couple of times by now, but i wanted to take my chance on creating a simple generic linked list in c#.
What do you think ?
This is the main class.
public class LinkedList<T>: IEnumerator<T>
{
private Node<T> head;
private Node<T> tail;
public T Current
{
get { return myCurrentNode.GetValue(); }
}
object IEnumerator.Current => Current;
private Node<T> myCurrentNode;
public LinkedList()
{
head = null;
tail = null;
}
public void Add(T value)
{
if (head == null && tail == null)
{
head = new Node<T>(value);
tail = head;
Reset();
return;
}
tail.SetNextNode(new Node<T>(value));
tail = tail.GetNextNode();
}
public void RemoveCurrentNode()
{
var node = new Node<T>();
node.SetNextNode(head);
while (node.GetNextNode() != myCurrentNode)
{
node = node.GetNextNode();
}
var nextNode = myCurrentNode.GetNextNode();
node.SetNextNode(nextNode);
if (head == myCurrentNode)
{
head = nextNode;
}
if (tail == myCurrentNode)
{
tail = node;
}
myCurrentNode = nextNode;
}
public bool MoveNext()
{
var nextNode = myCurrentNode.GetNextNode();
if (nextNode != null)
{
myCurrentNode = nextNode;
return true;
}
return false;
}
public void Reset()
{
myCurrentNode = new Node<T>();
myCurrentNode.SetNextNode(head);
}
public void Dispose()
{
myCurrentNode = null;
head = null;
tail = null;
}
}
Node class.
public class Node<T>
{
private T _value;
private Node<T> _nextNode;
public Node()
{
}
public T GetValue()
{
return _value;
}
public Node(T Value)
{
_value = Value;
}
public Node<T> GetNextNode()
{
return _nextNode;
}
public void SetNextNode(Node<T> nextNode)
{
_nextNode = nextNode;
}
}
And three unit tests to check my implementation.
public class LinkedListTest
{
private LinkedList.LinkedList<int> linkedList;
private List<int> initialList;
[Fact]
public void LinkedListCanBeEnumerated()
{
//arange
InitializeLinkedList(100);
//act
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
}
private void InitializeLinkedList(int howMany)
{
linkedList = new LinkedList.LinkedList<int>();
initialList = Enumerable.Range(1, howMany).ToList();
initialList.ForEach(i => linkedList.Add(i));
}
[Fact]
public void RemovingCurrentNodeShouldAlterTheList()
{
//arange
InitializeLinkedList(100);
//act
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(1));
}
[Fact]
public void RemovingTailNodeShouldResultInADifferentTailNode()
{
//arange
InitializeLinkedList(3);
//act
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[3];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(3));
}
}
c# linked-list reinventing-the-wheel
New contributor
$endgroup$
I guess this has been made a couple of times by now, but i wanted to take my chance on creating a simple generic linked list in c#.
What do you think ?
This is the main class.
public class LinkedList<T>: IEnumerator<T>
{
private Node<T> head;
private Node<T> tail;
public T Current
{
get { return myCurrentNode.GetValue(); }
}
object IEnumerator.Current => Current;
private Node<T> myCurrentNode;
public LinkedList()
{
head = null;
tail = null;
}
public void Add(T value)
{
if (head == null && tail == null)
{
head = new Node<T>(value);
tail = head;
Reset();
return;
}
tail.SetNextNode(new Node<T>(value));
tail = tail.GetNextNode();
}
public void RemoveCurrentNode()
{
var node = new Node<T>();
node.SetNextNode(head);
while (node.GetNextNode() != myCurrentNode)
{
node = node.GetNextNode();
}
var nextNode = myCurrentNode.GetNextNode();
node.SetNextNode(nextNode);
if (head == myCurrentNode)
{
head = nextNode;
}
if (tail == myCurrentNode)
{
tail = node;
}
myCurrentNode = nextNode;
}
public bool MoveNext()
{
var nextNode = myCurrentNode.GetNextNode();
if (nextNode != null)
{
myCurrentNode = nextNode;
return true;
}
return false;
}
public void Reset()
{
myCurrentNode = new Node<T>();
myCurrentNode.SetNextNode(head);
}
public void Dispose()
{
myCurrentNode = null;
head = null;
tail = null;
}
}
Node class.
public class Node<T>
{
private T _value;
private Node<T> _nextNode;
public Node()
{
}
public T GetValue()
{
return _value;
}
public Node(T Value)
{
_value = Value;
}
public Node<T> GetNextNode()
{
return _nextNode;
}
public void SetNextNode(Node<T> nextNode)
{
_nextNode = nextNode;
}
}
And three unit tests to check my implementation.
public class LinkedListTest
{
private LinkedList.LinkedList<int> linkedList;
private List<int> initialList;
[Fact]
public void LinkedListCanBeEnumerated()
{
//arange
InitializeLinkedList(100);
//act
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
}
private void InitializeLinkedList(int howMany)
{
linkedList = new LinkedList.LinkedList<int>();
initialList = Enumerable.Range(1, howMany).ToList();
initialList.ForEach(i => linkedList.Add(i));
}
[Fact]
public void RemovingCurrentNodeShouldAlterTheList()
{
//arange
InitializeLinkedList(100);
//act
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[100];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(1));
}
[Fact]
public void RemovingTailNodeShouldResultInADifferentTailNode()
{
//arange
InitializeLinkedList(3);
//act
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.MoveNext();
linkedList.RemoveCurrentNode();
linkedList.Reset();
int array = new int[3];
int index = 0;
while (linkedList.MoveNext())
{
array[index++] = (linkedList.Current);
}
//assert
array.ToList().ForEach(i => i.ShouldNotBe(3));
}
}
c# linked-list reinventing-the-wheel
c# linked-list reinventing-the-wheel
New contributor
New contributor
edited 3 hours ago
Rick Davin
3,167718
3,167718
New contributor
asked 5 hours ago
user297876user297876
1211
1211
New contributor
New contributor
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, bothhead
andtail
arenull
), you create two nodes, one in theAdd
method, and one inReset
which is called fromAdd
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.
$endgroup$
– Abigail
3 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago
add a comment |
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, bothhead
andtail
arenull
), you create two nodes, one in theAdd
method, and one inReset
which is called fromAdd
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.
$endgroup$
– Abigail
3 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, both
head
and tail
are null
), you create two nodes, one in the Add
method, and one in Reset
which is called from Add
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.$endgroup$
– Abigail
3 hours ago
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, both
head
and tail
are null
), you create two nodes, one in the Add
method, and one in Reset
which is called from Add
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.$endgroup$
– Abigail
3 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Collection != enumerator
The main problem I see here is that LinkedList<T>
implements IEnumerator<T>
instead of IEnumerable<T>
. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext()
and Current
, instead of being able to use foreach
. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.
IEnumerable<T>
represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield
).
IEnumerator<T>
represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach
statement (which calls GetEnumerator
on the given enumerable to obtain an enumerator).
The above means that myCurrentNode
does not belong in this class - it should be part of an enumerator. The same goes for Current
, MoveNext
, Reset
and Dispose
.
Regarding RemoveCurrentNode
, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode
also has to perform a linear search to find the preceding node.
Take a look at System.Collections.Generic.LinkedList<T>
to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.
Other notes
IEnumerator.Reset
is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset
.- Note that
IEnumerable<T>.GetEnumerator
is quite easy to implement withyield
. - There's no need to initialize
head
andtail
tonull
- that's their default value already. - There's also no need for disposal here - there are no unmanaged resources here that require disposal.
- Why does
Node
use Java-style get and set methods instead of properties? I'd expect to seepublic T Value { get; }
andpublic Node<T> NextNode { get; set; }
. - Personally I would handle the
head == myCurrentNode
edge-case inRemoveCurrentNode
without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation). - A
LinkedList(IEnumerable<T> collection)
constructor would be useful.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
user297876 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211760%2fsimple-linkedlist%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Collection != enumerator
The main problem I see here is that LinkedList<T>
implements IEnumerator<T>
instead of IEnumerable<T>
. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext()
and Current
, instead of being able to use foreach
. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.
IEnumerable<T>
represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield
).
IEnumerator<T>
represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach
statement (which calls GetEnumerator
on the given enumerable to obtain an enumerator).
The above means that myCurrentNode
does not belong in this class - it should be part of an enumerator. The same goes for Current
, MoveNext
, Reset
and Dispose
.
Regarding RemoveCurrentNode
, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode
also has to perform a linear search to find the preceding node.
Take a look at System.Collections.Generic.LinkedList<T>
to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.
Other notes
IEnumerator.Reset
is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset
.- Note that
IEnumerable<T>.GetEnumerator
is quite easy to implement withyield
. - There's no need to initialize
head
andtail
tonull
- that's their default value already. - There's also no need for disposal here - there are no unmanaged resources here that require disposal.
- Why does
Node
use Java-style get and set methods instead of properties? I'd expect to seepublic T Value { get; }
andpublic Node<T> NextNode { get; set; }
. - Personally I would handle the
head == myCurrentNode
edge-case inRemoveCurrentNode
without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation). - A
LinkedList(IEnumerable<T> collection)
constructor would be useful.
$endgroup$
add a comment |
$begingroup$
Collection != enumerator
The main problem I see here is that LinkedList<T>
implements IEnumerator<T>
instead of IEnumerable<T>
. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext()
and Current
, instead of being able to use foreach
. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.
IEnumerable<T>
represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield
).
IEnumerator<T>
represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach
statement (which calls GetEnumerator
on the given enumerable to obtain an enumerator).
The above means that myCurrentNode
does not belong in this class - it should be part of an enumerator. The same goes for Current
, MoveNext
, Reset
and Dispose
.
Regarding RemoveCurrentNode
, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode
also has to perform a linear search to find the preceding node.
Take a look at System.Collections.Generic.LinkedList<T>
to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.
Other notes
IEnumerator.Reset
is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset
.- Note that
IEnumerable<T>.GetEnumerator
is quite easy to implement withyield
. - There's no need to initialize
head
andtail
tonull
- that's their default value already. - There's also no need for disposal here - there are no unmanaged resources here that require disposal.
- Why does
Node
use Java-style get and set methods instead of properties? I'd expect to seepublic T Value { get; }
andpublic Node<T> NextNode { get; set; }
. - Personally I would handle the
head == myCurrentNode
edge-case inRemoveCurrentNode
without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation). - A
LinkedList(IEnumerable<T> collection)
constructor would be useful.
$endgroup$
add a comment |
$begingroup$
Collection != enumerator
The main problem I see here is that LinkedList<T>
implements IEnumerator<T>
instead of IEnumerable<T>
. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext()
and Current
, instead of being able to use foreach
. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.
IEnumerable<T>
represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield
).
IEnumerator<T>
represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach
statement (which calls GetEnumerator
on the given enumerable to obtain an enumerator).
The above means that myCurrentNode
does not belong in this class - it should be part of an enumerator. The same goes for Current
, MoveNext
, Reset
and Dispose
.
Regarding RemoveCurrentNode
, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode
also has to perform a linear search to find the preceding node.
Take a look at System.Collections.Generic.LinkedList<T>
to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.
Other notes
IEnumerator.Reset
is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset
.- Note that
IEnumerable<T>.GetEnumerator
is quite easy to implement withyield
. - There's no need to initialize
head
andtail
tonull
- that's their default value already. - There's also no need for disposal here - there are no unmanaged resources here that require disposal.
- Why does
Node
use Java-style get and set methods instead of properties? I'd expect to seepublic T Value { get; }
andpublic Node<T> NextNode { get; set; }
. - Personally I would handle the
head == myCurrentNode
edge-case inRemoveCurrentNode
without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation). - A
LinkedList(IEnumerable<T> collection)
constructor would be useful.
$endgroup$
Collection != enumerator
The main problem I see here is that LinkedList<T>
implements IEnumerator<T>
instead of IEnumerable<T>
. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext()
and Current
, instead of being able to use foreach
. This also prevents you from using Linq methods, and you can't do simultaneous enumerations.
IEnumerable<T>
represents a sequence of items that can be enumerated, such as an array, a (linked) list, or the result of a generator method (yield
).
IEnumerator<T>
represents the act of enumeration a collection. Enumerators are rarely used directly - they're usually 'hidden' behind a foreach
statement (which calls GetEnumerator
on the given enumerable to obtain an enumerator).
The above means that myCurrentNode
does not belong in this class - it should be part of an enumerator. The same goes for Current
, MoveNext
, Reset
and Dispose
.
Regarding RemoveCurrentNode
, it's both cumbersome and inefficient. Cumbersome, because you can't just pass the value (or node) that you want to remove as an argument - you have to look for it by enumerating the list. Inefficient, because once you've found the right node, RemoveCurrentNode
also has to perform a linear search to find the preceding node.
Take a look at System.Collections.Generic.LinkedList<T>
to get some inspiration. It's a doubly linked list, so not all of its methods are applicable in your case, but it should give you an idea of how to play to the strengths of a linked list.
Other notes
IEnumerator.Reset
is essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset
.- Note that
IEnumerable<T>.GetEnumerator
is quite easy to implement withyield
. - There's no need to initialize
head
andtail
tonull
- that's their default value already. - There's also no need for disposal here - there are no unmanaged resources here that require disposal.
- Why does
Node
use Java-style get and set methods instead of properties? I'd expect to seepublic T Value { get; }
andpublic Node<T> NextNode { get; set; }
. - Personally I would handle the
head == myCurrentNode
edge-case inRemoveCurrentNode
without creating an extra node. With or without doesn't make much of a difference in terms of code complexity, so I'd pick the more efficient approach (the one without an extra allocation). - A
LinkedList(IEnumerable<T> collection)
constructor would be useful.
answered 1 hour ago
Pieter WitvoetPieter Witvoet
5,906725
5,906725
add a comment |
add a comment |
user297876 is a new contributor. Be nice, and check out our Code of Conduct.
user297876 is a new contributor. Be nice, and check out our Code of Conduct.
user297876 is a new contributor. Be nice, and check out our Code of Conduct.
user297876 is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211760%2fsimple-linkedlist%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I don't program in C#, but when I look at the code, it seems that adding a value to an empty list (that is, both
head
andtail
arenull
), you create two nodes, one in theAdd
method, and one inReset
which is called fromAdd
. That strikes me as odd -- I'd expect there to be one node when adding a single value to an empty structure.$endgroup$
– Abigail
3 hours ago
$begingroup$
I added a new node in the reset to respect the corect implementation of the IEnumerator interface. Check the Remarks section over here docs.microsoft.com/en-us/dotnet/api/…
$endgroup$
– user297876
2 hours ago