0
\$\begingroup\$

I wrote an implementation of the Linked list data structure. I mostly did this because it's the simplest collection data structure (at least the simplest to implement), and I wanted to practice implementing IEnumerable<T> and IEnumerator<T>. I also wanted to play around with generics.

This was entirely a practice exercise to come to better grips with the language (it's also why I avoided using the yield return syntax for my enumerator; I wanted to implement an enumerator the "hard" way without any of the syntactic sugar).

As a learning exercise, it was fruitful.

That said, my project has three namespaces:

  • SimpleTypes (Node<TData> is defined here)
  • CollectionTypes.Enumerators (LinkedListEnumerator is defined here)
  • CollectionTypes (LinkedList<TData> is defined here)

 

Node.cs

namespace SimpleTypes
{
    public class Node<TData>
    {
        public TData Data { get; set; }
        public Node<TData> Next { get; set; }

        public Node(TData data)
        {
            Data = data;
        }

        public override string ToString()
        {
            return Data.ToString();
        }
    }
}

LinkedListEnumerator.cs

using System.Collections.Generic;
using System.Collections;

using SimpleTypes;

namespace CollectionTypes.Enumerators
{
    internal class LinkedListEnumerator<TData>: IEnumerator<TData>
    {
        private Node<TData> _current;
        private readonly Node<TData> _start;
        private bool _isDisposed;

        public TData Current { get => _current.Data; set { _current.Data = value; } }
        
        // Implementing `IEnumerator<T>` requires an implementation of `IEnumerator`
        object IEnumerator.Current { get => this.Current; }    // Explicit interface specifications don't have any access specifiers

        public LinkedListEnumerator(Node<TData> head)
        {
            _current = _start = new Node<TData>(default(TData));
            _start.Next = _current.Next = head;
            _isDisposed = false;
        }

        public bool MoveNext()
        {
            bool keepGoing = true;

            if (_current.Next is null)
                keepGoing = false;

            _current = _current.Next;
            
            return keepGoing;
        }

        public void Reset()
        {
            _current = _start;
        }

        public void Dispose()
        {
            // Dispose of unmanaged resources
            Dispose(true);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (_isDisposed)
                return;
            
            if (disposing)
            {
                // Dispose of managed resources
            }

            _current = null;
            _isDisposed = true;
        }

        ~LinkedListEnumerator()
        {
            Dispose(false);
        }
    }
}

LinkedList.cs

using System.Collections;
using System.Collections.Generic;

using SimpleTypes;
using CollectionTypes.Enumerators;

namespace CollectionTypes
{
    public class LinkedList<TData>: IEnumerable<TData>
    {
        public Node<TData> Head { get; set; }
        public Node<TData> Tail { get; set; }

        public LinkedList()
        {
            Head = Tail = null;
        }

        #region List API
        public void AddHead(TData data)
        {
            Node<TData> newHead = new Node<TData>(data);

            if (Head is null)
                Tail = newHead;
            else
                newHead.Next = Head;
            
            Head = newHead;
        }

        public void AddTail(TData data)
        {
            Node<TData> newTail = new Node<TData>(data);

            if (Tail is null)
                Head = newTail;
            else
                Tail.Next = newTail;

            Tail = newTail;
        }
        #endregion
        
        #region Interface Implementations
        public IEnumerator<TData> GetEnumerator()
        {
            return new LinkedListEnumerator<TData>(Head);
        }

        // Implementing `IEnumerable<T>` requires an implementation of `IEnumerable`
        IEnumerator IEnumerable.GetEnumerator()    // Explicit interface specifications don't have any access specifiers
        {
            return this.GetEnumerator();
        }
        #endregion

        public override string ToString()
        {
            string result = "";

            foreach (TData item in this)
            {
                result += item.ToString() + ", ";
            }

            return result.TrimEnd(new char[]{' ', ','});
        }
    }
}

 

For feedback, I'm most interested in:

  • Style, idioms and best practices
  • My implementation of the data type and how closely it matches the linked list API
  • Performance concerns
\$\endgroup\$
2
  • 1
    \$\begingroup\$ The ToString method is very inefficient. Use either string.Join or StringBuilder instead of string concatenation. \$\endgroup\$ Sep 17, 2021 at 18:09
  • \$\begingroup\$ @AlexanderPetrov; thanks and noted. I'll fix that. I didn't know that string.Join() worked for any IEnumerable. \$\endgroup\$ Sep 18, 2021 at 14:29

1 Answer 1

3
\$\begingroup\$
  • The IEnumerator<T>.Current property must have only a getter. I.e., you are not allowed to change the Current value from outside. Only MoveNext() and Reset() are allowed.
    public TData Current => _current.Data;
    
  • The IEnumerator.Current property can slightly be simplified. Add the expression body to the property instead of the getter (this defines the getter implicitly). Also, since this property does not involve logic besides returning a value, I would directly return _current.Data instead of this.Current.
    object IEnumerator.Current => _current.Data;
    
  • Since Node<T> is publicly exposed, I would put it in the same namespace as LinkedList<T>, otherwise the user is forced to import two namespaces.
  • You have implemented the full blown dispose pattern in the enumerator. There is nothing to be disposed here, since the enumerator is not keeping unmanaged resources. You can simply write
    void IDisposable.Dispose() { }
    
  • You are using a finalizer. Finalizers are costly and since we do need to dispose anything, drop it!
  • You are exposing the setter of Head and Tail. This allows the user to do manipulations leading to inconsistent data, e.g., to have a head and a tail not linked together. Make the setter private or protected.
    public Node<TData> Head { get; private set; }
    public Node<TData> Tail { get; private set; }
    
\$\endgroup\$
1
  • \$\begingroup\$ Thanks very much for all the suggestions. They've been implemented! \$\endgroup\$ Sep 18, 2021 at 18:59

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.