@@ -25,6 +25,19 @@ import java.io._
25
25
* This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access
26
26
* pattern, for example, random access or FIFO, consider using a collection more suited to this than `List`.
27
27
*
28
+ * ==Performance==
29
+ * '''Time:''' `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
30
+ * This includes the index-based lookup of elements, `length`, `append` and `reverse`.
31
+ *
32
+ * '''Space:''' `List` implements '''structural sharing''' of the tail list. This means that many operations are either
33
+ * zero- or constant-memory cost.
34
+ * {{{
35
+ * val mainList = List(3, 2, 1)
36
+ * val with4 = 4 :: mainList // re-uses mainList, costs one :: instance
37
+ * val with42 = 42 :: mainList // also re-uses mainList, cost one :: instance
38
+ * val shorter = mainList.tail // costs nothing as it uses the same 2::1::Nil instances as mainList
39
+ * }}}
40
+ *
28
41
* @example {{{
29
42
* // Make a list via the companion object factory
30
43
* val days = List("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
@@ -41,19 +54,6 @@ import java.io._
41
54
* }
42
55
* }}}
43
56
*
44
- * ==Performance==
45
- * '''Time:''' `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
46
- * This includes the index-based lookup of elements, `length`, `append` and `reverse`.
47
- *
48
- * '''Space:''' `List` implements '''structural sharing''' of the tail list. This means that many operations are either
49
- * zero- or constant-memory cost.
50
- * {{{
51
- * val mainList = List(3, 2, 1)
52
- * val with4 = 4 :: mainList // re-uses mainList, costs one :: instance
53
- * val with42 = 42 :: mainList // also re-uses mainList, cost one :: instance
54
- * val shorter = mainList.tail // costs nothing as it uses the same 2::1::Nil instances as mainList
55
- * }}}
56
- *
57
57
* @note The functional list is characterized by persistence and structural sharing, thus offering considerable
58
58
* performance and space consumption benefits in some scenarios if used correctly.
59
59
* However, note that objects having multiple references into the same functional list (that is,
0 commit comments