current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 0 down vote favorite

I've just been going through core data structures and algorithms recently, wanting to get back in touch with the core fundamentals. I'm starting simple with a LinkedList implementation in C#. The functionality works and was able to test it. I'm just wondering if yo see anything with the code that could be improved.

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

namespace DataStructuresAndAlgorithms.DataStructures.LinkedList
{
    public class SinglyLinkedList<T> : IEnumerable<T>
    {
        public SinglyLinkedListNode<T> Head { get; set; }
        public SinglyLinkedListNode<T> Tail { get; set; }

        public void AddToEnd(T value)
        {
            var newNode = new SinglyLinkedListNode<T>
            {
                Value = value,
                Next = null
            };
            if (Head == null && Tail == null)
            {
                Head = newNode;
                Tail = newNode;
            }
            if (Head == Tail)
            {
                Head.Next = newNode;
                Tail = newNode;
            }
            else
            {
                var existingLast = Tail;
                existingLast.Next = newNode;
                Tail = newNode;
            }
        }

        public void AddToBeginning(T value)
        {
            var newNode = new SinglyLinkedListNode<T>
            {
                Value = value,
                Next = null
            };
            if (Head == null && Tail == null)
            {
                Head = newNode;
                Tail = newNode;
            }
            else
            {
                var existingHead = Head;
                Head = newNode;
                Head.Next = existingHead;
            }
        }

        public bool Exists(T value)
        {
            var head = Head;
            while(head != null)
            {
                if (head.Value.Equals(value))
                {
                    return true;
                }
                head = head.Next;
            }
            return false;
        }

        public void Delete(T value)
        {
            var head = Head;
            SinglyLinkedListNode<T> previous = null;
            while(head != null)
            {
                if (head.Value.Equals(value))
                {
                    if (previous == null)
                    {
                        Head = Head.Next;
                    }
                    else
                    {
                        previous.Next = head.Next;
                    }
                }
                previous = head;
                head = head.Next;
            }
        }

        public void Clear()
        {
            Head = null;
            Tail = null;
        }

        public IEnumerator<T> GetEnumerator()
        {
            var head = Head;
            while(head != null)
            {
                yield return head.Value;
                head = head.Next;
            }
        }

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

    public class SinglyLinkedListNode<T>
    {
        public T Value { get; set; }
        public SinglyLinkedListNode<T> Next { get; set; }
    }
}
share|improve this question
up vote 0 down vote accepted
  • I would implement ICollection<T> in addition to IEnumerable<T>. It should be easy and straightforward.
  • Public setters of the Head and Tail properties will allow users of your class to corrupt the structure of linked list.
  • Not sure if you need to expose Head and Tail as properties at all, as they are the only ones who expose the SinglyLinkedListNode<T> instances used internally.

  • AddToEnd implementation can be simplified. The case of Head == Tail doesn't differ from else clause. So the method can be refactored as following (note that the non-null Head implies non-null Tail, this should be guaranteed by the design of your class):

    public void AddToEnd(T value)
{
    var newNode = new SinglyLinkedListNode<T>
    {
        Value = value,
        Next = null
    };

    if (Head == null)
    {
        Head = newNode;
    }
    else
    {
        Tail.Next = newNode;
    }

    Tail = newNode;
}

  • Similar refactorings can be applied to AddToBeginning. When you create a new node to be inserted at the beginning, its Next property will always refer to original Head node, whether it was null (list is empty) or actual node. Thus the method can be reduced to:

    public void AddToBeginning(T value)
{
    Head = new SinglyLinkedListNode<T>
    {
        Value = value,
        Next = Head
    };

    if (Tail == null)
    {
        Tail = Head;
    }
}
  • Delete method has a bug - it will never assign null to Tail, even if all elements are deleted from the list.
share|improve this answer
    
Thank you! All good points. I started to catch the redundancy of some of the conditions in the Add methods once I looked through it a couple of times. Awesome catch on the Delete bug, I will correct that. – Scott yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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