Doubly-linked list/Element definition: Difference between revisions
Doubly-linked list/Element definition (view source)
Revision as of 11:59, 28 November 2023
, 5 months ago→{{header|Wren}}: Minor tidy
(→{{header|zkl}}: rewrite to suit other tasks) |
m (→{{header|Wren}}: Minor tidy) |
||
(40 intermediate revisions by 23 users not shown) | |||
Line 11:
{{Template:See also lists}}
<br><br>
=={{header|Action!}}==
<syntaxhighlight lang="action!">DEFINE PTR="CARD"
TYPE ListNode=[
BYTE data
PTR prv,nxt]</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_definition.png Screenshot from Atari 8-bit computer]
=={{header|Ada}}==
<
type Link_Access is access Link;
type Link is record
Line 19 ⟶ 28:
Prev : Link_Access := null;
Data : Integer;
end record;</
Using generics, the specification might look like this:
<
type Element_Type is private;
package Linked_List is
Line 43 ⟶ 52:
Traversing : Boolean := False; -- True when in a traversal.
end record;
end Linked_List;</
In Ada 2005 this example can be written without declaration of an access type:
<
Next : not null access Link := Link'Unchecked_Access;
Prev : not null access Link := Link'Unchecked_Access;
Data : Integer;
end record;</
Here the list element is created already pointing to itself, so that no further initialization is required. The type of the element is marked as ''limited'' indicating that such elements have referential semantics and cannot be copied.
Ada's standard container library includes a generic doubly linked list. The structure of the link element is private.
=={{header|ALGOL 68}}==
Line 59 ⟶ 67:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.7 algol68g-2.7].}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
'''File: prelude/link.a68'''<
CO REQUIRES:
MODE OBJVALUE = ~ # Mode/type of actual obj to be queued #
Line 73 ⟶ 81:
PROC obj link free = (REF OBJLINK free)VOID:
prev OF free := next OF free := obj queue empty # give the garbage collector a big hint #</
=={{header|ALGOL W}}==
<syntaxhighlight lang="algolw"> % record type to hold an element of a doubly linked list of integers %
record DListIElement ( reference(DListIElement) prev
; integer iValue
; reference(DListIElement) next
);
% additional record types would be required for other element types %</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* structure Node Doublylinked List*/
.struct 0
NDlist_next: @ next element
.struct NDlist_next + 4
NDlist_prev: @ previous element
.struct NDlist_prev + 4
NDlist_value: @ element value or key
.struct NDlist_value + 4
NDlist_fin:
</syntaxhighlight>
=={{header|AutoHotkey}}==
Line 79 ⟶ 112:
=={{header|Axe}}==
<
r₂→{r₁}ʳ
0→{r₁+2}ʳ
Line 96 ⟶ 129:
Lbl VALUE
{r₁}ʳ
Return</
=={{header|
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
</syntaxhighlight>
=={{header|Bracmat}}==
<syntaxhighlight lang="bracmat">link=(prev=) (next=) (data=)</syntaxhighlight>
=={{header|C}}==
It basically doesn't matter if we use the name link, node, Node or some other name. These are matters of taste and aesthetics. However, it is important that the C language is case-sensitive and that the namespace for structures is separate.
<syntaxhighlight lang="c">struct Node
{
struct
struct
void *data;
};</syntaxhighlight>
An alternative technique is to define a pointer type by typedef as shown below. The advantage here is that you do not have to write struct everywhere - assuming that you will most often need a pointer to a struct Node, not the structure itself.
<syntaxhighlight lang="c">
struct Node;
typedef struct Node* Node;
struct Node
{
Node next;
Node prev;
void* data;
};
</syntaxhighlight>
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">class Link
{
public int Item { get; set; }
public Link Prev { get; set; }
public Link Next { get; set; }
//A constructor is not neccessary, but could be useful
public Link(int item, Link prev = null, Link next = null) {
Item = item;
Prev = prev;
Next = next;
}
}</syntaxhighlight>
=={{header|C++}}==
C++ has doubly linked list class template in standard library. However actual list noded are treated as implementation detail and encapsulated inside list. If we were to reimplement list, then node could look like that:
<
struct Node
{
Line 120 ⟶ 183:
Node* prev;
T data;
};</
=={{header|Clojure}}==
Line 134 ⟶ 189:
This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better.
<
(defn new-node [prev next data]
(Node. (ref prev) (ref next) data))</
=={{header|Common Lisp}}==
<
(defstruct dlink content prev next)</
See the functions on the [[Doubly-Linked List]] page for the usage of these structures.
Line 148 ⟶ 203:
=={{header|D}}==
A default constructor is implicit:
<
T data;
typeof(this)* prev, next;
Line 156 ⟶ 211:
alias N = Node!int;
N* n = new N(10);
}</
=={{header|Delphi}}==
<
type
Line 171 ⟶ 226:
end;
}</
=={{header|E}}==
Line 177 ⟶ 232:
This does no type-checking, under the assumption that it is being used by a containing doubly-linked list object which enforces that invariant along with others such as that <code>element.getNext().getPrev() == element</code>. See [[Doubly-Linked List#E]] for an actual implementation (which uses slightly more elaborate nodes than this).
<
def element {
to setValue(v) { value := v }
Line 190 ⟶ 245:
return element
}</
=={{header|Erlang}}==
Using the code in [[Doubly-linked_list/Definition]] the element is defined by:
<syntaxhighlight lang="erlang">
new( Data ) -> erlang:spawn( fun() -> loop( Data, noprevious, nonext ) end ).
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
type 'a DLElm = {
mutable prev: 'a DLElm option
data: 'a
mutable next: 'a DLElm option
}
</syntaxhighlight>
=={{header|Factor}}==
<syntaxhighlight lang="factor">TUPLE: node data next prev ;</syntaxhighlight>
=={{header|Fortran}}==
In ISO Fortran 95 or later:
<
real :: data
type(node), pointer :: next => null(), previous => null()
Line 207 ⟶ 274:
! . . . .
!
type( node ), target :: head</
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">type node
nxt as node ptr
prv as node ptr
dat as any ptr 'points to any kind of data; user's responsibility
'to keep track of what's actually in it
end type</syntaxhighlight>
=={{header|Go}}==
<
string
next, prev *dlNode
}</
Or, using the [http://golang.org/pkg/container/list/#Element container/list] package:
<
var node list.Element
// and using: node.Next(), node.Prev(), node.Value</
=={{header|Haskell}}==
Line 225 ⟶ 300:
Note that unlike naive pointer manipulation which could corrupt the doubly-linked list, updateLeft and updateRight will always yield a well-formed data structure.
<
data DList a = Leaf | Node (DList a) a (DList a)
Line 239 ⟶ 314:
where current = Node l v next
next = updateRight nr new
</syntaxhighlight>
==Icon and {{header|Unicon}}==
Line 245 ⟶ 320:
Uses Unicon classes.
<syntaxhighlight lang="unicon">
class DoubleLink (value, prev_link, next_link)
initially (value, prev_link, next_link)
Line 252 ⟶ 327:
self.next_link := next_link
end
</syntaxhighlight>
=={{header|J}}==
Line 262 ⟶ 337:
Nevertheless, this is doable, though it necessarily departs from the definition specified at [[Doubly-linked_list/Definition#J]].
<
create=:3 :0
this=:coname''
'predecessor successor data'=:y
successor__predecessor=: predecessor__successor=: this
)</
Here, when we create a new list element, we need to specify its successor node and its predecessor node and the data to be stored in the node. To start a new list we will need a node that can be the head and the tail of the list -- this will be the successor node for the last element of the list and the predecessor node for the first element of the list:
<
create=:3 :0
predecessor=:successor=:this=: coname''
)</
=={{header|Java}}==
{{works with|Java|1.5+}}
<
private T element;
private Node<T> next, prev;
Line 319 ⟶ 394:
return prev;
}
}</
For use with [[Java]] 1.4 and below, delete all "<T>"s and replace T's with "Object".
Line 325 ⟶ 400:
=={{header|JavaScript}}==
Inherits from LinkedList (see [[Singly-Linked_List_(element)#JavaScript]])
<
this._value = value;
this._next = next;
Line 351 ⟶ 426:
}
var head = createDoublyLinkedListFromArray([10,20,30,40]);</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">abstract type AbstractNode{T} end
struct EmptyNode{T} <: AbstractNode{T} end
mutable struct Node{T} <: AbstractNode{T}
value::T
pred::AbstractNode{T}
succ::AbstractNode{T}
end</syntaxhighlight>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.1.2
class Node<T: Number>(var data: T, var prev: Node<T>? = null, var next: Node<T>? = null) {
override fun toString(): String {
val sb = StringBuilder(this.data.toString())
var node = this.next
while (node != null) {
sb.append(" -> ", node.data.toString())
node = node.next
}
return sb.toString()
}
}
fun main(args: Array<String>) {
val n1 = Node(1)
val n2 = Node(2, n1)
n1.next = n2
val n3 = Node(3, n2)
n2.next = n3
println(n1)
println(n2)
println(n3)
}</syntaxhighlight>
{{out}}
<pre>
1 -> 2 -> 3
2 -> 3
3
</pre>
=={{header|Lang}}==
<syntaxhighlight lang="lang">
&Node = {
$next
$prev
$data
}
</syntaxhighlight>
=={{header|Lua}}==
see [[Doubly-linked_list/Definition#Lua]], essentially:
<syntaxhighlight lang="lua">local node = { data=data, prev=nil, next=nil }</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Mathematica and the Wolfram Language have no lower-level way of handling pointers. It does have a built-in, compilable doubly-linked list data structure:
<syntaxhighlight lang="mathematica">CreateDataStructure["DoublyLinkedList"]</syntaxhighlight>
=={{header|Modula-2}}==
<
Link = POINTER TO LinkRcd;
LinkRcd = RECORD
Prev, Next: Link;
Data: INTEGER
END;</
=={{header|Nim}}==
<
Node[T] = ref TNode[T]
TNode[T] = object
next, prev: Node[T]
data: T</
=={{header|Oberon-2}}==
<syntaxhighlight lang="oberon2">
MODULE Box;
TYPE
Object* = POINTER TO ObjectDesc;
ObjectDesc* = (* ABSTRACT *) RECORD
END;
(* ... *)
END Box.
MODULE Collections;
TYPE
Node* = POINTER TO NodeDesc;
NodeDesc* = (* ABSTRACT *) RECORD
prev-,next-: Node;
value-: Box.Object;
END;
(* ... *)
END Collections.
</syntaxhighlight>
=={{header|Objeck}}==
<
@value : Base;
@next : ListNode;
Line 403 ⟶ 563:
return @previous;
}
}</
=={{header|OCaml}}==
===Imperative===
<
mutable data: 'a;
mutable next: 'a dlink option;
Line 448 ⟶ 608:
in
aux
;;</
<
iter_forward_dlink (Printf.printf "%d\n") dl ;;
1
Line 457 ⟶ 617:
4
5
- : unit = ()</
===Functional===
Line 464 ⟶ 624:
examples of this page and its task, but in regular OCaml these kind of imperative structures can be advantageously replaced by a functional equivalent, that can be use in the same area, which is to have a list of elements and be able to point to one of these. We can use this type:
<
The middle element is the pointed item, and the two lists are the
previous and the following items.
Here are the associated functions:
<
| hd::tl -> [], hd, tl
| [] -> invalid_arg "empty list"
Line 486 ⟶ 646:
prev_tl, prev, item::next
| _ ->
failwith "begin of nav_list reached"</
<
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])
# let nl = next nl ;;
Line 495 ⟶ 655:
# current nl ;;
- : int = 3</
=={{header|Oforth}}==
Line 501 ⟶ 661:
Complete definition is here : [[../Definition#Oforth]]
<
=={{header|Oz}}==
We show how to create a new node as a record value.
<
node(prev:{NewCell _}
next:{NewCell _}
value:Value)
end</
Note: this is for illustrative purposes only. In a real Oz program, you would use one of the existing data types.
=={{header|Pascal}}==
<
data_ptr = ^data; (* presumes that type 'data' is defined above *)
link = record
Line 520 ⟶ 680:
next: link_ptr;
data: data_ptr;
end;</
=={{header|Perl}}==
<
data => 'say what',
next => \%foo_node,
prev => \%bar_node,
);
$node{next} = \%quux_node; # mutable</
=={{header|Phix}}==
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span>
<span style="color: #008080;">type</span> <span style="color: #000000;">slnode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">DATA</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;"><</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">udt</span><span style="color: #0000FF;"></</span><span style="color: #000000;">i</span><span style="color: #0000FF;">>(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
<!--</syntaxhighlight>-->
But more often you would just use the builtin sequences. See also [[Singly-linked_list/Element_definition#Phix|Singly-linked_list/Element_definition]].
Memory is automatically reclaimed the moment items are no longer needed.
Note that automatic typechecking does not occur under pwa/p2js, that is desktop/Phix only (for the debugging stage) but you can invoke a type such as the above explicitly.
=={{header|PicoLisp}}==
Line 595 ⟶ 718:
With that, 'cddr' can be used to access the next, and 'cadr' to access the
previous element.
<syntaxhighlight lang="picolisp">(de 2tail (X DLst)
(
(con DLst (cons X L NIL))
(if L
(con (cdr L) (cdr DLst))
(set DLst (cdr DLst)) ) ) )
(de 2head (X DLst)
(let L (car DLst) # Get current data list
(set DLst (cons X NIL L)) # Prepend two new cons pairs
Line 604 ⟶ 733:
# We prepend 'not' to the list in the previous example
(
For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
define structure
1 Node,
2 value fixed decimal,
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
P = NEW(: Node :); /* Creates a node, and lets P point at it. */
get (P => value); /* Reads in a value to the node we just created. */
/* Assuming that back_pointer and fwd_pointer point at other nodes, */
/* we can say ... */
P = P => fwd_pointer; /* P now points at the next node. */
...
P = P => back_pointer; /* P now points at the previous node. */
</syntaxhighlight>
=={{header|Plain English}}==
When you define a <code>thing</code>, you are defining a record as a doubly-linked list element. <code>next</code> and <code>previous</code> fields are implicitly added to the record that can be used to build and traverse a list.
<syntaxhighlight lang="plainenglish">An element is a thing with a number.</syntaxhighlight>
=={{header|Pop11}}==
<
define :class Link;
slot next = [];
slot prev = [];
slot data = [];
enddefine;</
=={{header|PureBasic}}==
<
*prev.node
*next.node
value.i
EndStructure</
=={{header|Python}}==
<
def __init__(self, data = None, prev = None, next = None):
self.prev = prev
Line 642 ⟶ 794:
while c != None:
yield c
c = c.prev</
=={{header|Racket}}==
<
(define-struct dlist (head tail) #:mutable)
(define-struct dlink (content prev next) #:mutable)
</syntaxhighlight>
See the functions on the [[Doubly-Linked List]] page for the usage of these structures.
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>role DLElem[::T] {
has DLElem[T] $.prev is rw;
has DLElem[T] $.next is rw;
has T $.payload = T;
method pre-insert(T $payload) {
die "Can't insert before beginning" unless $!prev;
my $elem = ::?CLASS.new(:$payload);
$!prev.next = $elem;
$elem.prev = $!prev;
$elem.next = self;
$!prev = $elem;
$elem;
}
method post-insert(T $payload) {
die "Can't insert after end" unless $!next;
my $elem = ::?CLASS.new(:$payload);
$!next.prev = $elem;
$elem.next = $!next;
$elem.prev = self;
$!next = $elem;
$elem;
}
method delete {
die "Can't delete a sentinel" unless $!prev and $!next;
$!next.prev = $!prev;
$!prev.next = $!next; # conveniently returns next element
}
}</syntaxhighlight>
=={{header|REXX}}==
Line 678 ⟶ 865:
║ @del k,m ─── deletes the M items starting with item K. ║
╚═════════════════════════════════════════════════════════════════════════╝
<
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 721 ⟶ 908:
/*──────────────────────────────────────────────────────────────────────────────────────*/
@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>
Line 761 ⟶ 948:
=={{header|Ruby}}==
Extending [[Singly-Linked List (element)#Ruby]]
<
attr_accessor :prev
# accessors :succ and :value are inherited
Line 780 ⟶ 967:
end
list = DListNode.from_values 1,2,3,4</
=={{header|Rust}}==
Line 786 ⟶ 973:
=== Simply using the standard library ===
<
fn main() {
// Doubly linked list containing 32-bit integers
let list = LinkedList::<i32>::new();
}</
=== The behind-the-scenes implementation ===
Doubly linked lists present a problem in Rust due to its ownership model. There cannot be two mutable references to the same object, so what are we to do? Below are the relevant lines (with added comments) from the <code>std</code> implementation ([https://doc.rust-lang.org/std/collections/struct.LinkedList.html Documentation] [https://github.com/rust-lang/rust/blob/master/src/libcollections/linked_list.rs Source]).
The standard library uses the (currently) unstable `Shared<T>` type which indicates that the ownership of its contained type has shared ownership. It is guaranteed not to be null, is variant over <code>T</code> (meaning that an <code>&Shared<&'static T></code> may be used where a <code>&Shared<&'a T></code> is expected, indicates to the compiler that it may own a <code>T</code>) and may be dereferenced to a mutable pointer (<code>*mut T</code>). All of the above may be accomplished in standard stable Rust, except for the non-null guarantee which allows the compiler to make a few extra optimizations.
<syntaxhighlight lang
head: Option<Shared<Node<T>>>,
marker: PhantomData<Box<Node<T>>>, // Indicates that we logically own a boxed (owned pointer) Node<T>>
}
struct Node<T> {
next:
prev:
}</
=={{header|Sidef}}==
<
data => 'say what',
next => foo_node,
Line 822 ⟶ 1,004:
);
node{:next} = quux_node; # mutable</
=={{header|Swift}}==
<syntaxhighlight lang="swift">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
class Node<T> {
var value: T
fileprivate var prev: NodePtr<T>?
fileprivate var next: NodePtr<T>?
init(value: T, prev: NodePtr<T>? = nil, next: NodePtr<T>? = nil) {
self.value = value
self.prev = prev
self.next = next
}
}
</syntaxhighlight>
=={{header|Tcl}}==
{{eff note|Tcl|list}}
{{works with|Tcl|8.6}} or {{libheader|TclOO}}
<
variable content next prev
constructor {value {list ""}} {
Line 846 ⟶ 1,045:
set prev {*}$args
}
}</
=={{header|Visual Basic .NET}}==
<
Public Value As T
Public [Next] As Node(Of T)
Public Previous As Node(Of T)
End Class</
=={{header|Wren}}==
{{libheader|Wren-llist}}
The DNode class in the above module is the element type for the DLinkedList class which is a generic doubly-linked list. The latter is implemented in such a way that the user does not need to deal directly with DNode though for the purposes of the task we show below how instances of it can be created and manipulated.
<syntaxhighlight lang="wren">import "./llist" for DNode
var dn1 = DNode.new(1)
var dn2 = DNode.new(2)
dn1.next = dn2
dn1.prev = null
dn2.prev = dn1
dn2.next = null
System.print(["node 1", "data = %(dn1.data)", "prev = %(dn1.prev)", "next = %(dn1.next)"])
System.print(["node 2", "data = %(dn2.data)", "prev = %(dn2.prev)", "next = %(dn2.next)"])</syntaxhighlight>
{{out}}
<pre>
[node 1, data = 1, prev = null, next = 2]
[node 2, data = 2, prev = 1, next = null]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">
def \Node\ Prev, Data, Next; \Element (Node) definition
</syntaxhighlight>
=={{header|zkl}}==
<
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
fcn toString{ value.toString() }
}</
<
a.next=b; b.prev=a;
println(a.next," ",b.prev);</
{{out}}
<pre>
|