Singly-linked list/Element definition: Difference between revisions
Content deleted Content added
Puppydrum64 (talk | contribs) |
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
||
Line 5: | Line 5: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
The program uses DSECT and USING pseudo instruction to define a node. |
The program uses DSECT and USING pseudo instruction to define a node. |
||
< |
<syntaxhighlight lang="360asm">* Singly-linked list/Element definition 07/02/2017 |
||
LISTSINA CSECT |
LISTSINA CSECT |
||
USING LISTSINA,R13 base register |
USING LISTSINA,R13 base register |
||
Line 91: | Line 91: | ||
NEXT DS A |
NEXT DS A |
||
YREGS |
YREGS |
||
END LISTSINA</ |
END LISTSINA</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 102: | Line 102: | ||
A linked list entry can be created by writing its value and the pointer to the next one to RAM. It should be noted that without some form of dynamic memory allocation, a linked list is not easy to use. |
A linked list entry can be created by writing its value and the pointer to the next one to RAM. It should be noted that without some form of dynamic memory allocation, a linked list is not easy to use. |
||
< |
<syntaxhighlight lang="6502asm">;create a node at address $0020, and another node at address $0040. |
||
;The first node has a value of #$77, the second, #$99. |
;The first node has a value of #$77, the second, #$99. |
||
;create first node |
;create first node |
||
Line 117: | Line 117: | ||
LDA #$FF ;use $FFFF as the null pointer since the only thing that can be at address $FFFF is the high byte of the IRQ routine. |
LDA #$FF ;use $FFFF as the null pointer since the only thing that can be at address $FFFF is the high byte of the IRQ routine. |
||
STA $41 |
STA $41 |
||
STA $42 </ |
STA $42 </syntaxhighlight> |
||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
<syntaxhighlight lang="aarch64 assembly"> |
|||
<lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program defList.s */ |
/* program defList.s */ |
||
Line 179: | Line 179: | ||
/* for this file see task include a file in language AArch64 assembly */ |
/* for this file see task include a file in language AArch64 assembly */ |
||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ACL2}}== |
=={{header|ACL2}}== |
||
The built in pair type, <code>cons</code>, is sufficient for defining a linked list. ACL2 does not have mutable variables, so functions must instead return a copy of the original list. |
The built in pair type, <code>cons</code>, is sufficient for defining a linked list. ACL2 does not have mutable variables, so functions must instead return a copy of the original list. |
||
< |
<syntaxhighlight lang="lisp">(let ((elem 8) |
||
(next (list 6 7 5 3 0 9))) |
(next (list 6 7 5 3 0 9))) |
||
(cons elem next))</ |
(cons elem next))</syntaxhighlight> |
||
Output: |
Output: |
||
Line 192: | Line 192: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">DEFINE PTR="CARD" |
||
TYPE ListNode=[ |
TYPE ListNode=[ |
||
BYTE data |
BYTE data |
||
PTR nxt]</ |
PTR nxt]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_element_definition.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_element_definition.png Screenshot from Atari 8-bit computer] |
||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
< |
<syntaxhighlight lang="actionscript">package |
||
{ |
{ |
||
public class Node |
public class Node |
||
Line 213: | Line 213: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{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 |
||
Next : Link_Access := null; |
Next : Link_Access := null; |
||
Data : Integer; |
Data : Integer; |
||
end record;</ |
end record;</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 228: | Line 228: | ||
{{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/single_link.a68'''< |
'''File: prelude/single_link.a68'''<syntaxhighlight lang="algol68"># -*- coding: utf-8 -*- # |
||
CO REQUIRES: |
CO REQUIRES: |
||
MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked # |
MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked # |
||
Line 242: | Line 242: | ||
PROC obj nextlink free = (REF OBJNEXTLINK free)VOID: |
PROC obj nextlink free = (REF OBJNEXTLINK free)VOID: |
||
next OF free := obj stack empty # give the garbage collector a BIG hint #</ |
next OF free := obj stack empty # give the garbage collector a BIG hint #</syntaxhighlight>'''See also:''' [[Stack#ALGOL_68|Stack]] |
||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw"> % record type to hold a singly linked list of integers % |
||
record ListI ( integer iValue; reference(ListI) next ); |
record ListI ( integer iValue; reference(ListI) next ); |
||
Line 252: | Line 252: | ||
% create a list of integers % |
% create a list of integers % |
||
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );</ |
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );</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 */ |
||
/* program defList.s */ |
/* program defList.s */ |
||
Line 325: | Line 325: | ||
pop {r0,r1,r2,r7,lr} @ restaur registers |
pop {r0,r1,r2,r7,lr} @ restaur registers |
||
bx lr @ return |
bx lr @ return |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
< |
<syntaxhighlight lang="ats">(* The Rosetta Code linear list type can contain any vt@ype. |
||
(The ‘@’ means it doesn’t have to be the size of a pointer. |
(The ‘@’ means it doesn’t have to be the size of a pointer. |
||
You can read {0 <= n} as ‘for all non-negative n’. *) |
You can read {0 <= n} as ‘for all non-negative n’. *) |
||
Line 347: | Line 347: | ||
case+ lst of |
case+ lst of |
||
| rclist_vt_nil () => () |
| rclist_vt_nil () => () |
||
| rclist_vt_cons _ => ()</ |
| rclist_vt_cons _ => ()</syntaxhighlight> |
||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">element = 5 ; data |
||
element_next = element2 ; link to next element</ |
element_next = element2 ; link to next element</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Line 357: | Line 357: | ||
Awk only has global associative arrays, which will be used for the list. Numerical indexes into the array will serve as node pointers. A list element will have the next node pointer separated from the value by the pre-defined SUBSEP value. A function will be used to access a node's next node pointer or value given a node pointer (array index). The first array element will serve as the list head. |
Awk only has global associative arrays, which will be used for the list. Numerical indexes into the array will serve as node pointers. A list element will have the next node pointer separated from the value by the pre-defined SUBSEP value. A function will be used to access a node's next node pointer or value given a node pointer (array index). The first array element will serve as the list head. |
||
< |
<syntaxhighlight lang="awk"> |
||
BEGIN { |
BEGIN { |
||
NIL = 0 |
NIL = 0 |
||
Line 381: | Line 381: | ||
return linkAndValue[part] |
return linkAndValue[part] |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Axe}}== |
=={{header|Axe}}== |
||
< |
<syntaxhighlight lang="axe">Lbl LINK |
||
r₂→{r₁}ʳ |
r₂→{r₁}ʳ |
||
0→{r₁+2}ʳ |
0→{r₁+2}ʳ |
||
Line 396: | Line 396: | ||
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{pNext%, iData%} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
Data mutation is not Bracmatish, but it can be done. Here is a datastructure for a mutable data value and for a mutable reference. |
Data mutation is not Bracmatish, but it can be done. Here is a datastructure for a mutable data value and for a mutable reference. |
||
< |
<syntaxhighlight lang="bracmat">link = |
||
(next=) |
(next=) |
||
(data=)</ |
(data=)</syntaxhighlight> |
||
Example of use: |
Example of use: |
||
< |
<syntaxhighlight lang="bracmat"> new$link:?link1 |
||
& new$link:?link2 |
& new$link:?link2 |
||
& first thing:?(link1..data) |
& first thing:?(link1..data) |
||
& secundus:?(link2..data) |
& secundus:?(link2..data) |
||
& '$link2:(=?(link1..next)) |
& '$link2:(=?(link1..next)) |
||
& !(link1..next..data)</ |
& !(link1..next..data)</syntaxhighlight> |
||
The last line returns |
The last line returns |
||
<pre>secundus</pre> |
<pre>secundus</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">struct link { |
||
struct link *next; |
struct link *next; |
||
int data; |
int data; |
||
};</ |
};</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">class LinkedListNode |
||
{ |
{ |
||
public int Value { get; set; } |
public int Value { get; set; } |
||
Line 437: | Line 437: | ||
Next = next; |
Next = next; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
A generic version: |
A generic version: |
||
< |
<syntaxhighlight lang="csharp">class LinkedListNode<T> |
||
{ |
{ |
||
public T Value { get; set; } |
public T Value { get; set; } |
||
Line 450: | Line 450: | ||
Next = next; |
Next = next; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
The most C-like possible version is basically C. |
The most C-like possible version is basically C. |
||
< |
<syntaxhighlight lang="csharp">unsafe struct link { |
||
public link* next; |
public link* next; |
||
public int data; |
public int data; |
||
};</ |
};</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 462: | Line 462: | ||
The simplest C++ version looks basically like the C version: |
The simplest C++ version looks basically like the C version: |
||
< |
<syntaxhighlight lang="cpp">struct link |
||
{ |
{ |
||
link* next; |
link* next; |
||
int data; |
int data; |
||
};</ |
};</syntaxhighlight> |
||
Initialization of links on the heap can be simplified by adding a constructor: |
Initialization of links on the heap can be simplified by adding a constructor: |
||
< |
<syntaxhighlight lang="cpp">struct link |
||
{ |
{ |
||
link* next; |
link* next; |
||
int data; |
int data; |
||
link(int a_data, link* a_next = 0): next(a_next), data(a_data) {} |
link(int a_data, link* a_next = 0): next(a_next), data(a_data) {} |
||
};</ |
};</syntaxhighlight> |
||
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement: |
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement: |
||
< |
<syntaxhighlight lang="cpp"> link* small_primes = new link(2, new link(3, new link(5, new link(7))));</syntaxhighlight> |
||
However, C++ also allows to make it generic on the data type (e.g. if you need large numbers, you might want to use a larger type than int, e.g. long on 64-bit platforms, long long on compilers that support it, or even a bigint class). |
However, C++ also allows to make it generic on the data type (e.g. if you need large numbers, you might want to use a larger type than int, e.g. long on 64-bit platforms, long long on compilers that support it, or even a bigint class). |
||
< |
<syntaxhighlight lang="cpp">template<typename T> struct link |
||
{ |
{ |
||
link* next; |
link* next; |
||
T data; |
T data; |
||
link(T a_data, link* a_next = 0): next(a_next), data(a_data) {} |
link(T a_data, link* a_next = 0): next(a_next), data(a_data) {} |
||
};</ |
};</syntaxhighlight> |
||
Note that the generic version works for any type, not only integral types. |
Note that the generic version works for any type, not only integral types. |
||
=={{header|Clean}}== |
=={{header|Clean}}== |
||
< |
<syntaxhighlight lang="clean">import StdMaybe |
||
:: Link t = { next :: Maybe (Link t), data :: t }</ |
:: Link t = { next :: Maybe (Link t), data :: t }</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
As with other LISPs, this is built in. Clojure provides a nice abstraction of lists with its use of: [http://clojure.org/sequences sequences] (also called seqs). |
As with other LISPs, this is built in. Clojure provides a nice abstraction of lists with its use of: [http://clojure.org/sequences sequences] (also called seqs). |
||
< |
<syntaxhighlight lang="clojure">(cons 1 (cons 2 (cons 3 nil))) ; =>(1 2 3)</syntaxhighlight> |
||
Note: this is an immutable data structure. With cons you are '''cons'''tructing a new seq. |
Note: this is an immutable data structure. With cons you are '''cons'''tructing a new seq. |
||
Line 508: | Line 508: | ||
The built-in <code>cons</code> type is used to construct linked lists. Using another type would be unidiomatic and inefficient. |
The built-in <code>cons</code> type is used to construct linked lists. Using another type would be unidiomatic and inefficient. |
||
< |
<syntaxhighlight lang="lisp">(cons 1 (cons 2 (cons 3 nil)) => (1 2 3)</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
Generic template-based node element. |
Generic template-based node element. |
||
< |
<syntaxhighlight lang="d">struct SLinkedNode(T) { |
||
T data; |
T data; |
||
typeof(this)* next; |
typeof(this)* next; |
||
Line 521: | Line 521: | ||
alias SLinkedNode!int N; |
alias SLinkedNode!int N; |
||
N* n = new N(10); |
N* n = new N(10); |
||
}</ |
}</syntaxhighlight> |
||
Also the Phobos library contains a singly-linked list, std.container.SList. Tango contains tango.util.collection.LinkSeq. |
Also the Phobos library contains a singly-linked list, std.container.SList. Tango contains tango.util.collection.LinkSeq. |
||
Line 528: | Line 528: | ||
A simple one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever. Note that in Standard Pascal, there are no generic pointers, therefore one has to settle for a specific data type there. |
A simple one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever. Note that in Standard Pascal, there are no generic pointers, therefore one has to settle for a specific data type there. |
||
< |
<syntaxhighlight lang="delphi">Type |
||
pOneWayList = ^OneWayList; |
pOneWayList = ^OneWayList; |
||
OneWayList = record |
OneWayList = record |
||
pData : pointer ; |
pData : pointer ; |
||
Next : pOneWayList ; |
Next : pOneWayList ; |
||
end;</ |
end;</syntaxhighlight> |
||
=={{header|Diego}}== |
=={{header|Diego}}== |
||
< |
<syntaxhighlight lang="diego">use_namespace(rosettacode)_me(); |
||
add_struct(link)_arg({link},next,{int},data); |
add_struct(link)_arg({link},next,{int},data); |
||
Line 542: | Line 542: | ||
add_link(primeNumbers)_arg([],2)_link()_arg([],3)_link()_arg([],5)_link()_arg(null,7); |
add_link(primeNumbers)_arg([],2)_link()_arg([],3)_link()_arg([],5)_link()_arg(null,7); |
||
reset_namespace[];</ |
reset_namespace[];</syntaxhighlight> |
||
=={{header|E}}== |
=={{header|E}}== |
||
< |
<syntaxhighlight lang="e">interface LinkedList guards LinkedListStamp {} |
||
def empty implements LinkedListStamp { |
def empty implements LinkedListStamp { |
||
to null() { return true } |
to null() { return true } |
||
Line 558: | Line 558: | ||
} |
} |
||
return link |
return link |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
< |
<syntaxhighlight lang="elena">class Link |
||
{ |
{ |
||
prop int Item; |
prop int Item; |
||
Line 571: | Line 571: | ||
Next := next |
Next := next |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Lists are builtin, but Erlang is single assignment. Here we need mutable link to next element. Mutable in Erlang usually means a process, so: |
Lists are builtin, but Erlang is single assignment. Here we need mutable link to next element. Mutable in Erlang usually means a process, so: |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ). |
new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ). |
||
</syntaxhighlight> |
|||
</lang> |
|||
For the whole module see [[Singly-linked_list/Element_insertion]] |
For the whole module see [[Singly-linked_list/Element_insertion]] |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
<lang>TUPLE: linked-list data next ; |
<syntaxhighlight lang="text">TUPLE: linked-list data next ; |
||
: <linked-list> ( data -- linked-list ) |
: <linked-list> ( data -- linked-list ) |
||
linked-list new swap >>data ;</ |
linked-list new swap >>data ;</syntaxhighlight> |
||
=={{header|Fantom}}== |
=={{header|Fantom}}== |
||
< |
<syntaxhighlight lang="fantom"> |
||
class Node |
class Node |
||
{ |
{ |
||
Line 600: | Line 600: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
Line 606: | Line 606: | ||
Idiomatically, |
Idiomatically, |
||
< |
<syntaxhighlight lang="forth">0 value numbers |
||
: push ( n -- ) |
: push ( n -- ) |
||
here swap numbers , , to numbers ;</ |
here swap numbers , , to numbers ;</syntaxhighlight> |
||
NUMBERS is the head of the list, initially nil (= 0); PUSH adds an element to the list; list cells have the structure {Link,Number}. Speaking generally, Number can be anything and list cells can be as long as desired (e.g., {Link,N1,N2} or {Link,Count,"a very long string"}), but the link is always first - or rather, a link always points to the next link, so that NEXT-LIST-CELL is simply fetch (@). Some operations: |
NUMBERS is the head of the list, initially nil (= 0); PUSH adds an element to the list; list cells have the structure {Link,Number}. Speaking generally, Number can be anything and list cells can be as long as desired (e.g., {Link,N1,N2} or {Link,Count,"a very long string"}), but the link is always first - or rather, a link always points to the next link, so that NEXT-LIST-CELL is simply fetch (@). Some operations: |
||
< |
<syntaxhighlight lang="forth">: length ( list -- u ) |
||
0 swap begin dup while 1 under+ @ repeat drop ; |
0 swap begin dup while 1 under+ @ repeat drop ; |
||
Line 619: | Line 619: | ||
: .numbers ( list -- ) |
: .numbers ( list -- ) |
||
begin dup while dup head . @ repeat drop ;</ |
begin dup while dup head . @ repeat drop ;</syntaxhighlight> |
||
Higher-order programming, simple continuations, and immediate words can pull out the parallel code of LENGTH and .NUMBERS . Anonymous and dynamically allocated lists are as straightforward. |
Higher-order programming, simple continuations, and immediate words can pull out the parallel code of LENGTH and .NUMBERS . Anonymous and dynamically allocated lists are as straightforward. |
||
Line 625: | Line 625: | ||
=={{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() |
type( node ), pointer :: next => null() |
||
Line 632: | Line 632: | ||
!. . . . |
!. . . . |
||
! |
! |
||
type( node ) :: head</ |
type( node ) :: head</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">type ll_int |
||
n as integer |
n as integer |
||
nxt as ll_int ptr |
nxt as ll_int ptr |
||
end type</ |
end type</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">type Ele struct { |
||
Data interface{} |
Data interface{} |
||
Next *Ele |
Next *Ele |
||
Line 658: | Line 658: | ||
func (e *Ele) String() string { |
func (e *Ele) String() string { |
||
return fmt.Sprintf("Ele: %v", e.Data) |
return fmt.Sprintf("Ele: %v", e.Data) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">class ListNode { |
||
Object payload |
Object payload |
||
ListNode next |
ListNode next |
||
String toString() { "${payload} -> ${next}" } |
String toString() { "${payload} -> ${next}" } |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">def n1 = new ListNode(payload:25) |
||
n1.next = new ListNode(payload:88) |
n1.next = new ListNode(payload:88) |
||
println n1</ |
println n1</syntaxhighlight> |
||
Output: |
Output: |
||
Line 683: | Line 683: | ||
An equivalent declaration for such a list type without the special syntax would look like this: |
An equivalent declaration for such a list type without the special syntax would look like this: |
||
< |
<syntaxhighlight lang="haskell"> data List a = Nil | Cons a (List a)</syntaxhighlight> |
||
A declaration like the one required in the task, with an integer as element type and a mutable link, would be |
A declaration like the one required in the task, with an integer as element type and a mutable link, would be |
||
< |
<syntaxhighlight lang="haskell"> data IntList s = Nil | Cons Integer (STRef s (IntList s))</syntaxhighlight> |
||
but that would be really awkward to use. |
but that would be really awkward to use. |
||
Line 697: | Line 697: | ||
==={{header|Icon}}=== |
==={{header|Icon}}=== |
||
<syntaxhighlight lang="icon"> |
|||
<lang Icon> |
|||
record Node (value, successor) |
record Node (value, successor) |
||
</syntaxhighlight> |
|||
</lang> |
|||
==={{header|Unicon}}=== |
==={{header|Unicon}}=== |
||
<syntaxhighlight lang="unicon"> |
|||
<lang Unicon> |
|||
class Node (value, successor) |
class Node (value, successor) |
||
initially (value, successor) |
initially (value, successor) |
||
Line 709: | Line 709: | ||
self.successor := successor |
self.successor := successor |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
With either the record or the class definition, new linked lists are easily created and manipulated: |
With either the record or the class definition, new linked lists are easily created and manipulated: |
||
<syntaxhighlight lang="icon"> |
|||
<lang Icon> |
|||
procedure main () |
procedure main () |
||
n := Node(1, Node (2)) |
n := Node(1, Node (2)) |
||
Line 719: | Line 719: | ||
write (n.successor.value) |
write (n.successor.value) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 727: | Line 727: | ||
However, for illustrative purposes: |
However, for illustrative purposes: |
||
< |
<syntaxhighlight lang="j">list=: 0 2$0 |
||
list</ |
list</syntaxhighlight> |
||
This creates and then displays an empty list, with zero elements. The first number in an item is (supposed to be) the index of the next element of the list (_ for the final element of the list). The second number in an item is the numeric value stored in that list item. The list is named and names are mutable in J which means links are mutable. |
This creates and then displays an empty list, with zero elements. The first number in an item is (supposed to be) the index of the next element of the list (_ for the final element of the list). The second number in an item is the numeric value stored in that list item. The list is named and names are mutable in J which means links are mutable. |
||
Line 734: | Line 734: | ||
To create such a list with one element which contains number 42, we can do the following: |
To create such a list with one element which contains number 42, we can do the following: |
||
< |
<syntaxhighlight lang="j"> list=: ,: _ 42 |
||
list |
list |
||
_ 42</ |
_ 42</syntaxhighlight> |
||
Now list contains one item, with index of the next item and value. |
Now list contains one item, with index of the next item and value. |
||
Line 742: | Line 742: | ||
Note: this solution exploits the fact that, in this numeric case, data types for index and for node content are the same. If we need to store, for example, strings in the nodes, we should do something different, for example: |
Note: this solution exploits the fact that, in this numeric case, data types for index and for node content are the same. If we need to store, for example, strings in the nodes, we should do something different, for example: |
||
< |
<syntaxhighlight lang="j"> list=: 0 2$a: NB. creates list with 0 items |
||
list |
list |
||
list=: ,: (<_) , <'some text' NB. creates list with 1 item |
list=: ,: (<_) , <'some text' NB. creates list with 1 item |
||
Line 748: | Line 748: | ||
+-+---------+ |
+-+---------+ |
||
|_|some text| |
|_|some text| |
||
+-+---------+</ |
+-+---------+</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
Line 754: | Line 754: | ||
The simplest Java version looks basically like the C++ version: |
The simplest Java version looks basically like the C++ version: |
||
< |
<syntaxhighlight lang="java">class Link |
||
{ |
{ |
||
Link next; |
Link next; |
||
int data; |
int data; |
||
}</ |
}</syntaxhighlight> |
||
Initialization of links on the heap can be simplified by adding a constructor: |
Initialization of links on the heap can be simplified by adding a constructor: |
||
< |
<syntaxhighlight lang="java">class Link |
||
{ |
{ |
||
Link next; |
Link next; |
||
int data; |
int data; |
||
Link(int a_data, Link a_next) { next = a_next; data = a_data; } |
Link(int a_data, Link a_next) { next = a_next; data = a_data; } |
||
}</ |
}</syntaxhighlight> |
||
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement: |
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement: |
||
< |
<syntaxhighlight lang="java"> Link small_primes = new Link(2, new Link(3, new Link(5, new Link(7, null))));</syntaxhighlight> |
||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
However, Java also allows to make it generic on the data type. This will only work on reference types, not primitive types like int or float (wrapper classes like Integer and Float are available). |
However, Java also allows to make it generic on the data type. This will only work on reference types, not primitive types like int or float (wrapper classes like Integer and Float are available). |
||
< |
<syntaxhighlight lang="java">class Link<T> |
||
{ |
{ |
||
Link<T> next; |
Link<T> next; |
||
T data; |
T data; |
||
Link(T a_data, Link<T> a_next) { next = a_next; data = a_data; } |
Link(T a_data, Link<T> a_next) { next = a_next; data = a_data; } |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">function LinkedList(value, next) { |
||
this._value = value; |
this._value = value; |
||
this._next = next; |
this._next = next; |
||
Line 813: | Line 813: | ||
} |
} |
||
var head = createLinkedListFromArray([10,20,30,40]);</ |
var head = createLinkedListFromArray([10,20,30,40]);</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 840: | Line 840: | ||
Note that according to these principles, the JSON value `null` does |
Note that according to these principles, the JSON value `null` does |
||
not represent a SLL, and JSON representatives of SLLs may have additional keys. |
not represent a SLL, and JSON representatives of SLLs may have additional keys. |
||
< |
<syntaxhighlight lang="jq">def is_empty_singly_linked_list: |
||
type == "object" and .next == null and (has("item")|not); |
type == "object" and .next == null and (has("item")|not); |
||
Line 857: | Line 857: | ||
else ($x.item) == ($y.item) |
else ($x.item) == ($y.item) |
||
and equal_singly_linked_lists($x.next; $y.next) |
and equal_singly_linked_lists($x.next; $y.next) |
||
end;</ |
end;</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 920: | Line 920: | ||
pop!(lst) # 3 |
pop!(lst) # 3 |
||
pop!(lst) # 2 |
pop!(lst) # 2 |
||
pop!(lst) # 1</ |
pop!(lst) # 1</syntaxhighlight> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
class Node<T: Number>(var data: T, var next: Node<T>? = null) { |
class Node<T: Number>(var data: T, var next: Node<T>? = null) { |
||
Line 940: | Line 940: | ||
val n = Node(1, Node(2, Node(3))) |
val n = Node(1, Node(2, Node(3))) |
||
println(n) |
println(n) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 950: | Line 950: | ||
As with other list-based languages, simple lists are represented easily in Logo. |
As with other list-based languages, simple lists are represented easily in Logo. |
||
< |
<syntaxhighlight lang="logo">fput item list ; add item to the head of a list |
||
first list ; get the data |
first list ; get the data |
||
butfirst list ; get the remainder |
butfirst list ; get the remainder |
||
bf list ; contraction for "butfirst"</ |
bf list ; contraction for "butfirst"</syntaxhighlight> |
||
These return modified lists, but you can also destructively modify lists. These are normally not used because you might accidentally create cycles in the list. |
These return modified lists, but you can also destructively modify lists. These are normally not used because you might accidentally create cycles in the list. |
||
< |
<syntaxhighlight lang="logo">.setfirst list value |
||
.setbf list remainder</ |
.setbf list remainder</syntaxhighlight> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Append[{}, x] |
||
-> {x}</ |
-> {x}</syntaxhighlight> |
||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
< |
<syntaxhighlight lang="modula2">TYPE |
||
Link = POINTER TO LinkRcd; |
Link = POINTER TO LinkRcd; |
||
LinkRcd = RECORD |
LinkRcd = RECORD |
||
Next: Link; |
Next: Link; |
||
Data: INTEGER |
Data: INTEGER |
||
END;</ |
END;</syntaxhighlight> |
||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
< |
<syntaxhighlight lang="modula3">TYPE |
||
Link = REF LinkRcd; |
Link = REF LinkRcd; |
||
LinkRcd = RECORD |
LinkRcd = RECORD |
||
Next: Link; |
Next: Link; |
||
Data: INTEGER |
Data: INTEGER |
||
END;</ |
END;</syntaxhighlight> |
||
=={{header|Nanoquery}}== |
=={{header|Nanoquery}}== |
||
The simplest version in Nanoquery is similar to the C version: |
The simplest version in Nanoquery is similar to the C version: |
||
< |
<syntaxhighlight lang="nanoquery">class link |
||
declare data |
declare data |
||
declare next |
declare next |
||
end</ |
end</syntaxhighlight> |
||
Like Java, it is possible to add a constructor that allows us to set the values on initialization. |
Like Java, it is possible to add a constructor that allows us to set the values on initialization. |
||
< |
<syntaxhighlight lang="nanoquery">class link |
||
declare data |
declare data |
||
declare next |
declare next |
||
Line 998: | Line 998: | ||
this.next = next |
this.next = next |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
This allows us to define an entire list in a single (albeit confusing) line of source. |
This allows us to define an entire list in a single (albeit confusing) line of source. |
||
< |
<syntaxhighlight lang="nanoquery">linkedlist = new(link, 1, new(link, 2, new(link, 3, new(link, 4, null))))</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">type |
||
Node[T] = ref object |
Node[T] = ref object |
||
Line 1,050: | Line 1,050: | ||
for i in 1..5: list.append(i) |
for i in 1..5: list.append(i) |
||
for i in 6..10: list.prepend(i) |
for i in 6..10: list.prepend(i) |
||
echo "List: ", list</ |
echo "List: ", list</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,057: | Line 1,057: | ||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
< |
<syntaxhighlight lang="objc">#import <Foundation/Foundation.h> |
||
@interface RCListElement<T> : NSObject |
@interface RCListElement<T> : NSObject |
||
Line 1,089: | Line 1,089: | ||
datum = d; |
datum = d; |
||
} |
} |
||
@end</ |
@end</syntaxhighlight> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Line 1,097: | Line 1,097: | ||
An equivalent declaration for such a list type without the special syntax would look like this: |
An equivalent declaration for such a list type without the special syntax would look like this: |
||
< |
<syntaxhighlight lang="ocaml"> type 'a list = Nil | Cons of 'a * 'a list</syntaxhighlight> |
||
A declaration like the one required in the task, with an integer as element type and a mutable link, would be |
A declaration like the one required in the task, with an integer as element type and a mutable link, would be |
||
< |
<syntaxhighlight lang="ocaml"> type int_list = Nil | Cons of int * int_list ref</syntaxhighlight> |
||
but that would be really awkward to use. |
but that would be really awkward to use. |
||
Line 1,107: | Line 1,107: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">Collection Class new: LinkedList(data, mutable next)</syntaxhighlight> |
||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
The simplest ooRexx version is similar in form to the Java or C++ versions: |
The simplest ooRexx version is similar in form to the Java or C++ versions: |
||
<syntaxhighlight lang="oorexx"> |
|||
<lang ooRexx> |
|||
list = .linkedlist~new |
list = .linkedlist~new |
||
index = list~insert("abc") -- insert a first item, keeping the index |
index = list~insert("abc") -- insert a first item, keeping the index |
||
Line 1,248: | Line 1,248: | ||
</syntaxhighlight> |
|||
</lang> |
|||
A link element can hold a reference to any ooRexx object. |
A link element can hold a reference to any ooRexx object. |
||
Line 1,254: | Line 1,254: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">type |
||
PLink = ^TLink; |
PLink = ^TLink; |
||
TLink = record |
TLink = record |
||
FNext: PLink; |
FNext: PLink; |
||
FData: integer; |
FData: integer; |
||
end;</ |
end;</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Line 1,265: | Line 1,265: | ||
However, if all you got is an algorithm in a foreign language, you can use references to accomplish the translation. |
However, if all you got is an algorithm in a foreign language, you can use references to accomplish the translation. |
||
< |
<syntaxhighlight lang="perl">my %node = ( |
||
data => 'say what', |
data => 'say what', |
||
next => \%foo_node, |
next => \%foo_node, |
||
); |
); |
||
$node{next} = \%bar_node; # mutable</ |
$node{next} = \%bar_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 something like |
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use something like |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</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;">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: #000000;">myotherudt</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;">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: #000000;">myotherudt</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;">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. It is worth noting that while "node lists", such as |
But more often you would just use the builtin sequences. It is worth noting that while "node lists", such as |
||
{{2},{'A',3},{'B',4},{'C',0}} are one way to hold a linked list (with the first element a dummy header), |
{{2},{'A',3},{'B',4},{'C',0}} are one way to hold a linked list (with the first element a dummy header), |
||
Line 1,304: | Line 1,304: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
declare 1 node based (p), |
declare 1 node based (p), |
||
2 value fixed, |
2 value fixed, |
||
2 link pointer; |
2 link pointer; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Pop11}}== |
=={{header|Pop11}}== |
||
Line 1,314: | Line 1,314: | ||
List are built in into Pop11, so normally on would just use them: |
List are built in into Pop11, so normally on would just use them: |
||
< |
<syntaxhighlight lang="pop11">;;; Use shorthand syntax to create list. |
||
lvars l1 = [1 2 three 'four']; |
lvars l1 = [1 2 three 'four']; |
||
;;; Allocate a single list node, with value field 1 and the link field |
;;; Allocate a single list node, with value field 1 and the link field |
||
Line 1,328: | Line 1,328: | ||
l1 -> back(l2); |
l1 -> back(l2); |
||
;;; Print l2 |
;;; Print l2 |
||
l2 =></ |
l2 =></syntaxhighlight> |
||
If however one wants to definite equivalent user-defined type, one can do this: |
If however one wants to definite equivalent user-defined type, one can do this: |
||
< |
<syntaxhighlight lang="pop11">uses objectclass; |
||
define :class ListNode; |
define :class ListNode; |
||
slot value = []; |
slot value = []; |
||
Line 1,347: | Line 1,347: | ||
;;; of l1 |
;;; of l1 |
||
consListNode(2, []) -> next(l1); |
consListNode(2, []) -> next(l1); |
||
l1 =></ |
l1 =></syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Structure MyData |
||
*next.MyData |
*next.MyData |
||
Value.i |
Value.i |
||
EndStructure</ |
EndStructure</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 1,360: | Line 1,360: | ||
The Node class implements also iteration for more Pythonic iteration over linked lists. |
The Node class implements also iteration for more Pythonic iteration over linked lists. |
||
< |
<syntaxhighlight lang="python">class LinkedList(object): |
||
"""USELESS academic/classroom example of a linked list implemented in Python. |
"""USELESS academic/classroom example of a linked list implemented in Python. |
||
Don't ever consider using something this crude! Use the built-in list() type! |
Don't ever consider using something this crude! Use the built-in list() type! |
||
Line 1,386: | Line 1,386: | ||
while cursor: |
while cursor: |
||
yield cursor.value |
yield cursor.value |
||
cursor = cursor.next</ |
cursor = cursor.next</syntaxhighlight> |
||
'''Note:''' As explained in this class' docstring implementing linked lists and nodes in Python is an utterly pointless academic exercise. It may give on the flavor of the elements that would be necessary in some other programming languages (''e.g.'' using Python as "executable psuedo-code"). Adding methods for finding, counting, removing and inserting elements is left as an academic exercise to the reader. For any practical application use the built-in ''list()'' or ''dict()'' types as appropriate. |
'''Note:''' As explained in this class' docstring implementing linked lists and nodes in Python is an utterly pointless academic exercise. It may give on the flavor of the elements that would be necessary in some other programming languages (''e.g.'' using Python as "executable psuedo-code"). Adding methods for finding, counting, removing and inserting elements is left as an academic exercise to the reader. For any practical application use the built-in ''list()'' or ''dict()'' types as appropriate. |
||
Line 1,394: | Line 1,394: | ||
Unlike other Lisp dialects, Racket's <tt>cons</tt> cells are immutable, so they cannot be used to satisfy this task. However, Racket also includes mutable pairs which are still the same old mutable singly-linked lists. |
Unlike other Lisp dialects, Racket's <tt>cons</tt> cells are immutable, so they cannot be used to satisfy this task. However, Racket also includes mutable pairs which are still the same old mutable singly-linked lists. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
(mcons 1 (mcons 2 (mcons 3 '()))) ; a mutable list |
(mcons 1 (mcons 2 (mcons 3 '()))) ; a mutable list |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 1,406: | Line 1,406: | ||
A <tt>Pair</tt> (constructed with the <code>=></code> operator) can be treated as a cons cell, and thus used to build a linked lists: |
A <tt>Pair</tt> (constructed with the <code>=></code> operator) can be treated as a cons cell, and thus used to build a linked lists: |
||
<lang |
<syntaxhighlight lang="raku" line>my $elem = 42 => $nextelem;</syntaxhighlight> |
||
However, because this is not the primary purpose of the <tt>Pair</tt> type, it suffers from the following limitations: |
However, because this is not the primary purpose of the <tt>Pair</tt> type, it suffers from the following limitations: |
||
Line 1,418: | Line 1,418: | ||
For more flexibility, one would create a custom type: |
For more flexibility, one would create a custom type: |
||
<lang |
<syntaxhighlight lang="raku" line>class Cell { |
||
has $.value is rw; |
has $.value is rw; |
||
has Cell $.next is rw; |
has Cell $.next is rw; |
||
Line 1,427: | Line 1,427: | ||
sub cons ($value, $next) { Cell.new(:$value, :$next) } |
sub cons ($value, $next) { Cell.new(:$value, :$next) } |
||
my $list = cons 10, (cons 20, (cons 30, Nil));</ |
my $list = cons 10, (cons 20, (cons 30, Nil));</syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
The REXX language doesn't have any native linked lists, but they can be created easily. |
The REXX language doesn't have any native linked lists, but they can be created easily. |
||
<br>The values of a REXX linked list can be anything (nulls, character strings, including any type/kind of number, of course). |
<br>The values of a REXX linked list can be anything (nulls, character strings, including any type/kind of number, of course). |
||
< |
<syntaxhighlight lang="rexx">/*REXX program demonstrates how to create and show a single-linked list.*/ |
||
@.=0 /*define a null linked list. */ |
@.=0 /*define a null linked list. */ |
||
call set@ 3 /*linked list: 12 Proth Primes. */ |
call set@ 3 /*linked list: 12 Proth Primes. */ |
||
Line 1,469: | Line 1,469: | ||
@..y=n /*set a locator pointer to self. */ |
@..y=n /*set a locator pointer to self. */ |
||
@.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/ |
@.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/ |
||
return /*return to invoker of this sub. */</ |
return /*return to invoker of this sub. */</syntaxhighlight> |
||
'''output''' |
'''output''' |
||
<pre> |
<pre> |
||
Line 1,490: | Line 1,490: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">class ListNode |
||
attr_accessor :value, :succ |
attr_accessor :value, :succ |
||
Line 1,517: | Line 1,517: | ||
end |
end |
||
list = ListNode.from_array([1,2,3,4])</ |
list = ListNode.from_array([1,2,3,4])</syntaxhighlight> |
||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">data = 10 |
||
link = 10 |
link = 10 |
||
dim node{data,link} </ |
dim node{data,link} </syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
Rust's <code>Option<T></code> type make the definition of a singly-linked list trivial. The use of <code>Box<T></code> (an owned pointer) is necessary because it has a known size, thus making sure the struct that contains it can have a finite size. |
Rust's <code>Option<T></code> type make the definition of a singly-linked list trivial. The use of <code>Box<T></code> (an owned pointer) is necessary because it has a known size, thus making sure the struct that contains it can have a finite size. |
||
< |
<syntaxhighlight lang="rust"> struct Node<T> { |
||
elem: T, |
elem: T, |
||
next: Option<Box<Node<T>>>, |
next: Option<Box<Node<T>>>, |
||
}</ |
}</syntaxhighlight> |
||
However, the above example would not be suitable for a library because, first and foremost, it is private by default but simply making it public would not allow for any encapsulation. |
However, the above example would not be suitable for a library because, first and foremost, it is private by default but simply making it public would not allow for any encapsulation. |
||
< |
<syntaxhighlight lang="rust">type Link<T> = Option<Box<Node<T>>>; // Type alias |
||
pub struct List<T> { // User-facing interface for list |
pub struct List<T> { // User-facing interface for list |
||
head: Link<T>, |
head: Link<T>, |
||
Line 1,548: | Line 1,548: | ||
List { head: None } |
List { head: None } |
||
// Add other methods here |
// Add other methods here |
||
}</ |
}</syntaxhighlight> |
||
Then a separate program could utilize the basic implementation above like so: |
Then a separate program could utilize the basic implementation above like so: |
||
< |
<syntaxhighlight lang="rust">extern crate LinkedList; // Name is arbitrary here |
||
use LinkedList::List; |
use LinkedList::List; |
||
Line 1,558: | Line 1,558: | ||
let list = List::new(); |
let list = List::new(); |
||
// Do stuff |
// Do stuff |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Immutable lists that you can use with pattern matching. |
Immutable lists that you can use with pattern matching. |
||
< |
<syntaxhighlight lang="scala"> |
||
sealed trait List[+A] |
sealed trait List[+A] |
||
case class Cons[+A](head: A, tail: List[A]) extends List[A] |
case class Cons[+A](head: A, tail: List[A]) extends List[A] |
||
Line 1,572: | Line 1,572: | ||
if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*)) |
if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*)) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Basic usage |
Basic usage |
||
< |
<syntaxhighlight lang="scala"> |
||
def main(args: Array[String]): Unit = { |
def main(args: Array[String]): Unit = { |
||
val words = List("Rosetta", "Code", "Scala", "Example") |
val words = List("Rosetta", "Code", "Scala", "Example") |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
Scheme, like other Lisp dialects, has extensive support for singly-linked lists. The element of such a list is known as a ''cons-pair'', because you use the <tt>cons</tt> function to construct it: |
Scheme, like other Lisp dialects, has extensive support for singly-linked lists. The element of such a list is known as a ''cons-pair'', because you use the <tt>cons</tt> function to construct it: |
||
<lang |
<syntaxhighlight lang="scheme">(cons value next)</syntaxhighlight> |
||
The value and next-link parts of the pair can be deconstructed using the <tt>car</tt> and <tt>cdr</tt> functions, respectively: |
The value and next-link parts of the pair can be deconstructed using the <tt>car</tt> and <tt>cdr</tt> functions, respectively: |
||
< |
<syntaxhighlight lang="scheme">(car my-list) ; returns the first element of the list |
||
(cdr my-list) ; returns the remainder of the list</ |
(cdr my-list) ; returns the remainder of the list</syntaxhighlight> |
||
Each of these parts are mutable and can be set using the <tt>set-car!</tt> and <tt>set-cdr!</tt> functions, respectively: |
Each of these parts are mutable and can be set using the <tt>set-car!</tt> and <tt>set-cdr!</tt> functions, respectively: |
||
< |
<syntaxhighlight lang="scheme">(set-car! my-list new-elem) |
||
(set-cdr! my-list new-next)</ |
(set-cdr! my-list new-next)</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var node = Hash.new( |
||
data => 'say what', |
data => 'say what', |
||
next => foo_node, |
next => foo_node, |
||
); |
); |
||
node{:next} = bar_node; # mutable</ |
node{:next} = bar_node; # mutable</syntaxhighlight> |
||
=={{header|SSEM}}== |
=={{header|SSEM}}== |
||
At the machine level, an element of a linked list can be represented using two successive words of storage where the first holds an item of data and the second holds either (a) the address where the next such pair of words will be found, or (b) a special <tt>NIL</tt> address indicating that we have reached the end of the list. Here is one way in which the list <tt>'(1 2 3)</tt> could be represented in SSEM code: |
At the machine level, an element of a linked list can be represented using two successive words of storage where the first holds an item of data and the second holds either (a) the address where the next such pair of words will be found, or (b) a special <tt>NIL</tt> address indicating that we have reached the end of the list. Here is one way in which the list <tt>'(1 2 3)</tt> could be represented in SSEM code: |
||
< |
<syntaxhighlight lang="ssem">01000000000000000000000000000000 26. 2 |
||
01111000000000000000000000000000 27. 30 |
01111000000000000000000000000000 27. 30 |
||
10000000000000000000000000000000 28. 1 |
10000000000000000000000000000000 28. 1 |
||
01011000000000000000000000000000 29. 26 |
01011000000000000000000000000000 29. 26 |
||
11000000000000000000000000000000 30. 3 |
11000000000000000000000000000000 30. 3 |
||
00000000000000000000000000000000 31. 0</ |
00000000000000000000000000000000 31. 0</syntaxhighlight> |
||
Notice that the physical location of the pairs in storage can vary arbitrarily, and that (in this implementation) <tt>NIL</tt> is represented by zero. For an example showing how this list can be accessed, see [[Singly-Linked List (traversal)#SSEM]]. |
Notice that the physical location of the pairs in storage can vary arbitrarily, and that (in this implementation) <tt>NIL</tt> is represented by zero. For an example showing how this list can be accessed, see [[Singly-Linked List (traversal)#SSEM]]. |
||
Line 1,626: | Line 1,626: | ||
Here we define two [https://www.stata.com/help.cgi?m2_struct structures]: one to hold a list item, another to hold the list [https://www.stata.com/help.cgi?m2_pointer pointers]: we store both the head and the tail, in order to be able to insert an element at both ends. An empty list has both head and tail set to NULL. |
Here we define two [https://www.stata.com/help.cgi?m2_struct structures]: one to hold a list item, another to hold the list [https://www.stata.com/help.cgi?m2_pointer pointers]: we store both the head and the tail, in order to be able to insert an element at both ends. An empty list has both head and tail set to NULL. |
||
< |
<syntaxhighlight lang="stata">struct item { |
||
transmorphic scalar value |
transmorphic scalar value |
||
pointer(struct item scalar) scalar next |
pointer(struct item scalar) scalar next |
||
Line 1,633: | Line 1,633: | ||
struct list { |
struct list { |
||
pointer(struct item scalar) scalar head, tail |
pointer(struct item scalar) scalar head, tail |
||
}</ |
}</syntaxhighlight> |
||
=== Test if empty === |
=== Test if empty === |
||
< |
<syntaxhighlight lang="stata">real scalar list_empty(struct list scalar a) { |
||
return(a.head == NULL) |
return(a.head == NULL) |
||
}</ |
}</syntaxhighlight> |
||
Note that when a structure value is created, here for instance with <code>a = list()</code>, the elements are set to default values (zero real scalar, NULL pointer...). Hence, a newly created list is always empty. |
Note that when a structure value is created, here for instance with <code>a = list()</code>, the elements are set to default values (zero real scalar, NULL pointer...). Hence, a newly created list is always empty. |
||
Line 1,645: | Line 1,645: | ||
We can insert an element either before head or after tail. We can also insert after a given list item, but we must make sure the tail pointer of the list is updated if necessary. |
We can insert an element either before head or after tail. We can also insert after a given list item, but we must make sure the tail pointer of the list is updated if necessary. |
||
< |
<syntaxhighlight lang="stata">void function list_insert(struct list scalar a, transmorphic scalar x) { |
||
struct item scalar i |
struct item scalar i |
||
i.value = x |
i.value = x |
||
Line 1,680: | Line 1,680: | ||
a.tail = &i |
a.tail = &i |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=== Traversal === |
=== Traversal === |
||
Line 1,686: | Line 1,686: | ||
Here are functions to compute the list length, and to print its elements. Here we assume list elements are either strings or real numbers, but one could write a more general function. |
Here are functions to compute the list length, and to print its elements. Here we assume list elements are either strings or real numbers, but one could write a more general function. |
||
< |
<syntaxhighlight lang="stata">real scalar list_length(struct list scalar a) { |
||
real scalar n |
real scalar n |
||
pointer(struct item scalar) scalar p |
pointer(struct item scalar) scalar p |
||
Line 1,707: | Line 1,707: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=== Return nth item === |
=== Return nth item === |
||
The function returns a pointer to the nth list item. If there are not enough elements, NULL is returned. |
The function returns a pointer to the nth list item. If there are not enough elements, NULL is returned. |
||
< |
<syntaxhighlight lang="stata">pointer(struct item scalar) scalar list_get(struct list scalar a, |
||
real scalar n) { |
real scalar n) { |
||
Line 1,723: | Line 1,723: | ||
} |
} |
||
return(p) |
return(p) |
||
}</ |
}</syntaxhighlight> |
||
=== Remove and return first element === |
=== Remove and return first element === |
||
Line 1,729: | Line 1,729: | ||
The following function "pops" the first element of the list. If the list is empty, Mata will throw an error. |
The following function "pops" the first element of the list. If the list is empty, Mata will throw an error. |
||
< |
<syntaxhighlight lang="stata">transmorphic scalar list_pop(struct list scalar a) { |
||
transmorphic scalar x |
transmorphic scalar x |
||
if (a.head == NULL) { |
if (a.head == NULL) { |
||
Line 1,741: | Line 1,741: | ||
} |
} |
||
return(x) |
return(x) |
||
}</ |
}</syntaxhighlight> |
||
=== Remove and return nth element === |
=== Remove and return nth element === |
||
< |
<syntaxhighlight lang="stata">transmorphic scalar list_remove(struct list scalar a, |
||
real scalar n) { |
real scalar n) { |
||
Line 1,781: | Line 1,781: | ||
} |
} |
||
return(x) |
return(x) |
||
}</ |
}</syntaxhighlight> |
||
=== Examples === |
=== Examples === |
||
Line 1,787: | Line 1,787: | ||
Adding to the head: |
Adding to the head: |
||
< |
<syntaxhighlight lang="stata">a = list() |
||
list_insert(a, 10) |
list_insert(a, 10) |
||
list_insert(a, 20) |
list_insert(a, 20) |
||
list_insert(a, 30) |
list_insert(a, 30) |
||
list_length(a) |
list_length(a) |
||
list_show(a);</ |
list_show(a);</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,804: | Line 1,804: | ||
Adding to the tail: |
Adding to the tail: |
||
< |
<syntaxhighlight lang="stata">a = list() |
||
list_insert_end(a, 10) |
list_insert_end(a, 10) |
||
list_insert_end(a, 20) |
list_insert_end(a, 20) |
||
list_insert_end(a, 30) |
list_insert_end(a, 30) |
||
list_length(a) |
list_length(a) |
||
list_show(a);</ |
list_show(a);</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,821: | Line 1,821: | ||
Adding after an element: |
Adding after an element: |
||
< |
<syntaxhighlight lang="stata">list_insert_after(a, list_get(a, 2), 40) |
||
list_show(a);</ |
list_show(a);</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,835: | Line 1,835: | ||
Pop the first element: |
Pop the first element: |
||
<lang |
<syntaxhighlight lang="stata">list_pop(a)</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,845: | Line 1,845: | ||
=== Linked-list task === |
=== Linked-list task === |
||
< |
<syntaxhighlight lang="stata">a = list() |
||
list_insert_end(a, "A") |
list_insert_end(a, "A") |
||
list_insert_end(a, "B") |
list_insert_end(a, "B") |
||
list_insert_after(a, list_get(a, 1), "C") |
list_insert_after(a, list_get(a, 1), "C") |
||
list_show(a)</ |
list_show(a)</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,861: | Line 1,861: | ||
=== Stack behavior === |
=== Stack behavior === |
||
< |
<syntaxhighlight lang="stata">a = list() |
||
for (i = 1; i <= 4; i++) { |
for (i = 1; i <= 4; i++) { |
||
list_insert(a, i) |
list_insert(a, i) |
||
Line 1,867: | Line 1,867: | ||
while (!list_empty(a)) { |
while (!list_empty(a)) { |
||
printf("%f\n", list_pop(a)) |
printf("%f\n", list_pop(a)) |
||
}</ |
}</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,880: | Line 1,880: | ||
=== Queue behavior === |
=== Queue behavior === |
||
< |
<syntaxhighlight lang="stata">a = list() |
||
for (i = 1; i <= 4; i++) { |
for (i = 1; i <= 4; i++) { |
||
list_insert_end(a, i) |
list_insert_end(a, i) |
||
Line 1,886: | Line 1,886: | ||
while (!list_empty(a)) { |
while (!list_empty(a)) { |
||
printf("%f\n", list_pop(a)) |
printf("%f\n", list_pop(a)) |
||
}</ |
}</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 1,898: | Line 1,898: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">class Node<T>{ |
||
var data:T?=nil |
var data:T?=nil |
||
var next:Node?=nil |
var next:Node?=nil |
||
Line 1,906: | Line 1,906: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Line 1,912: | Line 1,912: | ||
{{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 |
variable content next |
||
constructor {value {list ""}} { |
constructor {value {list ""}} { |
||
Line 1,936: | Line 1,936: | ||
return $values |
return $values |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-llist}} |
{{libheader|Wren-llist}} |
||
The Node class in the above module is the element type for the LinkedList class which is a generic singly-linked list. The latter is implemented in such a way that the user does not need to deal directly with Node though for the purposes of the task we show below how instances of it can be created and manipulated. |
The Node class in the above module is the element type for the LinkedList class which is a generic singly-linked list. The latter is implemented in such a way that the user does not need to deal directly with Node 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 Node |
||
var n1 = Node.new(1) |
var n1 = Node.new(1) |
||
Line 1,947: | Line 1,947: | ||
n1.next = n2 |
n1.next = n2 |
||
System.print(["node 1", "data = %(n1.data)", "next = %(n1.next)"]) |
System.print(["node 1", "data = %(n1.data)", "next = %(n1.next)"]) |
||
System.print(["node 2", "data = %(n2.data)", "next = %(n2.next)"])</ |
System.print(["node 2", "data = %(n2.data)", "next = %(n2.next)"])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,958: | Line 1,958: | ||
------------------------------------------------------------------------------ |
------------------------------------------------------------------------------ |
||
This file will be included in the singly-linked list operation implementations |
This file will be included in the singly-linked list operation implementations |
||
< |
<syntaxhighlight lang="x86asm"> |
||
; x86_64 Linux NASM |
; x86_64 Linux NASM |
||
; Linked_List_Definition.asm |
; Linked_List_Definition.asm |
||
Line 1,972: | Line 1,972: | ||
%endif |
%endif |
||
</syntaxhighlight> |
|||
</lang> |
|||
------------------------------------------------------------------------------ |
------------------------------------------------------------------------------ |
||
{{works with|NASM}} |
{{works with|NASM}} |
||
< |
<syntaxhighlight lang="asm"> |
||
struct link |
struct link |
||
.next: resd 1 |
.next: resd 1 |
||
.data: resd 1 |
.data: resd 1 |
||
endstruc |
endstruc |
||
</syntaxhighlight> |
|||
</lang> |
|||
Of course, ASM not natively having structures we can simply do.. |
Of course, ASM not natively having structures we can simply do.. |
||
< |
<syntaxhighlight lang="asm"> |
||
link resb 16 |
link resb 16 |
||
</syntaxhighlight> |
|||
</lang> |
|||
Which would reserve 16 bytes(2 dwords). We could just simply think of it in the form of a structure.<br><br> |
Which would reserve 16 bytes(2 dwords). We could just simply think of it in the form of a structure.<br><br> |
||
{{works with|MASM}} |
{{works with|MASM}} |
||
< |
<syntaxhighlight lang="asm"> |
||
link struct |
link struct |
||
next dd ? |
next dd ? |
||
data dd ? |
data dd ? |
||
link ends |
link ends |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{works with|FASM}} |
{{works with|FASM}} |
||
< |
<syntaxhighlight lang="asm">struc link next,data |
||
{ |
{ |
||
.next dd next |
.next dd next |
||
.data dd data |
.data dd data |
||
}</ |
}</syntaxhighlight> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">def \Node\ Link, Data; \linked list element definition |
||
int Node, List, N; |
int Node, List, N; |
||
def IntSize = 4; \number of bytes in an integer |
def IntSize = 4; \number of bytes in an integer |
||
Line 2,019: | Line 2,019: | ||
Node:= Node(Link); \move to next node |
Node:= Node(Link); \move to next node |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,027: | Line 2,027: | ||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
< |
<syntaxhighlight lang="zig">const std = @import("std"); |
||
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); |
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); |
||
Line 2,068: | Line 2,068: | ||
} |
} |
||
}; |
}; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Lists are a core element in zkl, both mutable and immutable. They are heterogeneous and can hold any object. They can be recursive. |
Lists are a core element in zkl, both mutable and immutable. They are heterogeneous and can hold any object. They can be recursive. |
||
< |
<syntaxhighlight lang="zkl">List(1,"two",3.14); L(1,"two",3.14); |
||
ROList(fcn{"foobar"}); T('+);</ |
ROList(fcn{"foobar"}); T('+);</syntaxhighlight> |
||
{{omit from|GUISS}} |
{{omit from|GUISS}} |