5
\$\begingroup\$

As part of the practice, I created minimalist linked list named SimpleList which can be iterated in two different ways: one element after another or by every second element.

Because I'm beginner I would really appreciate your opinion about my solution. Is it correct? What should I change?

public class SimpleList<T> : IEnumerable<T>
{
    protected class Node
    {
        public T Data { get; set; }
        public Node NextNode { get; set; }

        public Node(T data, Node nextNode)
        {
            Data = data;
            NextNode = nextNode;
        }
    }

    protected Node Head { get; set; } = null;

    public void Add(T data)
    {
        Head = new Node(data, Head);
    }

    #region IEnumerable<T> implementation
    public IEnumerator<T> GetEnumerator()
    {
        var current = Head;
        while (current != null)
        {
            yield return current.Data;
            current = current.NextNode;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    #endregion

    #region second iterator implementation
    private class EverySecondElementIterator : IEnumerable<T>
    {
        private readonly Node head;

        public EverySecondElementIterator(Node head)
        {
            this.head = head;
        }

        public IEnumerator<T> GetEnumerator()
        {
            var current = head;
            while (current != null)
            {
                yield return current.Data;
                current = current.NextNode?.NextNode;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    public IEnumerable<T> EverySecondElement => new EverySecondElementIterator(Head);
    #endregion
}
\$\endgroup\$
7
\$\begingroup\$

Use extension methods

I find you did well by implementing the EverySecondElementIterator as a separate class. However, I also think it would be better to turn it into an extension of IEnumerable<T> and use MoveNext instead of the internal Node.

Otherwise if someone suddenly comes up with the idea to skip every third element, you would need to modify the original SimpleList by creating another private class class and another property. We usually try to avoid modifying code that is tested and is working well. This would also violate the open/closed principle.

It's much safer and extendable to create a new and independent extension that you also can resue with any IEnumerable<T> and skip every-second-element of any collection.

Let the SimpleList be closed for modifications by not implementing anything as specific as that enumerator. It is already opend for extension by implementing the IEnumerable<T> interface. Make use of it.

\$\endgroup\$
  • \$\begingroup\$ You mean something like this: SimpleList.cs, IEnumerableExtensions.cs, Program.cs? My concerns: 1. extension class name starts with capital I but it's not an interface (what's proper naming convention?). 2. Static class can't be generic so my enumerator returns plain objects. Is it ok? \$\endgroup\$ – wozar May 28 at 12:30
  • \$\begingroup\$ @techb0t Or should I cast it to desirable type? \$\endgroup\$ – wozar May 28 at 12:37
  • \$\begingroup\$ @wozar since you know the T, it'd easier be easier when you implemented the generic interface IEnumerable<T> \$\endgroup\$ – t3chb0t May 28 at 12:48
  • \$\begingroup\$ I'm sorry but where should I implement it? \$\endgroup\$ – wozar May 28 at 12:56
  • \$\begingroup\$ I mean if I implement generic IEnumerable in my private EverySecondElementIterator class I still can't return it without casting to non-generic since static class doesn't know about T \$\endgroup\$ – wozar May 28 at 13:01
5
\$\begingroup\$

Terminology

The Add operation on a List appends the item to that list. Your method should be renamed to Prepend.

 public void Add(T data)
 {
      Head = new Node(data, Head);
 }
 public void Prepend(T data)
 {
      Head = new Node(data, Head);
 }

Design

You could keep track of the Tail and have an Add operation.

protected Node Head { get; set; } = null;

 protected Node Head { get; set; } = null;
 protected Node Tail { get { 
     var tail = Head;
     while (tail != null && tail.NextNode != null)
         tail = tail.NextNode;
     return tail;
 }}

 public void Add(T data)
 {
     if (Head == null)
         Head = new Node(data, null);
     else
         Tail.NextNode = new Node(data, null);
 }
\$\endgroup\$
  • \$\begingroup\$ Nothing more? I'm worried about this you can alternate list while iterating over it. What if we have two iterators? Should I prevent this e.g. using readonly copies od list? How can I even make such copy? It doesn't use any built in collection so it won't be trivial... \$\endgroup\$ – wozar May 27 at 16:43
  • \$\begingroup\$ @wozar It's up to caller code to know how to iterate over IEnumerable instances and how to allow/restrict concurrent access. \$\endgroup\$ – dfhwze May 27 at 16:46
  • \$\begingroup\$ Thank you for naming suggestion. I also noticed that you don't keep tail as simple reference to last added element and I have concerns about performance. Is it necessary if we can manipulate list only with this class' public methods? If I'm correct we can't modify node's NextNode property from outside SimpleList class so it should be impossible to break this list by adding next node before tail and creating some sort of branching. \$\endgroup\$ – wozar May 28 at 12:52
  • \$\begingroup\$ @wozar It's a design decision whether you want to keep track of other properties other than head that could also get calculated on demand. If performance is key, I would store the tail as well. If memory storage should be kept low, I would not. \$\endgroup\$ – dfhwze May 28 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.