Avatar of paulfioravanti

paulfioravanti's solution

to Simple Linked List in the Elixir Track

Published at Aug 20 2019 · 0 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.

Running tests

Execute the tests with:

$ mix test

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

If you're stuck on something, it may help to look at some of the available resources out there where answers might be found.

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

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

test_helper.exs

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)
defmodule LinkedList do
  @opaque t :: tuple()

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

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

  @doc """
  Calculate the length of a LinkedList
  """
  @spec length(t) :: non_neg_integer()
  def length(list), do: length(list, 0)
  defp length({}, acc), do: acc
  defp length({_head, tail}, acc), do: length(tail, acc + 1)

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

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

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

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

  @doc """
  Construct a LinkedList from a stdlib List
  """
  @spec from_list(list()) :: t
  def from_list(list) do
    list
    |> from_list({})
    |> reverse()
  end

  defp from_list([], acc), do: acc
  defp from_list([head | tail], acc), do: from_list(tail, push(acc, head))

  @doc """
  Construct a stdlib List LinkedList from a LinkedList
  """
  @spec to_list(t) :: list()
  def to_list(list) do
    list
    |> reverse()
    |> to_list([])
  end

  defp to_list({}, acc), do: acc
  defp to_list({head, tail}, acc), do: to_list(tail, [head | acc])

  @doc """
  Reverse a LinkedList
  """
  @spec reverse(t) :: t
  def reverse(list), do: reverse(list, {})
  defp reverse({}, acc), do: acc
  defp reverse({head, tail}, acc), do: reverse(tail, push(acc, head))
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?