Doubly-linked list/Definition: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 12:
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
Line 164:
TestAddAfter(7,listEnd)
TestClear()
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_definition.png Screenshot from Atari 8-bit computer]
Line 198:
{{works with|ALGOL 68|Revision 1 - one extension to language used - PRAGMA READ - a non standard feature similar to C's #include directive.}}{{works with|ALGOL 68G|Any - tested with release algol68g-2.7}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
'''File: prelude/Doubly-linked_list_Link.a68'''<
COMMENT REQUIRES:
MODE VALUE = ~;
Line 212:
MODE LINK = REF LINKNEW;
SKIP</
MODE LISTNEW = LINKNEW;
MODE LIST = REF LISTNEW;
Line 259:
link ISNT LINK(self);
SKIP</
# -*- coding: utf-8 -*- #
MODE VALUE = STRING; # user defined data type #
Line 303:
OD;
print(new line)
)</
{{out}}
<pre>
Line 313:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program defDblList.s */
Line 552:
bx lr @ return
</syntaxhighlight>
=={{header|ATS}}==
Line 566:
Here is ''dllist.sats''.
<
(* The public interface *)
Line 635:
(dl : list (t, n)) : dllist_t t
(********************************************************************)</
Here is ''dllist.dats''.
<
#include "share/atspre_staload.hats"
Line 1,019:
end
(********************************************************************)</
And here is ''dllist-demo.dats''.
<
staload "dllist.sats"
Line 1,142:
val _ = print_forwards dl
val _ = println! ()
}</
Line 1,165:
=={{header|C}}==
<
#include <stdio.h>
#include <stdlib.h>
Line 1,321:
n->succ->pred = n->pred;
return n;
}</
Simple test:
<
struct IntNode {
Line 1,359:
free(lista);
}
}</
=={{header|C sharp|C#}}==
Line 1,369:
Though mutating the ''structure'' of a list can only be done through the <code>LinkedList<T></code> class, mutating the values contained by the nodes of a list is done through its individual <code>LinkedListNode<T></code> instances, as the <code>LinkedListNode<T>.Next</code>.Value property is settable.
<
class Program
Line 1,394:
}
}
}</
{{out}}
Line 1,411:
=={{header|C++}}==
{{works with|C++11}}
<
#include <list>
Line 1,424:
std::cout << i << ' ';
std::cout << '\n';
}</
{{out}}
<pre>
Line 1,431:
=={{header|Clojure}}==
<
(defprotocol PDoubleList
Line 1,541:
(defmethod print-method Node [n w]
(print-method (symbol "#:double_list.Node") w)
(print-method (into {} (dissoc n :m)) w))</
Usage:
<
;=> nil
(def dl (double-list (range 10)))
Line 1,564:
;=> #:double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}
(get-prev *1)
;=> #:double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}</
=={{header|Common Lisp}}==
<
(defstruct dlink content prev next)
Line 1,615:
acc
(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
(reverse (extract-values (dlist-head dlist) nil))))</
The following produces <code>(1 2 3 4)</code>.
<
(insert-head dlist 1)
(insert-tail dlist 4)
Line 1,626:
(bad-link (insert-before dlist next-to-last 42)))
(remove-link dlist bad-link))
(print (dlist-elements dlist)))</
=={{header|D}}==
<
class LinkedList(T)
Line 1,736:
}
writeln;
}</
{{out}}
<pre>
Line 1,747:
{{libheader| boost.LinkedList}}[[https://github.com/MaiconSoft/DelphiBoostLib]]
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Doubly_linked;
Line 1,786:
List.Free;
Readln;
end.</
=={{header|E}}==
<
def firstINode
def lastINode
Line 1,895:
}
return dlList
}</
<
# value: <>
Line 1,927:
? for x in 11..20 { list.push(x) }
? list
# value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20></
=={{header|Erlang}}==
As with [[Singly-linked_list/Element_insertion]] a process is used to get mutability in Erlang's single assignment world.
<syntaxhighlight lang="erlang">
-module( doubly_linked_list ).
Line 1,999:
loop_foreach_previous( _Fun, noprevious ) -> ok;
loop_foreach_previous( Fun, Next ) -> Next ! {foreach_previous, Fun}.
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
type DList<'T> = {mutable front: DListAux<'T> option; mutable back: DListAux<'T> option} //'
Line 2,029:
if link.next = dlist.back then addBack dlist elt else
let e = Some {prev=Some link; data=elt; next=link.next}
link.next <- e</
=={{header|Fortran}}==
Tested with g95 and gfortran v. 4.6.
<
module dlist
implicit none
Line 2,241:
call tidy(mydll)
end program dl
</syntaxhighlight>
{{out}}
Line 2,251:
=={{header|Go}}==
Go has nothing like an enforced invariant. Responsibility for preventing circular loops must be shared by all code that modifies the list. Given that, the following declaration ''enables'' code to do that efficiently.
<
int
next, prev *dlNode
Line 2,263:
members map[*dlNode]int
head, tail **dlNode
}</
Or, just use the [http://golang.org/pkg/container/list/#Element container/list] package:
<
import "fmt"
Line 2,282:
fmt.Println(e.Value)
}
}</
=={{header|Haskell}}==
For an efficient implementation, see the <code>Data.FDList</code> module provided by [http://hackage.haskell.org/package/liboleg liboleg]. But before using doubly linked lists at all, see [http://stackoverflow.com/questions/1844195/doubly-linked-list-in-a-purely-functional-programming-language this discussion on Stack Overflow].
<
type NodeID = Maybe Rational
Line 2,341:
fromList = foldr fcons empty
toList = map vNode . M.elems</
An example of use:
<
where l = mcons 'M' n1 n2 x
x = rcons 'Z' $ fcons 'a' $ fcons 'q' $ singleton 'w'
n1 = firstNode x
Just n2 = nextNode x n1</
==Icon and {{header|Unicon}}==
Line 2,357:
The DoubleList is made from elements of DoubleLink. [[Doubly-Linked List (element)#Icon_and_Unicon]], [[Doubly-Linked List (element insertion)#Icon_and_Unicon]] and [[Doubly-Linked List (traversal)#Icon_and_Unicon]]
<syntaxhighlight lang="unicon">
class DoubleList (item)
Line 2,396:
self.item := DoubleLink (value)
end
</syntaxhighlight>
An <code>insert_before</code> method was added to the DoubleLink class:
<syntaxhighlight lang="unicon">
# insert given node before this one, losing its existing connections
method insert_before (node)
Line 2,408:
self.prev_link := node
end
</syntaxhighlight>
To test the double-linked list:
<syntaxhighlight lang="unicon">
procedure main ()
dlist := DoubleList (5)
Line 2,425:
write (node.value)
end
</syntaxhighlight>
{{out}}
Line 2,495:
The <code>LinkedList<T></code> class is the Doubly-linked list implementation in Java. There are a large number of methods supporting the list. An example is shown below.
<
import java.util.LinkedList;
Line 2,521:
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,540:
=={{header|Julia}}==
Regarding the avoidance or circular loops part of this task, a call to <syntaxhighlight lang
<
value::T
pred::Union{DLNode{T}, Nothing}
Line 2,613:
delete(node4)
print("From end to beginning post deletion: "); printconnected(node1, fromtail = true)
</
First value is 1 and last value is 3
From beginning to end: 1 -> 4 -> 2 -> 3
Line 2,621:
=={{header|Kotlin}}==
Rather than use the java.util.LinkedList<E> class, we will write our own simple LinkedList<E> class for this task:
<
class LinkedList<E> {
Line 2,686:
ll.insert(ll.last!!.prev, 3)
println(ll)
}</
{{out}}
Line 2,694:
=={{header|Lua}}==
<
-------------------
-- IMPLEMENTATION:
Line 2,802:
local n222 = list:insertAfter(n22, 222) validate(list, "-1,0,1,11,111,2,22,222,3,33,4,44,444,5,55")
local n333 = list:insertBefore(n4, 333) validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55")
local n555 = list:insertAfter(n55, 555) validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55,555")</
{{out}}
<pre>true
Line 2,837:
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Form 80, 50
Line 3,005:
}
Checkit
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
ds["Append", #] & /@ {1, 5, 7, 0, 3, 2};
ds["Prepend", 9];
Line 3,014:
(* This is adding at the end and then swap to insert in to the middle: *)
ds["Append", 14]; ds["SwapPart", Round[ds["Length"]/2], ds["Length"]];
ds["Elements"]</
{{out}}
<pre>{9, 1, 5, 14, 0, 3, 2, 4, 7}</pre>
Line 3,020:
=={{header|Nim}}==
Nim has a doubly linked list already in the lists module of the standard library.
<
List[T] = object
head, tail: Node[T]
Line 3,087:
l2.prepend newNode("hello")
l2.append newNode("world")
echo l2</
{{out}}
<pre>15 -> 14 -> 12
Line 3,093:
=={{header|Oberon-2}}==
<
IMPORT Basic;
TYPE
Line 3,106:
size-: INTEGER;
END;
</syntaxhighlight>
=={{header|Objeck}}==
<
use Collection;
Line 3,126:
while(list->Get() <> Nil);
}
}</
=={{header|Oforth}}==
<
DNode method: initialize := next := prev := value ;
Line 3,179:
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
dl ;</
{{out}}
Line 3,201:
| | | ---+---> end
+-----+-----+
<
(de 2list @
(let Prev NIL
Line 3,210:
(cons L Prev) ) ) )
(setq *DLst (2list 'was 'it 'a 'cat 'I 'saw))</
For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
define structure
1 Node,
Line 3,220:
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
</syntaxhighlight>
=={{header|PowerShell}}==
Create and populate the list:
<syntaxhighlight lang="powershell">
$list = New-Object -TypeName 'Collections.Generic.LinkedList[PSCustomObject]'
Line 3,233:
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 3,249:
</pre>
Insert a value at the head:
<syntaxhighlight lang="powershell">
$list.AddFirst([PSCustomObject]@{ID=123; X=123;Y=123}) | Out-Null
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 3,270:
</pre>
Insert a value in the middle:
<syntaxhighlight lang="powershell">
$current = $list.First
Line 3,285:
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 3,303:
</pre>
Insert a value at the end:
<syntaxhighlight lang="powershell">
$list.AddLast([PSCustomObject]@{ID=789; X=789;Y=789}) | Out-Null
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 3,327:
=={{header|PureBasic}}==
<
;the list of words that will be added to the list
words:
Line 3,394:
displayList(a(),"Insertion in Middle: ")
Repeat: Until Inkey() <> ""</
{{out}}
<pre>
Line 3,411:
datatype. See [https://wiki.python.org/moin/TimeComplexity TimeComplexity].
<
from collections import deque
Line 3,422:
for value in reversed(some_list):
print(value)
</syntaxhighlight>
{{out}}
Line 3,451:
break links between nodes in other lists.
<
"""A doubly-linked list. Requires Python >=3.7"""
from __future__ import annotations
Line 3,620:
self.size -= 1
return value
</syntaxhighlight>
=={{header|Racket}}==
The following is a port of the Common Lisp solution. The ouput is '(1 2 3 4).
<
#lang racket
(define-struct dlist (head tail) #:mutable #:transparent)
Line 3,685:
(remove-link dlist bad-link))
(dlist-elements dlist))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
This shows a complete example. (Other entries in the section focus on aspects of this solution.)
<syntaxhighlight lang="raku"
has DLElem[T] $.prev is rw;
has DLElem[T] $.next is rw;
Line 3,749:
say $dll.list; # 0 1 2 40 41 42
say $dll.reverse; # 42 41 40 2 1 0</
{{out}}
<pre>0 1 2 40 41 42
Line 3,780:
REXX doesn't have linked lists, as there are no pointers (or handles).
<br>However, linked lists can be simulated with lists in REXX.
<
call sy 'initializing the list.' ; call @init
call sy 'building list: Was it a cat I saw' ; call @put "Was it a cat I saw"
Line 3,823:
/*──────────────────────────────────────────────────────────────────────────────────────*/
@show: procedure expose $.; parse arg k,m,dir; if dir==-1 & k=='' then k=$.#
m=p(m $.#); call @parms 'kmd'; say @get(k,m, dir); return</
'''output'''
<pre style="height:30ex;overflow:scroll">
Line 3,862:
=={{header|Ring}}==
<
# Project : Doubly-linked list/Definition
Line 3,879:
svect = left(svect, len(svect) - 1)
see svect
</syntaxhighlight>
Output:
<pre>
Line 3,898:
<
(r7rs)
(chicken (import r7rs)))
Line 4,071:
(display "conversion from a list:")
(print-it (list->dllist (list "a" "b" "c")))</
{{out}}
Line 4,088:
=={{header|Swift}}==
<syntaxhighlight lang="text">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
class Node<T> {
Line 4,230:
list.remove(node!)
print(list)</
{{out}}
Line 4,253:
See also [[Doubly-Linked List (element)]] for a TclOO-based version.
<
proc dl {_name cmd {where error} {value ""}} {
upvar 1 $_name N
Line 4,323:
}
}
}</
<
set testcases [split {
dl D insert head foo
Line 4,349:
if {[lsearch $argv -p] >= 0} {parray D}
}
}</
=={{header|Visual Basic .NET}}==
<
Private m_Head As Node(Of T)
Private m_Tail As Node(Of T)
Line 4,480:
End Sub
End Class</
=={{header|Wren}}==
{{libheader|Wren-llist}}
The DLinkedList class in the above module is a generic doubly-linked list and is implemented in such a way that circular loops are not possible. We therefore use it here.
<
var dll = DLinkedList.new()
Line 4,491:
System.print(dll)
for (i in 1..3) dll.remove(i)
System.print(dll)</
{{out}}
Line 4,500:
=={{header|zkl}}==
<
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
Line 4,525:
}.fp(Ref(self),dir))
}
}</
<
a.append("c").append("d");
a.last().append("e");
a.last().first().append("b");
foreach n in (a){ print(n," ") } println();
foreach n in (a.last().walker(False)){ print(n," ") } println();</
{{out}}
<pre>
|