Singly-linked list/Element definition: Difference between revisions
Content added Content deleted
Line 754: | Line 754: | ||
var head = createLinkedListFromArray([10,20,30,40]);</lang> |
var head = createLinkedListFromArray([10,20,30,40]);</lang> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
In this entry, we envision a canonical mapping of SLLs to JSON objects as follows: |
|||
* the empty SLL is represented by `{"next": null}` |
|||
* a non-empty SLL is represented by an object of the form: |
|||
{"item": $item, "next": $next} |
|||
where $next is the canonical representative of a SLL, and $item may be any JSON value. |
|||
Examples: |
|||
* The empty SLL: { "next": null} |
|||
* A SLL holding the value 1 and no other: {"item": 1, "next": null} |
|||
<br> |
|||
Since it may be useful to allow non-canonical representatives of |
|||
SLLs, the following predicates adhere to the following principles: |
|||
* the empty SLL can be represented by any JSON object which does NOT have |
|||
a key named "item" and for which .next is `null`; |
|||
* non-empty SLLs can be represented by JSON objects having an "item" key and |
|||
for which .next is either `null` or a representative of a SLL. |
|||
Note that according to these principles, the JSON value `null` does |
|||
not represent a SLL, and JSON representatives of SLLs may have additional keys. |
|||
<lang jq>def is_empty_singly_linked_list: |
|||
type == "object" and .next == null and (has("item")|not); |
|||
def is_singly_linked_list: |
|||
is_empty_singly_linked_list or |
|||
(type == "object" |
|||
and has("item") |
|||
and (.next | ((. == null) or is_singly_linked_list))); |
|||
# Test for equality without checking for validity: |
|||
def equal_singly_linked_lists($x; $y): |
|||
($x|is_empty_singly_linked_list) as $xempty |
|||
| if $xempty then ($y|is_empty_singly_linked_list) |
|||
elif ($y|is_empty_singly_linked_list) |
|||
then $xempty |
|||
else ($x.item) == ($y.item) |
|||
and equal_singly_linked_lists($x.next; $y.next) |
|||
end;</lang> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |