Avatar of artemkorsakov

artemkorsakov's solution

to Simple Linked List in the C# Track

Published at May 03 2019 · 2 comments
Instructions
Test suite
Solution

Write a simple linked list implementation that uses Elements and a List.

The linked list is a fundamental data structure in computer science, often used in the implementation of other data structures. They're pervasive in functional programming languages, such as Clojure, Erlang, or Haskell, but far less common in imperative languages such as Ruby or Python.

The simplest kind of linked list is a singly linked list. Each element in the list contains data and a "next" field pointing to the next element in the list of elements.

This variant of linked lists is often used to represent sequences or push-down stacks (also called a LIFO stack; Last In, First Out).

As a first take, lets create a singly linked list to contain the range (1..10), and provide functions to reverse a linked list and convert to and from arrays.

When implementing this in a language with built-in linked lists, implement your own abstract data type.

Hints

This exercise requires you to create a linked list data structure which can be iterated. This requires you to implement the IEnumerable<T> interface. For more information, see this page.

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit SimpleLinkedList.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

Source

Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. http://www.brpreiss.com/books/opus8/html/page96.html#SECTION004300000000000000000

SimpleLinkedListTest.cs

using System.Linq;
using Xunit;

public class SimpleLinkedListTest
{
    [Fact]
    public void Single_item_list_value()
    {
        var list = new SimpleLinkedList<int>(1);
        Assert.Equal(1, list.Value);
    }

    [Fact(Skip = "Remove to run test")]
    public void Single_item_list_has_no_next_item()
    {
        var list = new SimpleLinkedList<int>(1);
        Assert.Null(list.Next);
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_item_list_first_value()
    {
        var list = new SimpleLinkedList<int>(2).Add(1);
        Assert.Equal(2, list.Value);
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_item_list_second_value()
    {
        var list = new SimpleLinkedList<int>(2).Add(1);
        Assert.Equal(1, list.Next.Value);
    }

    [Fact(Skip = "Remove to run test")]
    public void Two_item_list_second_item_has_no_next()
    {
        var list = new SimpleLinkedList<int>(2).Add(1);
        Assert.Null(list.Next.Next);
    }

    [Fact(Skip = "Remove to run test")]
    public void Implements_enumerable()
    {
        var values = new SimpleLinkedList<int>(2).Add(1);
        Assert.Equal(new[] { 2, 1 }, values);
    }

    [Fact(Skip = "Remove to run test")]
    public void From_enumerable()
    {
        var list = new SimpleLinkedList<int>(new[] { 11, 7, 5, 3, 2 });
        Assert.Equal(11, list.Value);
        Assert.Equal(7, list.Next.Value);
        Assert.Equal(5, list.Next.Next.Value);
        Assert.Equal(3, list.Next.Next.Next.Value);
        Assert.Equal(2, list.Next.Next.Next.Next.Value);
    }

    [Theory(Skip = "Remove to run test")]
    [InlineData(1)]
    [InlineData(2)]
    [InlineData(10)]
    [InlineData(100)]
    public void Reverse(int length)
    {
        var values = Enumerable.Range(1, length).ToArray();
        var list = new SimpleLinkedList<int>(values);
        var reversed = list.Reverse();
        Assert.Equal(values.Reverse(), reversed);
    }

    [Theory(Skip = "Remove to run test")]
    [InlineData(1)]
    [InlineData(2)]
    [InlineData(10)]
    [InlineData(100)]
    public void Roundtrip(int length)
    {
        var values = Enumerable.Range(1, length);
        var listValues = new SimpleLinkedList<int>(values);
        Assert.Equal(values, listValues);
    }
}
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class SimpleLinkedList<T> : IEnumerable<T>
{
    private readonly T[] list;
    private readonly int currentIndex;

    public SimpleLinkedList(T value)
    {
        list = new T[1];
        currentIndex = 0;
        list[currentIndex] = value;
    }

    public SimpleLinkedList(IEnumerable<T> values)
    {
        list = new T[values.Count()];
        currentIndex = 0;
        foreach (var value in values)
        {
            list[currentIndex++] = value;
        }
        currentIndex = 0;
    }

    public T Value => currentIndex < list.Length ? list[currentIndex] : default(T);

    public SimpleLinkedList<T> Next
    {
        get
        {
            if (currentIndex + 1 >= list.Length)
            {
                return default(SimpleLinkedList<T>);
            }

            var newList = new T[list.Length - currentIndex - 1];
            for (int i = 0; i < newList.Length; i++)
            {
                newList[i] = list[currentIndex + 1 + i];
            }

            return new SimpleLinkedList<T>(newList);
        }
    }

    public SimpleLinkedList<T> Add(T value)
    {
        var newList = new T[list.Length + 1];
        list.CopyTo(newList, 0);
        newList[list.Length] = value;
        return new SimpleLinkedList<T>(newList);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return ((IEnumerable<T>)list).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return ((IEnumerable<T>)list).GetEnumerator();
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of Cassandrad

Do you know that using a list from standard lib to implement the list data structure is cheating? So you obviously can replace the whole your code solution with simple System.Collections.List.

Avatar of artemkorsakov

You're right! Sorry me for this solution. I am very lazy and this is just my fault. I corrected the solution.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?