Avatar of davearonson

davearonson's solution

to Simple Linked List in the Elixir Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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.

Running tests

Execute the tests with:

$ elixir simple_linked_list_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help 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

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

linked_list_test.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("linked_list.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule LinkedListTest do
  use ExUnit.Case

  test "length/1 of new list" do
    list = LinkedList.new()
    assert LinkedList.length(list) == 0
  end

  @tag :pending
  test "empty?/1 of new list" do
    list = LinkedList.new()
    assert LinkedList.empty?(list)
  end

  @tag :pending
  test "length/1 of list of 1 datum" do
    list = LinkedList.new() |> LinkedList.push(10)
    assert LinkedList.length(list) == 1
  end

  @tag :pending
  test "empty?/1 of list of 1 datum" do
    list = LinkedList.new() |> LinkedList.push(20)
    refute LinkedList.empty?(list)
  end

  @tag :pending
  test "peek/1 of list of 1 datum" do
    list = LinkedList.new() |> LinkedList.push(20)
    assert LinkedList.peek(list) == {:ok, 20}
  end

  @tag :pending
  test "peek/1 of list of empty list" do
    list = LinkedList.new()
    assert LinkedList.peek(list) == {:error, :empty_list}
  end

  @tag :pending
  test "tail/1 of empty list" do
    list = LinkedList.new()
    assert {:error, :empty_list} = LinkedList.tail(list)
  end

  @tag :pending
  test "tail/1 of list of 1 datum" do
    list = LinkedList.new() |> LinkedList.push(:hello)
    assert {:ok, tail} = LinkedList.tail(list)
    assert LinkedList.peek(tail) == {:error, :empty_list}
  end

  @tag :pending
  test "pushed items are stacked" do
    list =
      LinkedList.new()
      |> LinkedList.push(:a)
      |> LinkedList.push(:b)

    assert LinkedList.peek(list) == {:ok, :b}
    assert {:ok, list} = LinkedList.tail(list)
    assert LinkedList.peek(list) == {:ok, :a}
    assert {:ok, list} = LinkedList.tail(list)
    assert LinkedList.peek(list) == {:error, :empty_list}
  end

  @tag :pending
  test "push 10 times" do
    list = Enum.reduce(1..10, LinkedList.new(), &LinkedList.push(&2, &1))
    assert LinkedList.peek(list) == {:ok, 10}
    assert LinkedList.length(list) == 10
  end

  @tag :pending
  test "pop/1 of list of 1 datum" do
    list = LinkedList.new() |> LinkedList.push(:a)
    assert {:ok, :a, tail} = LinkedList.pop(list)
    assert LinkedList.length(tail) == 0
  end

  @tag :pending
  test "popping frenzy" do
    list = Enum.reduce(11..20, LinkedList.new(), &LinkedList.push(&2, &1))
    assert LinkedList.length(list) == 10
    assert {:ok, 20, list} = LinkedList.pop(list)
    assert {:ok, 19, list} = LinkedList.pop(list)
    assert {:ok, 18, list} = LinkedList.pop(list)
    assert {:ok, 17, list} = LinkedList.pop(list)
    assert {:ok, 16, list} = LinkedList.pop(list)
    assert {:ok, 15} = LinkedList.peek(list)
    assert LinkedList.length(list) == 5
  end

  @tag :pending
  test "from_list/1 of empty list" do
    list = LinkedList.from_list([])
    assert LinkedList.length(list) == 0
  end

  @tag :pending
  test "from_list/1 of 2 element list" do
    list = LinkedList.from_list([:a, :b])
    assert LinkedList.length(list) == 2
    assert {:ok, :a, list} = LinkedList.pop(list)
    assert {:ok, :b, list} = LinkedList.pop(list)
    assert {:error, :empty_list} = LinkedList.pop(list)
  end

  @tag :pending
  test "to_list/1 of empty list" do
    list = LinkedList.new()
    assert LinkedList.to_list(list) == []
  end

  @tag :pending
  test "to_list/1 of list of 1 datum" do
    list = LinkedList.from_list([:mon])
    assert LinkedList.to_list(list) == [:mon]
  end

  @tag :pending
  test "to_list/1 of list of 2 datum" do
    list = LinkedList.from_list([:mon, :tues])
    assert LinkedList.to_list(list) == [:mon, :tues]
  end

  @tag :pending
  test "reverse/1 of list of 2 datum" do
    list = LinkedList.from_list([1, 2, 3]) |> LinkedList.reverse()
    assert LinkedList.to_list(list) == [3, 2, 1]
  end

  @tag :pending
  test "reverse/1 of list of 200 datum" do
    list = Enum.to_list(1..200)
    linked_list = LinkedList.from_list(list) |> LinkedList.reverse()
    assert LinkedList.to_list(linked_list) == Enum.reverse(list)
  end

  @tag :pending
  test "reverse/1 round trip" do
    list = Enum.to_list(1..200)

    linked_list =
      LinkedList.from_list(list)
      |> LinkedList.reverse()
      |> LinkedList.reverse()

    assert LinkedList.to_list(linked_list) == list
  end
end
defmodule LinkedList do
  @opaque t :: tuple()

  defstruct datum: nil, next: nil

  @doc """
  Construct a new LinkedList
  """
  @spec new() :: t
  def new(), do: nil

  @doc """
  Push an item onto a LinkedList
  """
  @spec push(t, any()) :: t
  def push(list, elem), do: %LinkedList{datum: elem, next: list}

  @doc """
  Calculate the length of a LinkedList
  """
  @spec length(t) :: non_neg_integer()
  def length(%LinkedList{next: next}), do: LinkedList.length(next) + 1
  def length(nil), do: 0

  @doc """
  Determine if a LinkedList is empty
  """
  @spec empty?(t) :: boolean()
  def empty?(%LinkedList{}), do: false
  def empty?(nil), do: true

  @doc """
  Get the value of a head of the LinkedList
  """
  @spec peek(t) :: {:ok, any()} | {:error, :empty_list}
  def peek(%LinkedList{datum: datum}), do: {:ok, datum}
  def peek(nil), do: {:error, :empty_list}

  @doc """
  Get tail of a LinkedList
  """
  @spec tail(t) :: {:ok, t} | {:error, :empty_list}
  def tail(%LinkedList{next: next}), do: {:ok, next}
  def tail(nil), do: {:error, :empty_list}

  @doc """
  Remove the head from a LinkedList
  """
  @spec pop(t) :: {:ok, any(), t} | {:error, :empty_list}
  def pop(%LinkedList{datum: datum, next: next}), do: {:ok, datum, next}
  def pop(nil), do: {:error, :empty_list}

  @doc """
  Construct a LinkedList from a stdlib List
  """
  @spec from_list(list()) :: t
  def from_list(list), do: do_from_list(Enum.reverse(list), nil)
  defp do_from_list([head|tail], acc) do
    do_from_list(tail, %LinkedList{datum: head, next: acc})
  end
  defp do_from_list([], acc), do: acc

  @doc """
  Construct a stdlib List LinkedList from a LinkedList
  """
  @spec to_list(t) :: list()
  def to_list(list), do: do_to_list(list, []) |> Enum.reverse
  defp do_to_list(%LinkedList{datum: datum, next: next}, acc) do
    do_to_list(next, [datum|acc])
  end
  defp do_to_list(nil, acc), do: acc

  @doc """
  Reverse a LinkedList
  """
  @spec reverse(t) :: t
  def reverse(list), do: do_reverse(list, nil)
  defp do_reverse(%LinkedList{datum: datum, next: next}, acc) do
    do_reverse(next, %LinkedList{datum: datum, next: acc})
  end
  defp do_reverse(nil, acc), do: acc
end

Community comments

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

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?