Doubly-linked list/Element definition: Difference between revisions
Content added Content deleted
m (→{{header|F Sharp|F#}}: fix heading, as suggested on the Count examples/Full list/Tier 4 talk page) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 13: | Line 13: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">DEFINE PTR="CARD" |
||
TYPE ListNode=[ |
TYPE ListNode=[ |
||
BYTE data |
BYTE data |
||
PTR prv,nxt]</ |
PTR prv,nxt]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_element_definition.png Screenshot from Atari 8-bit computer] |
[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 28: | 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 52: | 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 67: | Line 67: | ||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.7 algol68g-2.7].}} |
{{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]}} |
{{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'''< |
'''File: prelude/link.a68'''<syntaxhighlight lang="algol68"># -*- coding: utf-8 -*- # |
||
CO REQUIRES: |
CO REQUIRES: |
||
MODE OBJVALUE = ~ # Mode/type of actual obj to be queued # |
MODE OBJVALUE = ~ # Mode/type of actual obj to be queued # |
||
Line 81: | Line 81: | ||
PROC obj link free = (REF OBJLINK free)VOID: |
PROC obj link free = (REF OBJLINK free)VOID: |
||
prev OF free := next OF free := obj queue empty # give the garbage collector a big hint #</ |
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]] |
||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw"> % record type to hold an element of a doubly linked list of integers % |
||
record DListIElement ( reference(DListIElement) prev |
record DListIElement ( reference(DListIElement) prev |
||
; integer iValue |
; integer iValue |
||
; reference(DListIElement) next |
; reference(DListIElement) next |
||
); |
); |
||
% additional record types would be required for other element types %</ |
% additional record types would be required for other element types %</syntaxhighlight> |
||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
<syntaxhighlight lang="arm assembly"> |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
Line 106: | Line 106: | ||
.struct NDlist_value + 4 |
.struct NDlist_value + 4 |
||
NDlist_fin: |
NDlist_fin: |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
Line 112: | Line 112: | ||
=={{header|Axe}}== |
=={{header|Axe}}== |
||
< |
<syntaxhighlight lang="axe">Lbl LINK |
||
r₂→{r₁}ʳ |
r₂→{r₁}ʳ |
||
0→{r₁+2}ʳ |
0→{r₁+2}ʳ |
||
Line 129: | Line 129: | ||
Lbl VALUE |
Lbl VALUE |
||
{r₁}ʳ |
{r₁}ʳ |
||
Return</ |
Return</syntaxhighlight> |
||
=={{header|BBC 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}}== |
=={{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. |
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 Node *next; |
struct Node *next; |
||
struct Node *prev; |
struct Node *prev; |
||
void *data; |
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. |
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"> |
|||
<lang c> |
|||
struct Node; |
struct Node; |
||
typedef struct Node* Node; |
typedef struct Node* Node; |
||
Line 157: | Line 157: | ||
void* data; |
void* data; |
||
}; |
}; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">class Link |
||
{ |
{ |
||
public int Item { get; set; } |
public int Item { get; set; } |
||
Line 172: | Line 172: | ||
Next = next; |
Next = next; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{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: |
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 |
struct Node |
||
{ |
{ |
||
Line 182: | Line 182: | ||
Node* prev; |
Node* prev; |
||
T data; |
T data; |
||
};</ |
};</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Line 188: | Line 188: | ||
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 202: | Line 202: | ||
=={{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; |
typeof(this)* prev, next; |
||
Line 210: | Line 210: | ||
alias N = Node!int; |
alias N = Node!int; |
||
N* n = new N(10); |
N* n = new N(10); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
< |
<syntaxhighlight lang="d">struct Node(T) { |
||
type |
type |
||
Line 225: | Line 225: | ||
end; |
end; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|E}}== |
=={{header|E}}== |
||
Line 231: | Line 231: | ||
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 244: | Line 244: | ||
return element |
return element |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Using the code in [[Doubly-linked_list/Definition]] the element is defined by: |
Using the code in [[Doubly-linked_list/Definition]] the element is defined by: |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
new( Data ) -> erlang:spawn( fun() -> loop( Data, noprevious, nonext ) end ). |
new( Data ) -> erlang:spawn( fun() -> loop( Data, noprevious, nonext ) end ). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
type 'a DLElm = { |
type 'a DLElm = { |
||
mutable prev: 'a DLElm option |
mutable prev: 'a DLElm option |
||
Line 259: | Line 259: | ||
mutable next: 'a DLElm option |
mutable next: 'a DLElm option |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{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 273: | Line 273: | ||
! . . . . |
! . . . . |
||
! |
! |
||
type( node ), target :: head</ |
type( node ), target :: head</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">type node |
||
nxt as node ptr |
nxt as node ptr |
||
prv as node ptr |
prv as node ptr |
||
dat as any ptr 'points to any kind of data; user's responsibility |
dat as any ptr 'points to any kind of data; user's responsibility |
||
'to keep track of what's actually in it |
'to keep track of what's actually in it |
||
end type</ |
end type</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">type dlNode struct { |
||
string |
string |
||
next, prev *dlNode |
next, prev *dlNode |
||
}</ |
}</syntaxhighlight> |
||
Or, using the [http://golang.org/pkg/container/list/#Element container/list] package: |
Or, using the [http://golang.org/pkg/container/list/#Element container/list] package: |
||
< |
<syntaxhighlight lang="go">import "container/list" |
||
var node list.Element |
var node list.Element |
||
// and using: node.Next(), node.Prev(), node.Value</ |
// and using: node.Next(), node.Prev(), node.Value</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 299: | Line 299: | ||
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 313: | Line 313: | ||
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 319: | Line 319: | ||
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 326: | Line 326: | ||
self.next_link := next_link |
self.next_link := next_link |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 336: | Line 336: | ||
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 393: | Line 393: | ||
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 399: | Line 399: | ||
=={{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 425: | Line 425: | ||
} |
} |
||
var head = createDoublyLinkedListFromArray([10,20,30,40]);</ |
var head = createDoublyLinkedListFromArray([10,20,30,40]);</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">abstract type AbstractNode{T} end |
||
struct EmptyNode{T} <: AbstractNode{T} end |
struct EmptyNode{T} <: AbstractNode{T} end |
||
Line 437: | Line 437: | ||
pred::AbstractNode{T} |
pred::AbstractNode{T} |
||
succ::AbstractNode{T} |
succ::AbstractNode{T} |
||
end</ |
end</syntaxhighlight> |
||
=={{header|Kotlin}}== |
=={{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) { |
class Node<T: Number>(var data: T, var prev: Node<T>? = null, var next: Node<T>? = null) { |
||
Line 463: | Line 463: | ||
println(n2) |
println(n2) |
||
println(n3) |
println(n3) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 474: | Line 474: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
see [[Doubly-linked_list/Definition#Lua]], essentially: |
see [[Doubly-linked_list/Definition#Lua]], essentially: |
||
< |
<syntaxhighlight lang="lua">local node = { data=data, prev=nil, next=nil }</syntaxhighlight> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{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: |
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}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">type |
||
Node[T] = ref TNode[T] |
Node[T] = ref TNode[T] |
||
TNode[T] = object |
TNode[T] = object |
||
next, prev: Node[T] |
next, prev: Node[T] |
||
data: T</ |
data: T</syntaxhighlight> |
||
=={{header|Oberon-2}}== |
=={{header|Oberon-2}}== |
||
< |
<syntaxhighlight lang="oberon2"> |
||
MODULE Box; |
MODULE Box; |
||
TYPE |
TYPE |
||
Line 518: | Line 518: | ||
(* ... *) |
(* ... *) |
||
END Collections. |
END Collections. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
< |
<syntaxhighlight lang="objeck">class ListNode { |
||
@value : Base; |
@value : Base; |
||
@next : ListNode; |
@next : ListNode; |
||
Line 553: | Line 553: | ||
return @previous; |
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 598: | Line 598: | ||
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 607: | Line 607: | ||
4 |
4 |
||
5 |
5 |
||
- : unit = ()</ |
- : unit = ()</syntaxhighlight> |
||
===Functional=== |
===Functional=== |
||
Line 614: | Line 614: | ||
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 636: | Line 636: | ||
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 645: | Line 645: | ||
# current nl ;; |
# current nl ;; |
||
- : int = 3</ |
- : int = 3</syntaxhighlight> |
||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
Line 651: | Line 651: | ||
Complete definition is here : [[../Definition#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 670: | Line 670: | ||
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|Phix}}== |
=={{header|Phix}}== |
||
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use |
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;">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;">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;">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> |
<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]]. |
But more often you would just use the builtin sequences. See also [[Singly-linked_list/Element_definition#Phix|Singly-linked_list/Element_definition]]. |
||
Line 708: | Line 708: | ||
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) |
||
(let L (cdr DLst) |
(let L (cdr DLst) |
||
(con DLst (cons X L NIL)) |
(con DLst (cons X L NIL)) |
||
Line 723: | Line 723: | ||
# We prepend 'not' to the list in the previous example |
# We prepend 'not' to the list in the previous example |
||
(2head 'not *DLst)</ |
(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}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
define structure |
define structure |
||
1 Node, |
1 Node, |
||
Line 742: | Line 742: | ||
... |
... |
||
P = P => back_pointer; /* P now points at the previous node. */ |
P = P => back_pointer; /* P now points at the previous node. */ |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Plain English}}== |
=={{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. |
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 784: | Line 784: | ||
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. |
||
Line 798: | Line 798: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<syntaxhighlight lang="raku" line>role DLElem[::T] { |
||
has DLElem[T] $.prev is rw; |
has DLElem[T] $.prev is rw; |
||
has DLElem[T] $.next is rw; |
has DLElem[T] $.next is rw; |
||
Line 828: | Line 828: | ||
$!prev.next = $!next; # conveniently returns next element |
$!prev.next = $!next; # conveniently returns next element |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 855: | Line 855: | ||
║ @del k,m ─── deletes the M items starting with 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 '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 'building list: Was it a cat I saw' ; call @put "Was it a cat I saw" |
||
Line 898: | Line 898: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
@show: procedure expose $.; parse arg k,m,dir; if dir==-1 & k=='' then k=$.# |
@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</ |
m=p(m $.#); call @parms 'kmd'; say @get(k,m, dir); return</syntaxhighlight> |
||
'''output''' |
'''output''' |
||
<pre> |
<pre> |
||
Line 938: | Line 938: | ||
=={{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 957: | Line 957: | ||
end |
end |
||
list = DListNode.from_values 1,2,3,4</ |
list = DListNode.from_values 1,2,3,4</syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
Line 963: | Line 963: | ||
=== Simply using the standard library === |
=== Simply using the standard library === |
||
< |
<syntaxhighlight lang="rust">use std::collections::LinkedList; |
||
fn main() { |
fn main() { |
||
// Doubly linked list containing 32-bit integers |
// Doubly linked list containing 32-bit integers |
||
let list = LinkedList::<i32>::new(); |
let list = LinkedList::<i32>::new(); |
||
}</ |
}</syntaxhighlight> |
||
=== The behind-the-scenes implementation === |
=== The behind-the-scenes implementation === |
||
Line 974: | Line 974: | ||
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. |
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>>>, |
head: Option<Shared<Node<T>>>, |
||
tail: Option<Shared<Node<T>>>, |
tail: Option<Shared<Node<T>>>, |
||
Line 985: | Line 985: | ||
prev: Option<Shared<Node<T>>>, |
prev: Option<Shared<Node<T>>>, |
||
element: T, |
element: T, |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var node = Hash.new( |
||
data => 'say what', |
data => 'say what', |
||
next => foo_node, |
next => foo_node, |
||
Line 994: | Line 994: | ||
); |
); |
||
node{:next} = quux_node; # mutable</ |
node{:next} = quux_node; # mutable</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>> |
||
class Node<T> { |
class Node<T> { |
||
Line 1,011: | Line 1,011: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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 1,035: | Line 1,035: | ||
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}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-llist}} |
{{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. |
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="ecmascript">import "/llist" for DNode |
||
var dn1 = DNode.new(1) |
var dn1 = DNode.new(1) |
||
Line 1,057: | Line 1,057: | ||
dn2.next = null |
dn2.next = null |
||
System.print(["node 1", "data = %(dn1.data)", "prev = %(dn1.prev)", "next = %(dn1.next)"]) |
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)"])</ |
System.print(["node 2", "data = %(dn2.data)", "prev = %(dn2.prev)", "next = %(dn2.next)"])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,066: | Line 1,066: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">class Node{ |
||
fcn init(_value,_prev=Void,_next=Void) |
fcn init(_value,_prev=Void,_next=Void) |
||
{ var value=_value, prev=_prev, next=_next; } |
{ var value=_value, prev=_prev, next=_next; } |
||
fcn toString{ value.toString() } |
fcn toString{ value.toString() } |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">a,b:=Node(1),Node("three"); |
||
a.next=b; b.prev=a; |
a.next=b; b.prev=a; |
||
println(a.next," ",b.prev);</ |
println(a.next," ",b.prev);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |