aboutsummaryrefslogtreecommitdiff
path: root/simple-linked-list/README.md
diff options
context:
space:
mode:
authorFederico Igne <git@federicoigne.com>2020-12-26 17:48:38 +0000
committerFederico Igne <git@federicoigne.com>2021-11-03 18:55:08 +0000
commit02481656966b0a8dfc95cf3c22bcc049660ff7d4 (patch)
tree8e39798fcaf27931d91c2088423fd4e97adcfc2d /simple-linked-list/README.md
parent4e2052c4d792540c2f742b2c2a081b11117ed41d (diff)
downloadexercism-02481656966b0a8dfc95cf3c22bcc049660ff7d4.tar.gz
exercism-02481656966b0a8dfc95cf3c22bcc049660ff7d4.zip
Move Rust exercises in a subdirectory
Diffstat (limited to 'simple-linked-list/README.md')
-rw-r--r--simple-linked-list/README.md137
1 files changed, 0 insertions, 137 deletions
diff --git a/simple-linked-list/README.md b/simple-linked-list/README.md
deleted file mode 100644
index 47178e8..0000000
--- a/simple-linked-list/README.md
+++ /dev/null
@@ -1,137 +0,0 @@
1# Simple Linked List
2
3Write a simple linked list implementation that uses Elements and a List.
4
5The linked list is a fundamental data structure in computer science,
6often used in the implementation of other data structures. They're
7pervasive in functional programming languages, such as Clojure, Erlang,
8or Haskell, but far less common in imperative languages such as Ruby or
9Python.
10
11The simplest kind of linked list is a singly linked list. Each element in the
12list contains data and a "next" field pointing to the next element in the list
13of elements.
14
15This variant of linked lists is often used to represent sequences or
16push-down stacks (also called a LIFO stack; Last In, First Out).
17
18As a first take, lets create a singly linked list to contain the range (1..10),
19and provide functions to reverse a linked list and convert to and from arrays.
20
21When implementing this in a language with built-in linked lists,
22implement your own abstract data type.
23
24## Implementation Hints
25
26Do not implement the struct `SimpleLinkedList` as a wrapper around a `Vec`. Instead, allocate nodes on the heap.
27This might be implemented as:
28```
29pub struct SimpleLinkedList<T> {
30 head: Option<Box<Node<T>>>,
31}
32```
33The `head` field points to the first element (Node) of this linked list.
34This implementation also requires a struct `Node` with the following fields:
35```
36struct Node<T> {
37 data: T,
38 next: Option<Box<Node<T>>>,
39}
40```
41`data` contains the stored data, and `next` points to the following node (if available) or None.
42
43### Why `Option<Box<Node<T>>>` and not just `Option<Node<T>>`?
44Try it on your own. You will get the following error.
45
46```
47| struct Node<T>
48| ^^^^^^^^^^^^^^ recursive type has infinite size
49...
50| next: Option<Node<T>>,
51| --------------------- recursive without indirection
52 ```
53
54 The problem is that at compile time the size of next must be known.
55 Since `next` is recursive ("a node has a node has a node..."), the compiler does not know how much memory is to be allocated.
56 In contrast, [Box](https://doc.rust-lang.org/std/boxed/) is a heap pointer with a defined size.
57
58
59## Rust Installation
60
61Refer to the [exercism help page][help-page] for Rust installation and learning
62resources.
63
64## Writing the Code
65
66Execute the tests with:
67
68```bash
69$ cargo test
70```
71
72All but the first test have been ignored. After you get the first test to
73pass, open the tests source file which is located in the `tests` directory
74and remove the `#[ignore]` flag from the next test and get the tests to pass
75again. Each separate test is a function with `#[test]` flag above it.
76Continue, until you pass every test.
77
78If you wish to run all ignored tests without editing the tests source file, use:
79
80```bash
81$ cargo test -- --ignored
82```
83
84To run a specific test, for example `some_test`, you can use:
85
86```bash
87$ cargo test some_test
88```
89
90If the specific test is ignored use:
91
92```bash
93$ cargo test some_test -- --ignored
94```
95
96To learn more about Rust tests refer to the [online test documentation][rust-tests]
97
98Make sure to read the [Modules][modules] chapter if you
99haven't already, it will help you with organizing your files.
100
101## Further improvements
102
103After you have solved the exercise, please consider using the additional utilities, described in the [installation guide](https://exercism.io/tracks/rust/installation), to further refine your final solution.
104
105To format your solution, inside the solution directory use
106
107```bash
108cargo fmt
109```
110
111To see, if your solution contains some common ineffective use cases, inside the solution directory use
112
113```bash
114cargo clippy --all-targets
115```
116
117## Submitting the solution
118
119Generally you should submit all files in which you implemented your solution (`src/lib.rs` in most cases). If you are using any external crates, please consider submitting the `Cargo.toml` file. This will make the review process faster and clearer.
120
121## Feedback, Issues, Pull Requests
122
123The [exercism/rust](https://github.com/exercism/rust) repository on GitHub is the home for all of the Rust exercises. If you have feedback about an exercise, or want to help implement new exercises, head over there and create an issue. Members of the rust track team are happy to help!
124
125If you want to know more about Exercism, take a look at the [contribution guide](https://github.com/exercism/docs/blob/master/contributing-to-language-tracks/README.md).
126
127[help-page]: https://exercism.io/tracks/rust/learning
128[modules]: https://doc.rust-lang.org/book/ch07-02-defining-modules-to-control-scope-and-privacy.html
129[cargo]: https://doc.rust-lang.org/book/ch14-00-more-about-cargo.html
130[rust-tests]: https://doc.rust-lang.org/book/ch11-02-running-tests.html
131
132## Source
133
134Inspired by 'Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby', singly linked-lists. [https://web.archive.org/web/20160731005714/http://brpreiss.com/books/opus8/html/page96.html](https://web.archive.org/web/20160731005714/http://brpreiss.com/books/opus8/html/page96.html)
135
136## Submitting Incomplete Solutions
137It's possible to submit an incomplete solution so you can see how others have completed the exercise.