53 lines
2.0 KiB
Markdown
53 lines
2.0 KiB
Markdown
|
# Simple Linked List
|
||
|
|
|
||
|
|
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.
|
||
|
|
|
||
|
|
* * * *
|
||
|
|
|
||
|
|
For installation and learning resources, refer to the
|
||
|
|
[Ruby resources page](http://exercism.io/languages/ruby/resources).
|
||
|
|
|
||
|
|
For running the tests provided, you will need the Minitest gem. Open a
|
||
|
|
terminal window and run the following command to install minitest:
|
||
|
|
|
||
|
|
gem install minitest
|
||
|
|
|
||
|
|
If you would like color output, you can `require 'minitest/pride'` in
|
||
|
|
the test file, or note the alternative instruction, below, for running
|
||
|
|
the test file.
|
||
|
|
|
||
|
|
Run the tests from the exercise directory using the following command:
|
||
|
|
|
||
|
|
ruby simple_linked_list_test.rb
|
||
|
|
|
||
|
|
To include color from the command line:
|
||
|
|
|
||
|
|
ruby -r minitest/pride simple_linked_list_test.rb
|
||
|
|
|
||
|
|
|
||
|
|
## 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](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.
|