Mixing
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
edited Jan 18 at 13:50
Rick Davin
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
$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
edited Jan 18 at 13:50
Rick Davin
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
$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, bothheadandtailarenull), you create two nodes, one in theAddmethod, and one inResetwhich 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
Jan 18 at 13:42
$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
Jan 18 at 14:23
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
edited Jan 18 at 13:50
Rick Davin
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
$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
edited Jan 18 at 13:50
Rick Davin
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
edited Jan 18 at 13:50
Rick Davin
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
edited Jan 18 at 13:50
Rick Davin
3,177718
edited Jan 18 at 13:50
Rick Davin
3,177718
edited Jan 18 at 13:50
Rick Davin
3,177718
3,177718
asked Jan 18 at 11:09
user297876user297876
1462
asked Jan 18 at 11:09
user297876user297876
1462
asked Jan 18 at 11:09
user297876user297876
1462
1462
$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, bothheadandtailarenull), you create two nodes, one in theAddmethod, and one inResetwhich 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
Jan 18 at 13:42
$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
Jan 18 at 14:23
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, bothheadandtailarenull), you create two nodes, one in theAddmethod, and one inResetwhich 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
Jan 18 at 13:42
$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
Jan 18 at 14:23
$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
Jan 18 at 13:42
$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
Jan 18 at 13:42
$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
Jan 18 at 14:23
$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
Jan 18 at 14:23
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.Resetis essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset.- Note that
IEnumerable<T>.GetEnumeratoris quite easy to implement withyield. - There's no need to initialize
headandtailtonull- 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
Nodeuse 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 == myCurrentNodeedge-case inRemoveCurrentNodewithout 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 Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
$endgroup$
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
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.Resetis essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset.- Note that
IEnumerable<T>.GetEnumeratoris quite easy to implement withyield. - There's no need to initialize
headandtailtonull- 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
Nodeuse 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 == myCurrentNodeedge-case inRemoveCurrentNodewithout 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 Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
$endgroup$
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
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.Resetis essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset.- Note that
IEnumerable<T>.GetEnumeratoris quite easy to implement withyield. - There's no need to initialize
headandtailtonull- 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
Nodeuse 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 == myCurrentNodeedge-case inRemoveCurrentNodewithout 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 Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
$endgroup$
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
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.Resetis essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset.- Note that
IEnumerable<T>.GetEnumeratoris quite easy to implement withyield. - There's no need to initialize
headandtailtonull- 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
Nodeuse 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 == myCurrentNodeedge-case inRemoveCurrentNodewithout 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 Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
$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.Resetis essentially deprecated. Enumerating a collection again is done by obtaining a new enumerator. Modern enumerators typically throw an exception inReset.- Note that
IEnumerable<T>.GetEnumeratoris quite easy to implement withyield. - There's no need to initialize
headandtailtonull- 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
Nodeuse 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 == myCurrentNodeedge-case inRemoveCurrentNodewithout 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 Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
answered Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
answered Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
answered Jan 18 at 15:52
Pieter WitvoetPieter Witvoet
6,284826
6,284826
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
add a comment |
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
$begingroup$
Thank you @Pieter, now I understand the reason behind IEnumerator. I would improve this implementation with a IEnumerable instead.
$endgroup$
– user297876
Jan 20 at 16:38
add a comment |
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');
});
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');
});
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');
});
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');
});
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
headandtailarenull), you create two nodes, one in theAddmethod, and one inResetwhich 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
Jan 18 at 13:42
$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
Jan 18 at 14:23