D 2017-12-01T15:42:56.659
L Singly-Linked\sList
P 97b2bac950a5c04b34f6d7a8550ac0b0fd51cb5a
U Entomy
W 1932
<h1>Purpose</h1>
<p>Sometimes the overhead of larger containers isn't justifiable, and so the smaller node of the Singly-Linked List is advantageous.</p>
<p>This is also fundamentally how the [Stack] and [Queue] work, although this List has more overhead than either of those, but provides more features.</p>
<h1>Notable Features</h1>
<h2>Non-Deallocative Traversal</h2>
<p>Traversal between nodes of any list type does not remove the previous node, so they behave more like arrays.</p>
<h2>Insertion</h2>
<p>Unlike the [Stack] or [Queue], or the Array, nodes can be inserted inside the list without requiring a new list.</p>
<h2>Queries</h2>
<p>Some queries are possible upon this generalized list, and are made available here. Whether a list contains a value, all instances of a certain value, former N values, hinder N values, and so on. All of these queries either return a boolean or another list which can be queried.</p>
<h1>Considerations</h1>
<p>Use of an iterator is slower than traversal through <code>Node.Ahind</code>, due to the implementation. This is because the list operations largely operate on nodes themselves, not on a cursor, so the cursor heavy iterator has additional overhead. Being simpler, iterators are good for prototyping or when performance doesn't matter, but manual traversal is advised.</p>
<p>As a compromise between iteration and traversal, an <code>each</code> function exists, which traverses through the list for you, constructing an array of the same ordering as the list, which can then be iterated through. The performance overhead is generally less than iteration, while otherwise working the same as iteration (all arrays work in iteration loops). Iterating over this in reverse is also the fastest approach to reverse order iteration through a singly-linked list, if this is occasionally needed. However for more regular need the [Doubly-Linked List] is recommended.</p>
Z 18796031a46098c6ac33d8c5f74b6763