Singly-linked list/Reversal: Difference between revisions
m (→{{header|Julia}}: sp) |
|||
Line 48: | Line 48: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Modern processors with large caches and fast memory access for ordinary |
Modern processors with large caches and fast memory access for ordinary vectors and databases for larger types of data structures have made linked lists nearly obsolete. In Julia, arrays are almost always preferred to linked lists. A linked list class is available in the DataStructures.jl package. The code below is abridged from that module, which can be read in its full form at https://github.com/JuliaCollections/DataStructures.jl/blob/master/src/list.jl. |
||
<syntaxhighlight lang="julia">abstract type LinkedList{T} end |
<syntaxhighlight lang="julia">abstract type LinkedList{T} end |
||
Revision as of 01:25, 2 April 2023
- I don't even know how to reverse a linked-list, and I don't even know what that is. -- a YouTuber.
Reverse a linked list. Obviously you can do it by turning it into a normal list and back, but feel free to use a smarter, possibly more efficient way.
ALGOL 68
Using the code from the Singly-linked list/Traversal#ALGOL_68 Task
LOC and HEAP are like NEW in other languages. LOC generates a new item on the stack and HEAP a new item on the heap (which is garbage collected).
The use of LOC in the outermost level is OK as the generated elements will exist until the final END, but HEAP must be used in the loop creating the reverse list elements, to ensure they still exist when the loop exits.
BEGIN
MODE STRINGLIST = STRUCT(STRING value, REF STRINGLIST next);
# construct a STRINGLIST with a few elements #
STRINGLIST list := ("Big",
LOC STRINGLIST := ("fjords",
LOC STRINGLIST := ("vex",
LOC STRINGLIST := ("quick",
LOC STRINGLIST := ("waltz",
LOC STRINGLIST := ("nymph",NIL))))));
# print the list and build the reverse list #
REF STRINGLIST node := list;
REF STRINGLIST reverse := REF STRINGLIST(NIL);
WHILE node ISNT REF STRINGLIST(NIL) DO
reverse := HEAP STRINGLIST
:= STRINGLIST( value OF node, reverse );
print((value OF node, space));
node := next OF node
OD;
print(newline);
# print the reverse list #
node := reverse;
WHILE node ISNT REF STRINGLIST(NIL) DO
print((value OF node, space));
node := next OF node
OD;
print(newline)
END
- Output:
Big fjords vex quick waltz nymph nymph waltz quick vex fjords Big
Julia
Modern processors with large caches and fast memory access for ordinary vectors and databases for larger types of data structures have made linked lists nearly obsolete. In Julia, arrays are almost always preferred to linked lists. A linked list class is available in the DataStructures.jl package. The code below is abridged from that module, which can be read in its full form at https://github.com/JuliaCollections/DataStructures.jl/blob/master/src/list.jl.
abstract type LinkedList{T} end
Base.eltype(::Type{<:LinkedList{T}}) where T = T
mutable struct Nil{T} <: LinkedList{T} end
mutable struct Cons{T} <: LinkedList{T}
head::T
tail::LinkedList{T}
end
cons(h, t::LinkedList{T}) where {T} = Cons{T}(h, t)
nil(T) = Nil{T}()
nil() = nil(Any)
head(x::Cons) = x.head
tail(x::Cons) = x.tail
function Base.show(io::IO, l::LinkedList{T}) where T
if isa(l,Nil)
if T === Any
print(io, "nil()")
else
print(io, "nil(", T, ")")
end
else
print(io, "list(")
show(io, head(l))
for t in tail(l)
print(io, ", ")
show(io, t)
end
print(io, ")")
end
end
function list(elts...)
l = nil(Base.promote_typeof(elts...))
for i=length(elts):-1:1
l = cons(elts[i],l)
end
return l
end
Base.iterate(l::LinkedList, ::Nil) = nothing
function Base.iterate(l::LinkedList, state::Cons = l)
state.head, state.tail
end
function Base.reverse(l::LinkedList{T}) where T
l2 = nil(T)
for h in l
l2 = cons(h, l2)
end
return l2
end
llist = list(1, 2, 3, 4, 5)
revlist = reverse(llist)
@show llist revlist
- Output:
llist = list(1, 2, 3, 4, 5) revlist = list(5, 4, 3, 2, 1)
Wren
The LinkedList class in Wren-llist represents a singly-linked list.
It's possible to iterate backwards through this without creating an intermediate list by traversing through it until you reach the last element, then traversing through it again until you reach the penultimate element and so on until you reach the first element. This is easy to code since LinkedList has an indexer which works in precisely this manner.
It's also possible to iterate backwards through the linked list using the generic reverse iterator in Wren-iterate. However, this does create a list internally and then iterates backwards through that.
You could, of course, create a new LinkedList and then add elements to it as you iterate through them in reverse order.
However, it's also possible to reverse the LinkedList in place by successively exchanging elements at both ends. Internally, the 'exchange' method uses the indexer to swap elements.
import "./llist" for LinkedList
import "./iterate" for Reversed
var pangram = "Big fjords vex quick waltz nymph"
var elements = pangram.split(" ")
var sll = LinkedList.new(elements)
// iterate forwards
for (e in sll) System.write("%(e) ")
System.print("\n")
// iterate backwards without creating a list
for (i in sll.count-1..0) System.write("%(sll[i]) ")
System.print("\n")
// iterate backwards by creating a list internally
for (e in Reversed.new(sll)) System.write("%(e) ")
System.print()
// reverse the linked list in place
var i = 0
var j = sll.count - 1
while (i < j) {
sll.exchange(i, j)
i = i + 1
j = j - 1
}
// now we can iterate forwards
for (e in sll) System.write("%(e) ")
System.print()
- Output:
Big fjords vex quick waltz nymph nymph waltz quick vex fjords Big nymph waltz quick vex fjords Big nymph waltz quick vex fjords Big