Doubly-linked list/Element definition: Difference between revisions
(Racket) |
m (→{{header|Wren}}: Minor tidy) |
||
(75 intermediate revisions by 37 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Data Structures}} |
{{task|Data Structures}} |
||
Define the data structure for a [[Linked_List#Doubly-Linked_List|doubly-linked list]] element. The element should include a data member to hold its value and pointers to both the next element in the list and the previous element in the list. The pointers should be mutable. |
|||
;Task: |
|||
Define the data structure for a [[Linked_List#Doubly-Linked_List|doubly-linked list]] element. |
|||
The element should include a data member to hold its value and pointers to both the next element in the list and the previous element in the list. |
|||
The pointers should be mutable. |
|||
{{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}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">type Link; |
||
type Link_Access is access Link; |
type Link_Access is access Link; |
||
type Link is record |
type Link is record |
||
Line 9: | Line 28: | ||
Prev : Link_Access := null; |
Prev : Link_Access := null; |
||
Data : Integer; |
Data : Integer; |
||
end record;</ |
end record;</syntaxhighlight> |
||
Using generics, the specification might look like this: |
Using generics, the specification might look like this: |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
package Linked_List is |
package Linked_List is |
||
Line 33: | Line 52: | ||
Traversing : Boolean := False; -- True when in a traversal. |
Traversing : Boolean := False; -- True when in a traversal. |
||
end record; |
end record; |
||
end Linked_List;</ |
end Linked_List;</syntaxhighlight> |
||
In Ada 2005 this example can be written without declaration of an access type: |
In Ada 2005 this example can be written without declaration of an access type: |
||
< |
<syntaxhighlight lang="ada">type Link is limited record |
||
Next : not null access Link := Link'Unchecked_Access; |
Next : not null access Link := Link'Unchecked_Access; |
||
Prev : not null access Link := Link'Unchecked_Access; |
Prev : not null access Link := Link'Unchecked_Access; |
||
Data : Integer; |
Data : Integer; |
||
end record;</ |
end record;</syntaxhighlight> |
||
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. |
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. |
||
Line 45: | Line 64: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{works with|ALGOL 68|Revision 1 |
{{works with|ALGOL 68|Revision 1.}} |
||
{{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'''<syntaxhighlight lang="algol68"># -*- coding: utf-8 -*- # |
|||
CO REQUIRES: |
|||
MODE OBJVALUE = ~ # Mode/type of actual obj to be queued # |
|||
END CO |
|||
MODE OBJLINK = STRUCT( |
|||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} |
|||
REF OBJLINK next, |
|||
{{wont work 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] - due to extensive use of '''format'''[ted] ''transput''}} |
|||
REF OBJLINK prev, |
|||
<lang algol68>MODE LINK = STRUCT ( |
|||
OBJVALUE value # ... etc. required # |
|||
REF LINK prev, |
|||
REF LINK next, |
|||
DATA value |
|||
); |
); |
||
PROC obj link new = REF OBJLINK: HEAP OBJLINK; |
|||
MODE DATA = STRUCT(INT year elected, STRING name); |
|||
PROC obj link free = (REF OBJLINK free)VOID: |
|||
LINK previous, incumbent, elect; |
|||
prev OF free := next OF free := obj queue empty # give the garbage collector a big hint #</syntaxhighlight>'''See also:''' [[Queue/Usage#ALGOL_68|Queue/Usage]] |
|||
previous := (NIL, incumbent, DATA(1993, "Clinton")); |
|||
incumbent:= (previous, elect,DATA(2001, "Bush" )); |
|||
elect := (incumbent, NIL, DATA(2008, "Obama" )); |
|||
=={{header|ALGOL W}}== |
|||
REF LINK node := previous; |
|||
<syntaxhighlight lang="algolw"> % record type to hold an element of a doubly linked list of integers % |
|||
WHILE REF LINK(node) ISNT NIL DO |
|||
record DListIElement ( reference(DListIElement) prev |
|||
printf(($dddd": "g"; "$,value OF node)); |
|||
; integer iValue |
|||
node := next OF node |
|||
; reference(DListIElement) next |
|||
OD; |
|||
); |
|||
print(new line); |
|||
% additional record types would be required for other element types %</syntaxhighlight> |
|||
=={{header|ARM Assembly}}== |
|||
node := elect; |
|||
{{works with|as|Raspberry Pi}} |
|||
WHILE REF LINK(node) ISNT NIL DO |
|||
<syntaxhighlight lang="arm assembly"> |
|||
printf(($dddd": "g"; "$,value OF node)); |
|||
node := prev OF node |
|||
/* ARM assembly Raspberry PI */ |
|||
OD; |
|||
print((newline))</lang> |
|||
/* structure Node Doublylinked List*/ |
|||
Output: |
|||
.struct 0 |
|||
<pre> |
|||
NDlist_next: @ next element |
|||
1993: Clinton; 2001: Bush; 2008: Obama; |
|||
.struct NDlist_next + 4 |
|||
2008: Obama; 2001: Bush; 1993: Clinton; |
|||
NDlist_prev: @ previous element |
|||
</pre> |
|||
.struct NDlist_prev + 4 |
|||
NDlist_value: @ element value or key |
|||
.struct NDlist_value + 4 |
|||
NDlist_fin: |
|||
</syntaxhighlight> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
see [[Doubly-linked list/AutoHotkey]] |
see [[Doubly-linked list/AutoHotkey]] |
||
=={{header| |
=={{header|Axe}}== |
||
<syntaxhighlight lang="axe">Lbl LINK |
|||
r₂→{r₁}ʳ |
|||
0→{r₁+2}ʳ |
|||
0→{r₁+4}ʳ |
|||
r₁ |
|||
Return |
|||
Lbl NEXT |
|||
{r₁+2}ʳ |
|||
Return |
|||
Lbl PREV |
|||
{r₁+4}ʳ |
|||
Return |
|||
Lbl VALUE |
|||
{r₁}ʳ |
|||
Return</syntaxhighlight> |
|||
=={{header|BASIC}}== |
|||
==={{header|BBC BASIC}}=== |
|||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM node{pPrev%, pNext%, iData%} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Bracmat}}== |
|||
<syntaxhighlight lang="bracmat">link=(prev=) (next=) (data=)</syntaxhighlight> |
|||
=={{header|C}}== |
=={{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. |
|||
<lang c>struct link { |
|||
<syntaxhighlight lang="c">struct Node |
|||
{ |
|||
struct link *prev; |
|||
struct Node *next; |
|||
int data; |
|||
struct Node *prev; |
|||
};</lang> |
|||
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#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">class Link |
||
{ |
{ |
||
public int |
public int Item { get; set; } |
||
public Link |
public Link Prev { get; set; } |
||
public Link |
public Link Next { get; set; } |
||
}</lang> |
|||
//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: |
|||
<syntaxhighlight lang="cpp">template <typename T> |
|||
struct Node |
|||
{ |
|||
Node* next; |
|||
Node* prev; |
|||
T data; |
|||
};</syntaxhighlight> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Line 108: | Line 189: | ||
This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better. |
This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better. |
||
< |
<syntaxhighlight lang="clojure">(defrecord Node [prev next data]) |
||
(defn new-node [prev next data] |
(defn new-node [prev next data] |
||
(Node. (ref prev) (ref next) data))</ |
(Node. (ref prev) (ref next) data))</syntaxhighlight> |
||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defstruct dlist head tail) |
||
(defstruct dlink content prev next)</ |
(defstruct dlink content prev next)</syntaxhighlight> |
||
See the functions on the [[Doubly-Linked List]] page for the usage of these structures. |
See the functions on the [[Doubly-Linked List]] page for the usage of these structures. |
||
Line 122: | Line 203: | ||
=={{header|D}}== |
=={{header|D}}== |
||
A default constructor is implicit: |
A default constructor is implicit: |
||
< |
<syntaxhighlight lang="d">struct Node(T) { |
||
T data; |
T data; |
||
typeof(this)* prev, next; |
|||
} |
|||
}</lang> |
|||
void main() { |
|||
alias N = Node!int; |
|||
N* n = new N(10); |
|||
}</syntaxhighlight> |
|||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
< |
<syntaxhighlight lang="d">struct Node(T) { |
||
type |
type |
||
Line 140: | Line 226: | ||
end; |
end; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|E}}== |
=={{header|E}}== |
||
Line 146: | Line 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). |
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). |
||
< |
<syntaxhighlight lang="e">def makeElement(var value, var next, var prev) { |
||
def element { |
def element { |
||
to setValue(v) { value := v } |
to setValue(v) { value := v } |
||
Line 159: | Line 245: | ||
return element |
return element |
||
}</ |
}</syntaxhighlight> |
||
=={{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}}== |
=={{header|Fortran}}== |
||
In ISO Fortran 95 or later: |
In ISO Fortran 95 or later: |
||
< |
<syntaxhighlight lang="fortran">type node |
||
real :: data |
real :: data |
||
type(node), pointer :: next => null(), previous => null() |
type(node), pointer :: next => null(), previous => null() |
||
Line 170: | Line 274: | ||
! . . . . |
! . . . . |
||
! |
! |
||
type( node ), target :: head</ |
type( node ), target :: head</syntaxhighlight> |
||
=={{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}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">type dlNode struct { |
||
string |
string |
||
next, prev * |
next, prev *dlNode |
||
}</ |
}</syntaxhighlight> |
||
Or, using the [http://golang.org/pkg/container/list/#Element container/list] package: |
|||
<syntaxhighlight lang="go">import "container/list" |
|||
var node list.Element |
|||
// and using: node.Next(), node.Prev(), node.Value</syntaxhighlight> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 182: | Line 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. |
Note that unlike naive pointer manipulation which could corrupt the doubly-linked list, updateLeft and updateRight will always yield a well-formed data structure. |
||
< |
<syntaxhighlight lang="haskell"> |
||
data DList a = Leaf | Node (DList a) a (DList a) |
data DList a = Leaf | Node (DList a) a (DList a) |
||
Line 196: | Line 314: | ||
where current = Node l v next |
where current = Node l v next |
||
next = updateRight nr new |
next = updateRight nr new |
||
</syntaxhighlight> |
|||
</lang> |
|||
==Icon and {{header|Unicon}}== |
==Icon and {{header|Unicon}}== |
||
Line 202: | Line 320: | ||
Uses Unicon classes. |
Uses Unicon classes. |
||
<syntaxhighlight lang="unicon"> |
|||
<lang Unicon> |
|||
class DoubleLink (value, prev_link, next_link) |
class DoubleLink (value, prev_link, next_link) |
||
initially (value, prev_link, next_link) |
initially (value, prev_link, next_link) |
||
Line 209: | Line 327: | ||
self.next_link := next_link |
self.next_link := next_link |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 219: | Line 337: | ||
Nevertheless, this is doable, though it necessarily departs from the definition specified at [[Doubly-linked_list/Definition#J]]. |
Nevertheless, this is doable, though it necessarily departs from the definition specified at [[Doubly-linked_list/Definition#J]]. |
||
< |
<syntaxhighlight lang="j">coclass'DoublyLinkedListElement' |
||
create=:3 :0 |
create=:3 :0 |
||
this=:coname'' |
this=:coname'' |
||
'predecessor successor data'=:y |
'predecessor successor data'=:y |
||
successor__predecessor=: predecessor__successor=: this |
successor__predecessor=: predecessor__successor=: this |
||
)</ |
)</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang="j">coclass'DoublyLinkedListHead' |
||
create=:3 :0 |
create=:3 :0 |
||
predecessor=:successor=:this=: coname'' |
predecessor=:successor=:this=: coname'' |
||
)</ |
)</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
< |
<syntaxhighlight lang="java">public class Node<T> { |
||
private T element; |
private T element; |
||
private Node<T> next, prev; |
private Node<T> next, prev; |
||
Line 276: | Line 394: | ||
return prev; |
return prev; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
For use with [[Java]] 1.4 and below, delete all "<T>"s and replace T's with "Object". |
For use with [[Java]] 1.4 and below, delete all "<T>"s and replace T's with "Object". |
||
Line 282: | Line 400: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Inherits from LinkedList (see [[Singly-Linked_List_(element)#JavaScript]]) |
Inherits from LinkedList (see [[Singly-Linked_List_(element)#JavaScript]]) |
||
< |
<syntaxhighlight lang="javascript">function DoublyLinkedList(value, next, prev) { |
||
this._value = value; |
this._value = value; |
||
this._next = next; |
this._next = next; |
||
Line 308: | Line 426: | ||
} |
} |
||
var head = createDoublyLinkedListFromArray([10,20,30,40]);</ |
var head = createDoublyLinkedListFromArray([10,20,30,40]);</syntaxhighlight> |
||
=={{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}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">TYPE |
||
Link = POINTER TO LinkRcd; |
Link = POINTER TO LinkRcd; |
||
LinkRcd = RECORD |
LinkRcd = RECORD |
||
Prev, Next: Link; |
Prev, Next: Link; |
||
Data: INTEGER |
Data: INTEGER |
||
END;</ |
END;</syntaxhighlight> |
||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">type |
|||
Node[T] = ref TNode[T] |
|||
TNode[T] = object |
|||
next, prev: Node[T] |
|||
data: T</syntaxhighlight> |
|||
=={{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}}== |
|||
<syntaxhighlight lang="objeck">class ListNode { |
|||
@value : Base; |
|||
@next : ListNode; |
|||
@previous: ListNode; |
|||
New(value : Base) { |
|||
@value := value; |
|||
} |
|||
method : public : Set(value : Base) ~ Nil { |
|||
@value := value; |
|||
} |
|||
method : public : Get() ~ Base { |
|||
return @value; |
|||
} |
|||
method : public : SetNext(next : Collection.ListNode) ~ Nil { |
|||
@next := next; |
|||
} |
|||
method : public : GetNext() ~ ListNode { |
|||
return @next; |
|||
} |
|||
method : public : SetPrevious(previous : Collection.ListNode) ~ Nil { |
|||
@previous := previous; |
|||
} |
|||
method : public : GetPrevious() ~ ListNode { |
|||
return @previous; |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
===Imperative=== |
===Imperative=== |
||
< |
<syntaxhighlight lang="ocaml">type 'a dlink = { |
||
mutable data: 'a; |
mutable data: 'a; |
||
mutable next: 'a dlink option; |
mutable next: 'a dlink option; |
||
Line 362: | Line 608: | ||
in |
in |
||
aux |
aux |
||
;;</ |
;;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ocaml"># let dl = dlink_of_list [1;2;3;4;5] in |
||
iter_forward_dlink (Printf.printf "%d\n") dl ;; |
iter_forward_dlink (Printf.printf "%d\n") dl ;; |
||
1 |
1 |
||
Line 371: | Line 617: | ||
4 |
4 |
||
5 |
5 |
||
- : unit = ()</ |
- : unit = ()</syntaxhighlight> |
||
===Functional=== |
===Functional=== |
||
Line 378: | Line 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: |
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: |
||
< |
<syntaxhighlight lang="ocaml">type 'a nav_list = 'a list * 'a * 'a list</syntaxhighlight> |
||
The middle element is the pointed item, and the two lists are the |
The middle element is the pointed item, and the two lists are the |
||
previous and the following items. |
previous and the following items. |
||
Here are the associated functions: |
Here are the associated functions: |
||
< |
<syntaxhighlight lang="ocaml">let nav_list_of_list = function |
||
| hd::tl -> [], hd, tl |
| hd::tl -> [], hd, tl |
||
| [] -> invalid_arg "empty list" |
| [] -> invalid_arg "empty list" |
||
Line 400: | Line 646: | ||
prev_tl, prev, item::next |
prev_tl, prev, item::next |
||
| _ -> |
| _ -> |
||
failwith "begin of nav_list reached"</ |
failwith "begin of nav_list reached"</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ocaml"># let nl = nav_list_of_list [1;2;3;4;5] ;; |
||
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5]) |
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5]) |
||
# let nl = next nl ;; |
# let nl = next nl ;; |
||
Line 409: | Line 655: | ||
# current nl ;; |
# current nl ;; |
||
- : int = 3</ |
- : int = 3</syntaxhighlight> |
||
=={{header|Oforth}}== |
|||
Complete definition is here : [[../Definition#Oforth]] |
|||
<syntaxhighlight lang="oforth">Object Class new: DNode(value, mutable prev, mutable next)</syntaxhighlight> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
We show how to create a new node as a record value. |
We show how to create a new node as a record value. |
||
< |
<syntaxhighlight lang="oz">fun {CreateNewNode Value} |
||
node(prev:{NewCell _} |
node(prev:{NewCell _} |
||
next:{NewCell _} |
next:{NewCell _} |
||
value:Value) |
value:Value) |
||
end</ |
end</syntaxhighlight> |
||
Note: this is for illustrative purposes only. In a real Oz program, you would use one of the existing data types. |
Note: this is for illustrative purposes only. In a real Oz program, you would use one of the existing data types. |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">type link_ptr = ^link; |
||
data_ptr = ^data; (* presumes that type 'data' is defined above *) |
data_ptr = ^data; (* presumes that type 'data' is defined above *) |
||
link = record |
link = record |
||
Line 428: | Line 680: | ||
next: link_ptr; |
next: link_ptr; |
||
data: data_ptr; |
data: data_ptr; |
||
end;</ |
end;</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">my %node = ( |
||
data => 'say what', |
data => 'say what', |
||
next => \%foo_node, |
next => \%foo_node, |
||
prev => \%bar_node, |
prev => \%bar_node, |
||
); |
); |
||
$node{next} = \%quux_node; # mutable</ |
$node{next} = \%quux_node; # mutable</syntaxhighlight> |
||
=={{header|Perl 6}}== |
|||
=={{header|Phix}}== |
|||
<lang perl6>role DLElem[::T] { |
|||
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use |
|||
has DLElem[T] $.prev is rw; |
|||
<!--<syntaxhighlight lang="phix">--> |
|||
has DLElem[T] $.next is rw; |
|||
<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> |
|||
has T $.payload = T; |
|||
<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. |
|||
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; |
|||
} |
|||
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. |
|||
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 |
|||
} |
|||
}</lang> |
|||
=={{header|PL/I}}== |
|||
<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. */ |
|||
</lang> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Line 503: | Line 718: | ||
With that, 'cddr' can be used to access the next, and 'cadr' to access the |
With that, 'cddr' can be used to access the next, and 'cadr' to access the |
||
previous element. |
previous element. |
||
<syntaxhighlight lang="picolisp">(de 2tail (X DLst) |
|||
<lang PicoLisp># 'cons' an element to a doubly-linked list |
|||
( |
(let L (cdr 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 |
(let L (car DLst) # Get current data list |
||
(set DLst (cons X NIL L)) # Prepend two new cons pairs |
(set DLst (cons X NIL L)) # Prepend two new cons pairs |
||
Line 512: | Line 733: | ||
# We prepend 'not' to the list in the previous example |
# We prepend 'not' to the list in the previous example |
||
( |
(2head 'not *DLst)</syntaxhighlight> |
||
For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]]. |
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}}== |
=={{header|Pop11}}== |
||
< |
<syntaxhighlight lang="pop11">uses objectclass; |
||
define :class Link; |
define :class Link; |
||
slot next = []; |
slot next = []; |
||
slot prev = []; |
slot prev = []; |
||
slot data = []; |
slot data = []; |
||
enddefine;</ |
enddefine;</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Structure node |
||
*prev.node |
*prev.node |
||
*next.node |
*next.node |
||
value.i |
value.i |
||
EndStructure</ |
EndStructure</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">class Node(object): |
||
def __init__(self, data = None, prev = None, next = None): |
def __init__(self, data = None, prev = None, next = None): |
||
self.prev = prev |
self.prev = prev |
||
Line 550: | Line 794: | ||
while c != None: |
while c != None: |
||
yield c |
yield c |
||
c = c.prev</ |
c = c.prev</syntaxhighlight> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
(define-struct dlist (head tail) #:mutable) |
(define-struct dlist (head tail) #:mutable) |
||
(define-struct dlink (content prev next) #:mutable) |
(define-struct dlink (content prev next) #:mutable) |
||
</syntaxhighlight> |
|||
</lang> |
|||
See the functions on the [[Doubly-Linked List]] page for the usage of these structures. |
See the functions on the [[Doubly-Linked List]] page for the usage of these structures. |
||
=={{header| |
=={{header|Raku}}== |
||
(formerly Perl 6) |
|||
REXX doesn't have linked lists, as there are no pointers (or handles). |
|||
<br> |
|||
However, linked lists can be simulated with lists in REXX. |
|||
<lang rexx>/*REXX program that implements various List Manager functions. */ |
|||
/*┌────────────────────────────────────────────────────────────────────┐ |
|||
┌─┘ Functions of the List Manager └─┐ |
|||
│ │ |
|||
│ @init ─── initializes the List. │ |
|||
│ │ |
|||
│ @size ─── returns the size of the List [could be 0 (zero)]. │ |
|||
│ │ |
|||
│ @show ─── shows (displays) the complete List. │ |
|||
│ @show k,1 ─── shows (displays) the Kth item. │ |
|||
│ @show k,m ─── shows (displays) M items, starting with Kth item. │ |
|||
│ @show ,,─1 ─── shows (displays) the complete List backwards. │ |
|||
│ │ |
|||
│ @get k ─── returns the Kth item. │ |
|||
│ @get k,m ─── returns the M items starting with the Kth item. │ |
|||
│ │ |
|||
│ @put x ─── adds the X items to the end (tail) of the List. │ |
|||
│ @put x,0 ─── adds the X items to the start (head) of the List. │ |
|||
│ @put x,k ─── adds the X items to before of the Kth item. │ |
|||
│ │ |
|||
│ @del k ─── deletes the item K. │ |
|||
│ @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' |
|||
call sy 'displaying list size.' ; say 'list size='@size() |
|||
call sy 'forward list' ; call @show |
|||
call sy 'backward list' ; call @show ,,-1 |
|||
call sy 'showing 4th item' ; call @show 4,1 |
|||
call sy 'showing 6th & 6th items' ; call @show 5,2 |
|||
call sy 'adding item before item 4: black' ; call @put 'black',4 |
|||
call sy 'showing list' ; call @show |
|||
call sy 'adding to tail: there, in the ...'; call @put 'there, in the shadows, stalking its prey (and next meal).' |
|||
call sy 'showing list' ; call @show |
|||
call sy 'adding to head: Oy!' ; call @put 'Oy!',0 |
|||
call sy 'showing list' ; call @show |
|||
exit /*stick a fork in it, we're done.*/ |
|||
/*──────────────────────────────────subroutines─────────────────────────*/ |
|||
p: return word(arg(1),1) |
|||
sy: say; say left('',30) "───" arg(1) '───'; return |
|||
@hasopt: arg o; return pos(o,opt)\==0 |
|||
@size: return $.# |
|||
@init: $.@=''; $.#=0; return 0 |
|||
@adjust: $.@=space($.@); $.#=words($.@); return 0 |
|||
<syntaxhighlight lang="raku" line>role DLElem[::T] { |
|||
@parms: arg opt |
|||
has DLElem[T] $.prev is rw; |
|||
if @hasopt('k') then k=min($.#+1,max(1,p(k 1))) |
|||
has DLElem[T] $.next is rw; |
|||
if @hasopt('m') then m=p(m 1) |
|||
has T $.payload = T; |
|||
if @hasopt('d') then dir=p(dir 1) |
|||
return |
|||
method pre-insert(T $payload) { |
|||
@show: procedure expose $.; parse arg k,m,dir |
|||
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) { |
|||
@get: procedure expose $.; arg k,m,dir,_ |
|||
die "Can't insert after end" unless $!next; |
|||
my $elem = ::?CLASS.new(:$payload); |
|||
do j=k for m by dir while j>0 & j<=$.# |
|||
$!next.prev = $elem; |
|||
_=_ subword($.@,j,1) |
|||
$elem.next = $!next; |
|||
end /*j*/ |
|||
$elem.prev = self; |
|||
$!next = $elem; |
|||
$elem; |
|||
} |
|||
method delete { |
|||
@put: procedure expose $.; parse arg x,k |
|||
die "Can't delete a sentinel" unless $!prev and $!next; |
|||
k=p(k $.#+1) |
|||
$!next.prev = $!prev; |
|||
$!prev.next = $!next; # conveniently returns next element |
|||
$.@=subword($.@,1,max(0,k-1)) x subword($.@,k) |
|||
} |
|||
call @adjust |
|||
}</syntaxhighlight> |
|||
return 0 |
|||
=={{header|REXX}}== |
|||
@del: procedure expose $.; arg k,m |
|||
REXX doesn't have linked lists, as there are no pointers (or handles). |
|||
call @parms 'km' |
|||
<br>However, linked lists can be simulated with lists in REXX. |
|||
_=subword($.@,k,k-1) subword($.@,k+m) |
|||
$.@=_ |
|||
╔═════════════════════════════════════════════════════════════════════════╗ |
|||
call @adjust |
|||
║ ☼☼☼☼☼☼☼☼☼☼☼ Functions of the List Manager ☼☼☼☼☼☼☼☼☼☼☼ ║ |
|||
return</lang> |
|||
║ @init ─── initializes the List. ║ |
|||
║ ║ |
|||
║ @size ─── returns the size of the List [could be a 0 (zero)]. ║ |
|||
║ ║ |
|||
║ @show ─── shows (displays) the complete List. ║ |
|||
║ @show k,1 ─── shows (displays) the Kth item. ║ |
|||
║ @show k,m ─── shows (displays) M items, starting with Kth item. ║ |
|||
║ @show ,,─1 ─── shows (displays) the complete List backwards. ║ |
|||
║ ║ |
|||
║ @get k ─── returns the Kth item. ║ |
|||
║ @get k,m ─── returns the M items starting with the Kth item. ║ |
|||
║ ║ |
|||
║ @put x ─── adds the X items to the end (tail) of the List. ║ |
|||
║ @put x,0 ─── adds the X items to the start (head) of the List. ║ |
|||
║ @put x,k ─── adds the X items to before of the Kth item. ║ |
|||
║ ║ |
|||
║ @del k ─── deletes the item K. ║ |
|||
║ @del k,m ─── deletes the M items starting with item K. ║ |
|||
╚═════════════════════════════════════════════════════════════════════════╝ |
|||
<syntaxhighlight lang="rexx">/*REXX program implements various List Manager functions (see the documentation above).*/ |
|||
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" |
|||
call sy 'displaying list size.' ; say "list size="@size() |
|||
call sy 'forward list' ; call @show |
|||
call sy 'backward list' ; call @show ,,-1 |
|||
call sy 'showing 4th item' ; call @show 4,1 |
|||
call sy 'showing 5th & 6th items' ; call @show 5,2 |
|||
call sy 'adding item before item 4: black' ; call @put "black",4 |
|||
call sy 'showing list' ; call @show |
|||
call sy 'adding to tail: there, in the ...' ; call @put "there, in the shadows, stalking its prey (and next meal)." |
|||
call sy 'showing list' ; call @show |
|||
call sy 'adding to head: Oy!' ; call @put "Oy!",0 |
|||
call sy 'showing list' ; call @show |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
p: return word(arg(1), 1) /*pick the first word out of many items*/ |
|||
sy: say; say left('', 30) "───" arg(1) '───'; return |
|||
@init: $.@=; @adjust: $.@=space($.@); $.#=words($.@); return |
|||
@hasopt: arg o; return pos(o, opt)\==0 |
|||
@size: return $.# |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@del: procedure expose $.; arg k,m; call @parms 'km' |
|||
_=subword($.@, k, k-1) subword($.@, k+m) |
|||
$.@=_; call @adjust; return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@get: procedure expose $.; arg k,m,dir,_ |
|||
call @parms 'kmd' |
|||
do j=k for m by dir while j>0 & j<=$.# |
|||
_=_ subword($.@, j, 1) |
|||
end /*j*/ |
|||
return strip(_) |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@parms: arg opt /*define a variable based on an option.*/ |
|||
if @hasopt('k') then k=min($.#+1, max(1, p(k 1))) |
|||
if @hasopt('m') then m=p(m 1) |
|||
if @hasopt('d') then dir=p(dir 1); return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@put: procedure expose $.; parse arg x,k; k=p(k $.#+1); call @parms 'k' |
|||
$.@=subword($.@, 1, max(0, k-1)) x subword($.@, k); call @adjust |
|||
return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
@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</syntaxhighlight> |
|||
'''output''' |
'''output''' |
||
<pre> |
|||
<pre style="height:30ex;overflow:scroll"> |
|||
─── initializing the list. ─── |
─── initializing the list. ─── |
||
Line 683: | Line 948: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Extending [[Singly-Linked List (element)#Ruby]] |
Extending [[Singly-Linked List (element)#Ruby]] |
||
< |
<syntaxhighlight lang="ruby">class DListNode < ListNode |
||
attr_accessor :prev |
attr_accessor :prev |
||
# accessors :succ and :value are inherited |
# accessors :succ and :value are inherited |
||
Line 702: | Line 967: | ||
end |
end |
||
list = DListNode.from_values 1,2,3,4</ |
list = DListNode.from_values 1,2,3,4</syntaxhighlight> |
||
=={{header|Rust}}== |
|||
=== Simply using the standard library === |
|||
<syntaxhighlight lang="rust">use std::collections::LinkedList; |
|||
fn main() { |
|||
// Doubly linked list containing 32-bit integers |
|||
let list = LinkedList::<i32>::new(); |
|||
}</syntaxhighlight> |
|||
=== 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="rust">pub struct LinkedList<T> { |
|||
head: Option<Shared<Node<T>>>, |
|||
tail: Option<Shared<Node<T>>>, |
|||
len: usize, |
|||
marker: PhantomData<Box<Node<T>>>, // Indicates that we logically own a boxed (owned pointer) Node<T>> |
|||
} |
|||
struct Node<T> { |
|||
next: Option<Shared<Node<T>>>, |
|||
prev: Option<Shared<Node<T>>>, |
|||
element: T, |
|||
}</syntaxhighlight> |
|||
=={{header|Sidef}}== |
|||
<syntaxhighlight lang="ruby">var node = Hash.new( |
|||
data => 'say what', |
|||
next => foo_node, |
|||
prev => bar_node, |
|||
); |
|||
node{:next} = quux_node; # mutable</syntaxhighlight> |
|||
=={{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}}== |
=={{header|Tcl}}== |
||
{{eff note|Tcl|list}} |
{{eff note|Tcl|list}} |
||
{{works with|Tcl|8.6}} or {{libheader|TclOO}} |
{{works with|Tcl|8.6}} or {{libheader|TclOO}} |
||
< |
<syntaxhighlight lang="tcl">oo::class create List { |
||
variable content next prev |
variable content next prev |
||
constructor {value {list ""}} { |
constructor {value {list ""}} { |
||
Line 726: | Line 1,045: | ||
set prev {*}$args |
set prev {*}$args |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
< |
<syntaxhighlight lang="vbnet">Public Class Node(Of T) |
||
Public Value As T |
Public Value As T |
||
Public [Next] As Node(Of T) |
Public [Next] As Node(Of T) |
||
Public Previous As Node(Of T) |
Public Previous As Node(Of T) |
||
End Class</ |
End Class</syntaxhighlight> |
||
=={{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}}== |
|||
<syntaxhighlight lang="zkl">class Node{ |
|||
fcn init(_value,_prev=Void,_next=Void) |
|||
{ var value=_value, prev=_prev, next=_next; } |
|||
fcn toString{ value.toString() } |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">a,b:=Node(1),Node("three"); |
|||
a.next=b; b.prev=a; |
|||
println(a.next," ",b.prev);</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
three 1 |
|||
</pre> |
|||
{{omit from|ACL2}} |
{{omit from|ACL2}} |
Latest revision as of 11:59, 28 November 2023
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Define the data structure for a doubly-linked list element.
The element should include a data member to hold its value and pointers to both the next element in the list and the previous element in the list.
The pointers should be mutable.
- See also
- Array
- Associative array: Creation, Iteration
- Collections
- Compound data type
- Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
- Linked list
- Queue: Definition, Usage
- Set
- Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
- Stack
Action!
DEFINE PTR="CARD"
TYPE ListNode=[
BYTE data
PTR prv,nxt]
- Output:
Screenshot from Atari 8-bit computer
Ada
type Link;
type Link_Access is access Link;
type Link is record
Next : Link_Access := null;
Prev : Link_Access := null;
Data : Integer;
end record;
Using generics, the specification might look like this:
generic
type Element_Type is private;
package Linked_List is
type List_Type is limited private;
...
private
type List_Element;
type List_Element_Ptr is access list_element;
type List_Element is
record
Prev : List_Element_Ptr;
Data : Element_Type;
Next : List_Element_Ptr;
end record;
type List_Type is
record
Head : List_Element_Ptr; -- Pointer to first element.
Tail : List_Element_Ptr; -- Pointer to last element.
Cursor : List_Element_Ptr; -- Pointer to cursor element.
Count : Natural := 0; -- Number of items in list.
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:
type Link is limited record
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.
ALGOL 68
File: prelude/link.a68
# -*- coding: utf-8 -*- #
CO REQUIRES:
MODE OBJVALUE = ~ # Mode/type of actual obj to be queued #
END CO
MODE OBJLINK = STRUCT(
REF OBJLINK next,
REF OBJLINK prev,
OBJVALUE value # ... etc. required #
);
PROC obj link new = REF OBJLINK: HEAP OBJLINK;
PROC obj link free = (REF OBJLINK free)VOID:
prev OF free := next OF free := obj queue empty # give the garbage collector a big hint #
See also: Queue/Usage
ALGOL W
% 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 %
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:
AutoHotkey
see Doubly-linked list/AutoHotkey
Axe
Lbl LINK
r₂→{r₁}ʳ
0→{r₁+2}ʳ
0→{r₁+4}ʳ
r₁
Return
Lbl NEXT
{r₁+2}ʳ
Return
Lbl PREV
{r₁+4}ʳ
Return
Lbl VALUE
{r₁}ʳ
Return
BASIC
BBC BASIC
DIM node{pPrev%, pNext%, iData%}
Bracmat
link=(prev=) (next=) (data=)
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.
struct Node
{
struct Node *next;
struct Node *prev;
void *data;
};
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.
struct Node;
typedef struct Node* Node;
struct Node
{
Node next;
Node prev;
void* data;
};
C#
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;
}
}
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:
template <typename T>
struct Node
{
Node* next;
Node* prev;
T data;
};
Clojure
This sort of mutable structure is not idiomatic in Clojure. Doubly-linked list/Definition#Clojure or a finger tree implementation would be better.
(defrecord Node [prev next data])
(defn new-node [prev next data]
(Node. (ref prev) (ref next) data))
Common Lisp
(defstruct dlist head tail)
(defstruct dlink content prev next)
See the functions on the Doubly-Linked List page for the usage of these structures.
D
A default constructor is implicit:
struct Node(T) {
T data;
typeof(this)* prev, next;
}
void main() {
alias N = Node!int;
N* n = new N(10);
}
Delphi
struct Node(T) {
type
pList = ^List ;
list = record
data : pointer ;
prev : pList ;
next : pList ;
end;
}
E
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 element.getNext().getPrev() == element
. See Doubly-Linked List#E for an actual implementation (which uses slightly more elaborate nodes than this).
def makeElement(var value, var next, var prev) {
def element {
to setValue(v) { value := v }
to getValue() { return value }
to setNext(n) { next := n }
to getNext() { return next }
to setPrev(p) { prev := p }
to getPrev() { return prev }
}
return element
}
Erlang
Using the code in Doubly-linked_list/Definition the element is defined by:
new( Data ) -> erlang:spawn( fun() -> loop( Data, noprevious, nonext ) end ).
F#
type 'a DLElm = {
mutable prev: 'a DLElm option
data: 'a
mutable next: 'a DLElm option
}
Factor
TUPLE: node data next prev ;
Fortran
In ISO Fortran 95 or later:
type node
real :: data
type(node), pointer :: next => null(), previous => null()
end type node
!
! . . . .
!
type( node ), target :: head
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
Go
type dlNode struct {
string
next, prev *dlNode
}
Or, using the container/list package:
import "container/list"
var node list.Element
// and using: node.Next(), node.Prev(), node.Value
Haskell
Haskell in general doesn't have mutability so the following 'mutator' functions use lazy evaluation instead.
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)
updateLeft _ Leaf = Leaf
updateLeft Leaf (Node _ v r) = Node Leaf v r
updateLeft new@(Node nl _ _) (Node _ v r) = current
where current = Node prev v r
prev = updateLeft nl new
updateRight _ Leaf = Leaf
updateRight Leaf (Node l v _) = Node l v Leaf
updateRight new@(Node _ _ nr) (Node l v _) = current
where current = Node l v next
next = updateRight nr new
Icon and Unicon
Uses Unicon classes.
class DoubleLink (value, prev_link, next_link)
initially (value, prev_link, next_link)
self.value := value
self.prev_link := prev_link # links are 'null' if not given
self.next_link := next_link
end
J
As discussed in Doubly-linked_list/Definition#J, doubly linked lists are antithetical to J's design. Defining individual elements as independent structures is even worse. Now each element of the list must contain three arrays (everything in J is an array), all so that we can implement a list.
Yo Dawg, we heard you like lists, so we put lists in your lists so you can list while you list.
Nevertheless, this is doable, though it necessarily departs from the definition specified at Doubly-linked_list/Definition#J.
coclass'DoublyLinkedListElement'
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:
coclass'DoublyLinkedListHead'
create=:3 :0
predecessor=:successor=:this=: coname''
)
Java
public class Node<T> {
private T element;
private Node<T> next, prev;
public Node<T>(){
next = prev = element = null;
}
public Node<T>(Node<T> n, Node<T> p, T elem){
next = n;
prev = p;
element = elem;
}
public void setNext(Node<T> n){
next = n;
}
public Node<T> getNext(){
return next;
}
public void setElem(T elem){
element = elem;
}
public T getElem(){
return element;
}
public void setNext(Node<T> n){
next = n;
}
public Node<T> setPrev(Node<T> p){
prev = p;
}
public getPrev(){
return prev;
}
}
For use with Java 1.4 and below, delete all "<T>"s and replace T's with "Object".
JavaScript
Inherits from LinkedList (see Singly-Linked_List_(element)#JavaScript)
function DoublyLinkedList(value, next, prev) {
this._value = value;
this._next = next;
this._prev = prev;
}
// from LinkedList, inherit: value(), next(), traverse(), print()
DoublyLinkedList.prototype = new LinkedList();
DoublyLinkedList.prototype.prev = function() {
if (arguments.length == 1)
this._prev = arguments[0];
else
return this._prev;
}
function createDoublyLinkedListFromArray(ary) {
var node, prev, head = new DoublyLinkedList(ary[0], null, null);
prev = head;
for (var i = 1; i < ary.length; i++) {
node = new DoublyLinkedList(ary[i], null, prev);
prev.next(node);
prev = node;
}
return head;
}
var head = createDoublyLinkedListFromArray([10,20,30,40]);
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
Kotlin
// 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)
}
- Output:
1 -> 2 -> 3 2 -> 3 3
Lang
&Node = {
$next
$prev
$data
}
Lua
see Doubly-linked_list/Definition#Lua, essentially:
local node = { data=data, prev=nil, next=nil }
Mathematica/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:
CreateDataStructure["DoublyLinkedList"]
Modula-2
TYPE
Link = POINTER TO LinkRcd;
LinkRcd = RECORD
Prev, Next: Link;
Data: INTEGER
END;
Nim
type
Node[T] = ref TNode[T]
TNode[T] = object
next, prev: Node[T]
data: T
Oberon-2
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.
Objeck
class ListNode {
@value : Base;
@next : ListNode;
@previous: ListNode;
New(value : Base) {
@value := value;
}
method : public : Set(value : Base) ~ Nil {
@value := value;
}
method : public : Get() ~ Base {
return @value;
}
method : public : SetNext(next : Collection.ListNode) ~ Nil {
@next := next;
}
method : public : GetNext() ~ ListNode {
return @next;
}
method : public : SetPrevious(previous : Collection.ListNode) ~ Nil {
@previous := previous;
}
method : public : GetPrevious() ~ ListNode {
return @previous;
}
}
OCaml
Imperative
type 'a dlink = {
mutable data: 'a;
mutable next: 'a dlink option;
mutable prev: 'a dlink option;
}
let dlink_of_list li =
let f prev_dlink x =
let dlink = {
data = x;
prev = None;
next = prev_dlink }
in
begin match prev_dlink with
| None -> ()
| Some prev_dlink ->
prev_dlink.prev <- Some dlink
end;
Some dlink
in
List.fold_left f None (List.rev li)
;;
let list_of_dlink =
let rec aux acc = function
| None -> List.rev acc
| Some{ data = d;
prev = _;
next = next } -> aux (d::acc) next
in
aux []
;;
let iter_forward_dlink f =
let rec aux = function
| None -> ()
| Some{ data = d;
prev = _;
next = next } -> f d; aux next
in
aux
;;
# let dl = dlink_of_list [1;2;3;4;5] in
iter_forward_dlink (Printf.printf "%d\n") dl ;;
1
2
3
4
5
- : unit = ()
Functional
The previous implementation is the strict equivalent of the other 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:
type 'a nav_list = 'a list * 'a * 'a list
The middle element is the pointed item, and the two lists are the previous and the following items. Here are the associated functions:
let nav_list_of_list = function
| hd::tl -> [], hd, tl
| [] -> invalid_arg "empty list"
let current = function
| _, item, _ -> item
let next = function
| prev, item, next::next_tl ->
item::prev, next, next_tl
| _ ->
failwith "end of nav_list reached"
let prev = function
| prev::prev_tl, item, next ->
prev_tl, prev, item::next
| _ ->
failwith "begin of nav_list reached"
# let nl = nav_list_of_list [1;2;3;4;5] ;;
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([1], 2, [3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([2; 1], 3, [4; 5])
# current nl ;;
- : int = 3
Oforth
Complete definition is here : Doubly-linked list/Definition#Oforth
Object Class new: DNode(value, mutable prev, mutable next)
Oz
We show how to create a new node as a record value.
fun {CreateNewNode 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.
Pascal
type link_ptr = ^link;
data_ptr = ^data; (* presumes that type 'data' is defined above *)
link = record
prev: link_ptr;
next: link_ptr;
data: data_ptr;
end;
Perl
my %node = (
data => 'say what',
next => \%foo_node,
prev => \%bar_node,
);
$node{next} = \%quux_node; # mutable
Phix
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use
enum NEXT,PREV,DATA type slnode(object x) return (sequence(x) and length(x)=DATA and <i>udt</i>(x[DATA]) and integer(x[NEXT] and integer(x[PREV])) end type
But more often you would just use the builtin sequences. See also 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.
PicoLisp
We use (in addition to the header structure described in Doubly-linked list/Definition#PicoLisp) two cells per doubly-linked list element:
+-----+-----+ +-----+-----+ | Val | ---+---> | | | ---+---> next +-----+-----+ +--+--+-----+ | prev <---+
With that, 'cddr' can be used to access the next, and 'cadr' to access the previous element.
(de 2tail (X DLst)
(let L (cdr 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
(if L # Unless DLst was empty
(set (cdr L) (car DLst)) # set new 'prev' link
(con DLst (car DLst)) ) ) ) # otherwise set 'end' link
# We prepend 'not' to the list in the previous example
(2head 'not *DLst)
For output of the example data, see Doubly-linked list/Traversal#PicoLisp.
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. */
Plain English
When you define a thing
, you are defining a record as a doubly-linked list element. next
and previous
fields are implicitly added to the record that can be used to build and traverse a list.
An element is a thing with a number.
Pop11
uses objectclass;
define :class Link;
slot next = [];
slot prev = [];
slot data = [];
enddefine;
PureBasic
Structure node
*prev.node
*next.node
value.i
EndStructure
Python
class Node(object):
def __init__(self, data = None, prev = None, next = None):
self.prev = prev
self.next = next
self.data = data
def __str__(self):
return str(self.data)
def __repr__(self):
return repr(self.data)
def iter_forward(self):
c = self
while c != None:
yield c
c = c.next
def iter_backward(self):
c = self
while c != None:
yield c
c = c.prev
Racket
(define-struct dlist (head tail) #:mutable)
(define-struct dlink (content prev next) #:mutable)
See the functions on the Doubly-Linked List page for the usage of these structures.
Raku
(formerly Perl 6)
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
}
}
REXX
REXX doesn't have linked lists, as there are no pointers (or handles).
However, linked lists can be simulated with lists in REXX.
╔═════════════════════════════════════════════════════════════════════════╗ ║ ☼☼☼☼☼☼☼☼☼☼☼ Functions of the List Manager ☼☼☼☼☼☼☼☼☼☼☼ ║ ║ @init ─── initializes the List. ║ ║ ║ ║ @size ─── returns the size of the List [could be a 0 (zero)]. ║ ║ ║ ║ @show ─── shows (displays) the complete List. ║ ║ @show k,1 ─── shows (displays) the Kth item. ║ ║ @show k,m ─── shows (displays) M items, starting with Kth item. ║ ║ @show ,,─1 ─── shows (displays) the complete List backwards. ║ ║ ║ ║ @get k ─── returns the Kth item. ║ ║ @get k,m ─── returns the M items starting with the Kth item. ║ ║ ║ ║ @put x ─── adds the X items to the end (tail) of the List. ║ ║ @put x,0 ─── adds the X items to the start (head) of the List. ║ ║ @put x,k ─── adds the X items to before of the Kth item. ║ ║ ║ ║ @del k ─── deletes the item K. ║ ║ @del k,m ─── deletes the M items starting with item K. ║ ╚═════════════════════════════════════════════════════════════════════════╝
/*REXX program implements various List Manager functions (see the documentation above).*/
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"
call sy 'displaying list size.' ; say "list size="@size()
call sy 'forward list' ; call @show
call sy 'backward list' ; call @show ,,-1
call sy 'showing 4th item' ; call @show 4,1
call sy 'showing 5th & 6th items' ; call @show 5,2
call sy 'adding item before item 4: black' ; call @put "black",4
call sy 'showing list' ; call @show
call sy 'adding to tail: there, in the ...' ; call @put "there, in the shadows, stalking its prey (and next meal)."
call sy 'showing list' ; call @show
call sy 'adding to head: Oy!' ; call @put "Oy!",0
call sy 'showing list' ; call @show
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
p: return word(arg(1), 1) /*pick the first word out of many items*/
sy: say; say left('', 30) "───" arg(1) '───'; return
@init: $.@=; @adjust: $.@=space($.@); $.#=words($.@); return
@hasopt: arg o; return pos(o, opt)\==0
@size: return $.#
/*──────────────────────────────────────────────────────────────────────────────────────*/
@del: procedure expose $.; arg k,m; call @parms 'km'
_=subword($.@, k, k-1) subword($.@, k+m)
$.@=_; call @adjust; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
@get: procedure expose $.; arg k,m,dir,_
call @parms 'kmd'
do j=k for m by dir while j>0 & j<=$.#
_=_ subword($.@, j, 1)
end /*j*/
return strip(_)
/*──────────────────────────────────────────────────────────────────────────────────────*/
@parms: arg opt /*define a variable based on an option.*/
if @hasopt('k') then k=min($.#+1, max(1, p(k 1)))
if @hasopt('m') then m=p(m 1)
if @hasopt('d') then dir=p(dir 1); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
@put: procedure expose $.; parse arg x,k; k=p(k $.#+1); call @parms 'k'
$.@=subword($.@, 1, max(0, k-1)) x subword($.@, k); call @adjust
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
@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
─── initializing the list. ─── ─── building list: Was it a cat I saw ─── ─── displaying list size. ─── list size=6 ─── forward list ─── Was it a cat I saw ─── backward list ─── saw I cat a it Was ─── showing 4th item ─── cat ─── showing 6th & 6th items ─── I saw ─── adding item before item 4: black ─── ─── showing list ─── Was it a black cat I saw ─── adding to tail: there, in the ... ─── ─── showing list ─── Was it a black cat I saw there, in the shadows, stalking its prey (and next meal). ─── adding to head: Oy! ─── ─── showing list ─── Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).
Ruby
Extending Singly-Linked List (element)#Ruby
class DListNode < ListNode
attr_accessor :prev
# accessors :succ and :value are inherited
def initialize(value, prev=nil, succ=nil)
@value = value
@prev = prev
@prev.succ = self if prev
@succ = succ
@succ.prev = self if succ
end
def self.from_values(*ary)
ary << (f = ary.pop)
ary.map! {|i| new i }
ary.inject(f) {|p, c| p.succ = c; c.prev = p; c }
end
end
list = DListNode.from_values 1,2,3,4
Rust
Simply using the standard library
use std::collections::LinkedList;
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 std
implementation (Documentation 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 T
(meaning that an &Shared<&'static T>
may be used where a &Shared<&'a T>
is expected, indicates to the compiler that it may own a T
) and may be dereferenced to a mutable pointer (*mut T
). 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.
pub struct LinkedList<T> {
head: Option<Shared<Node<T>>>,
tail: Option<Shared<Node<T>>>,
len: usize,
marker: PhantomData<Box<Node<T>>>, // Indicates that we logically own a boxed (owned pointer) Node<T>>
}
struct Node<T> {
next: Option<Shared<Node<T>>>,
prev: Option<Shared<Node<T>>>,
element: T,
}
Sidef
var node = Hash.new(
data => 'say what',
next => foo_node,
prev => bar_node,
);
node{:next} = quux_node; # mutable
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
}
}
Tcl
or
oo::class create List {
variable content next prev
constructor {value {list ""}} {
set content $value
set next $list
set prev ""
if {$next ne ""} {
$next previous [self]
}
}
method value args {
set content {*}$args
}
method next args {
set next {*}$args
}
method previous args {
set prev {*}$args
}
}
Visual Basic .NET
Public Class Node(Of T)
Public Value As T
Public [Next] As Node(Of T)
Public Previous As Node(Of T)
End Class
Wren
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.
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)"])
- Output:
[node 1, data = 1, prev = null, next = 2] [node 2, data = 2, prev = 1, next = null]
XPL0
def \Node\ Prev, Data, Next; \Element (Node) definition
zkl
class Node{
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
fcn toString{ value.toString() }
}
a,b:=Node(1),Node("three");
a.next=b; b.prev=a;
println(a.next," ",b.prev);
- Output:
three 1
- Programming Tasks
- Data Structures
- Action!
- Ada
- ALGOL 68
- ALGOL W
- ARM Assembly
- AutoHotkey
- Axe
- BASIC
- BBC BASIC
- Bracmat
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Delphi
- E
- Erlang
- F Sharp
- Factor
- Fortran
- FreeBASIC
- Go
- Haskell
- Unicon
- J
- Java
- JavaScript
- Julia
- Kotlin
- Lang
- Lua
- Mathematica
- Wolfram Language
- Modula-2
- Nim
- Oberon-2
- Objeck
- OCaml
- Oforth
- Oz
- Pascal
- Perl
- Phix
- PicoLisp
- PL/I
- Plain English
- Pop11
- PureBasic
- Python
- Racket
- Raku
- REXX
- Ruby
- Rust
- Sidef
- Swift
- Tcl
- TclOO
- Visual Basic .NET
- Wren
- Wren-llist
- XPL0
- Zkl
- ACL2/Omit
- TI-83 BASIC/Omit
- TI-89 BASIC/Omit