Singly-linked list/Element definition: Difference between revisions
PascalABC.NET
(→{{header|Diego}}: Added Diego entry) |
(PascalABC.NET) |
||
(13 intermediate revisions by 11 users not shown) | |||
Line 5:
=={{header|360 Assembly}}==
The program uses DSECT and USING pseudo instruction to define a node.
<
LISTSINA CSECT
USING LISTSINA,R13 base register
Line 91:
NEXT DS A
YREGS
END LISTSINA</
{{out}}
<pre>
Line 98:
C
</pre>
=={{header|6502 Assembly}}==
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.
;create first node
LDA #$77
STA $20
LDA #$40
STA $21
LDA #$00
STA $22
;create second node
LDA #$99
STA $40
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 $42 </syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program defList.s */
Line 159 ⟶ 179:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{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.
<
(next (list 6 7 5 3 0 9)))
(cons elem next))</
Output:
Line 172 ⟶ 192:
=={{header|Action!}}==
<
TYPE ListNode=[
BYTE data
PTR nxt]</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Singly-linked_list_element_definition.png Screenshot from Atari 8-bit computer]
=={{header|ActionScript}}==
<
{
public class Node
Line 193 ⟶ 213:
}
}
}</
=={{header|Ada}}==
<
type Link_Access is access Link;
type Link is record
Next : Link_Access := null;
Data : Integer;
end record;</
=={{header|ALGOL 68}}==
Line 208 ⟶ 228:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.7 algol68g-2.7].}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
'''File: prelude/single_link.a68'''<
CO REQUIRES:
MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked #
Line 222 ⟶ 242:
PROC obj nextlink free = (REF OBJNEXTLINK free)VOID:
next OF free := obj stack empty # give the garbage collector a BIG hint #</
=={{header|ALGOL W}}==
<
record ListI ( integer iValue; reference(ListI) next );
Line 232 ⟶ 252:
% create a list of integers %
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program defList.s */
Line 305 ⟶ 325:
pop {r0,r1,r2,r7,lr} @ restaur registers
bx lr @ return
</syntaxhighlight>
=={{header|ATS}}==
<
(The ‘@’ means it doesn’t have to be the size of a pointer.
You can read {0 <= n} as ‘for all non-negative n’. *)
Line 327 ⟶ 347:
case+ lst of
| rclist_vt_nil () => ()
| rclist_vt_cons _ => ()</
=={{header|AutoHotkey}}==
<
element_next = element2 ; link to next element</
=={{header|AWK}}==
Line 337 ⟶ 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.
<
BEGIN {
NIL = 0
Line 361 ⟶ 381:
return linkAndValue[part]
}
</syntaxhighlight>
=={{header|Axe}}==
<
r₂→{r₁}ʳ
0→{r₁+2}ʳ
Line 376 ⟶ 396:
Lbl VALUE
{r₁}ʳ
Return</
=={{header|
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
</syntaxhighlight>
=={{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.
<
(next=)
(data=)</
Example of use:
<
& new$link:?link2
& first thing:?(link1..data)
& secundus:?(link2..data)
& '$link2:(=?(link1..next))
& !(link1..next..data)</
The last line returns
<pre>secundus</pre>
=={{header|C}}==
<
struct link *next;
int data;
};</
=={{header|C sharp|C#}}==
<
{
public int Value { get; set; }
Line 417 ⟶ 438:
Next = next;
}
}</
A generic version:
<
{
public T Value { get; set; }
Line 430 ⟶ 451:
Next = next;
}
}</
The most C-like possible version is basically C.
<
public link* next;
public int data;
};</
=={{header|C++}}==
Line 442 ⟶ 463:
The simplest C++ version looks basically like the C version:
<
{
link* next;
int data;
};</
Initialization of links on the heap can be simplified by adding a constructor:
<
{
link* next;
int data;
link(int a_data, link* a_next = 0): next(a_next), data(a_data) {}
};</
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement:
<
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).
<
{
link* next;
T data;
link(T a_data, link* a_next = 0): next(a_next), data(a_data) {}
};</
Note that the generic version works for any type, not only integral types.
=={{header|Clean}}==
<
:: Link t = { next :: Maybe (Link t), data :: t }</
=={{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).
<
Note: this is an immutable data structure. With cons you are '''cons'''tructing a new seq.
Line 488 ⟶ 509:
The built-in <code>cons</code> type is used to construct linked lists. Using another type would be unidiomatic and inefficient.
<
=={{header|D}}==
Generic template-based node element.
<
T data;
typeof(this)* next;
Line 501 ⟶ 522:
alias SLinkedNode!int N;
N* n = new N(10);
}</
Also the Phobos library contains a singly-linked list, std.container.SList. Tango contains tango.util.collection.LinkSeq.
Line 508 ⟶ 529:
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.
<
pOneWayList = ^OneWayList;
OneWayList = record
pData : pointer ;
Next : pOneWayList ;
end;</
=={{header|Diego}}==
<
add_struct(link)_arg({link},next,{int},data);
Line 522 ⟶ 543:
add_link(primeNumbers)_arg([],2)_link()_arg([],3)_link()_arg([],5)_link()_arg(null,7);
reset_namespace[];</
=={{header|E}}==
<
def empty implements LinkedListStamp {
to null() { return true }
Line 538 ⟶ 559:
}
return link
}</
=={{header|Elena}}==
ELENA 6.x
<syntaxhighlight lang="elena">class Link
{
constructor(int item, Link next)
Line 551 ⟶ 573:
Next := next
}
}</
=={{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:
<syntaxhighlight lang="erlang">
new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ).
</syntaxhighlight>
For the whole module see [[Singly-linked_list/Element_insertion]]
=={{header|Factor}}==
<syntaxhighlight lang="text">TUPLE: linked-list data next ;
: <linked-list> ( data -- linked-list )
linked-list new swap >>data ;</
=={{header|Fantom}}==
<
class Node
{
Line 580 ⟶ 602:
}
}
</syntaxhighlight>
=={{header|Forth}}==
Line 586 ⟶ 608:
Idiomatically,
<
: push ( n -- )
here swap numbers , , to numbers ;</
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:
<
0 swap begin dup while 1 under+ @ repeat drop ;
Line 599 ⟶ 621:
: .numbers ( list -- )
begin dup while dup head . @ repeat drop ;</
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 605 ⟶ 627:
=={{header|Fortran}}==
In ISO Fortran 95 or later:
<
real :: data
type( node ), pointer :: next => null()
Line 612 ⟶ 634:
!. . . .
!
type( node ) :: head</
=={{header|FreeBASIC}}==
<
n as integer
nxt as ll_int ptr
end type</
=={{header|Go}}==
<
Data interface{}
Next *Ele
Line 638 ⟶ 660:
func (e *Ele) String() string {
return fmt.Sprintf("Ele: %v", e.Data)
}</
=={{header|Groovy}}==
Solution:
<
Object payload
ListNode next
String toString() { "${payload} -> ${next}" }
}</
Test:
<
n1.next = new ListNode(payload:88)
println n1</
Output:
Line 663 ⟶ 685:
An equivalent declaration for such a list type without the special syntax would look like this:
<
A declaration like the one required in the task, with an integer as element type and a mutable link, would be
<
but that would be really awkward to use.
Line 677 ⟶ 699:
==={{header|Icon}}===
<syntaxhighlight lang="icon">
record Node (value, successor)
</syntaxhighlight>
==={{header|Unicon}}===
<syntaxhighlight lang="unicon">
class Node (value, successor)
initially (value, successor)
Line 689 ⟶ 711:
self.successor := successor
end
</syntaxhighlight>
With either the record or the class definition, new linked lists are easily created and manipulated:
<syntaxhighlight lang="icon">
procedure main ()
n := Node(1, Node (2))
Line 699 ⟶ 721:
write (n.successor.value)
end
</syntaxhighlight>
=={{header|J}}==
Line 707 ⟶ 729:
However, for illustrative purposes:
<
list</
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 714 ⟶ 736:
To create such a list with one element which contains number 42, we can do the following:
<
list
_ 42</
Now list contains one item, with index of the next item and value.
Line 722 ⟶ 744:
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:
<
list
list=: ,: (<_) , <'some text' NB. creates list with 1 item
Line 728 ⟶ 750:
+-+---------+
|_|some text|
+-+---------+</
=={{header|Java}}==
Line 734 ⟶ 756:
The simplest Java version looks basically like the C++ version:
<
{
Link next;
int data;
}</
Initialization of links on the heap can be simplified by adding a constructor:
<
{
Link next;
int data;
Link(int a_data, Link a_next) { next = a_next; data = a_data; }
}</
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement:
<
{{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).
<
{
Link<T> next;
T data;
Link(T a_data, Link<T> a_next) { next = a_next; data = a_data; }
}</
=={{header|JavaScript}}==
<
this._value = value;
this._next = next;
Line 793 ⟶ 815:
}
var head = createLinkedListFromArray([10,20,30,40]);</
=={{header|jq}}==
Line 820 ⟶ 842:
Note that according to these principles, the JSON value `null` does
not represent a SLL, and JSON representatives of SLLs may have additional keys.
<
type == "object" and .next == null and (has("item")|not);
Line 837 ⟶ 859:
else ($x.item) == ($y.item)
and equal_singly_linked_lists($x.next; $y.next)
end;
# insert $x into the front of the SLL
def insert($x):
if is_empty_singly_linked_list then {item: $x, next: null}
else .next |= new($x; .)
end;
</syntaxhighlight>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
struct EmptyNode{T} <: AbstractNode{T} end
Line 900 ⟶ 929:
pop!(lst) # 3
pop!(lst) # 2
pop!(lst) # 1</
=={{header|Kotlin}}==
<
class Node<T: Number>(var data: T, var next: Node<T>? = null) {
Line 920 ⟶ 949:
val n = Node(1, Node(2, Node(3)))
println(n)
}</
{{out}}
Line 926 ⟶ 955:
1 -> 2 -> 3
</pre>
=={{header|Lang}}==
<syntaxhighlight lang="lang">
&Node = {
$next
$data
}
</syntaxhighlight>
=={{header|Logo}}==
As with other list-based languages, simple lists are represented easily in Logo.
<
first list ; get the data
butfirst list ; get the remainder
bf list ; contraction for "butfirst"</
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.
<
.setbf list remainder</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
-> {x}</
=={{header|MiniScript}}==
Implementing linked lists in MiniScript is an academic exercise. For practical applications, use the built-in list type.
<syntaxhighlight lang="miniscript">
Node = {"item": null, "next": null}
Node.init = function(item)
node = new Node
node.item = item
return node
end function
LinkedList = {"head": null, "tail": null}
LinkedList.append = function(item)
newNode = Node.init(item)
if self.head == null then
self.head = newNode
self.tail = self.head
else
self.tail.next = newNode
self.tail = self.tail.next
end if
end function
LinkedList.insert = function(aftItem, item)
newNode = Node.init(item)
cursor = self.head
while cursor.item != aftItem
print cursor.item
cursor = cursor.next
end while
newNode.next = cursor.next
cursor.next = newNode
end function
LinkedList.traverse = function
cursor = self.head
while cursor != null
// do stuff
print cursor.item
cursor = cursor.next
end while
end function
test = new LinkedList
test.append("A")
test.append("B")
test.insert("A","C")
test.traverse
</syntaxhighlight>
=={{header|Modula-2}}==
<
Link = POINTER TO LinkRcd;
LinkRcd = RECORD
Next: Link;
Data: INTEGER
END;</
=={{header|Modula-3}}==
<
Link = REF LinkRcd;
LinkRcd = RECORD
Next: Link;
Data: INTEGER
END;</
=={{header|Nanoquery}}==
The simplest version in Nanoquery is similar to the C version:
<
declare data
declare next
end</
Like Java, it is possible to add a constructor that allows us to set the values on initialization.
<
declare data
declare next
Line 978 ⟶ 1,065:
this.next = next
end
end</
This allows us to define an entire list in a single (albeit confusing) line of source.
<
=={{header|Nim}}==
<syntaxhighlight lang="nim">
import std/strutils # for join
type
Node[T] = ref object
next: Node[T]
Line 1,030 ⟶ 1,119:
for i in 1..5: list.append(i)
for i in 6..10: list.prepend(i)
echo "List: ", $list
</syntaxhighlight>
{{out}}
Line 1,037 ⟶ 1,127:
=={{header|Objective-C}}==
<
@interface RCListElement<T> : NSObject
Line 1,069 ⟶ 1,159:
datum = d;
}
@end</
=={{header|OCaml}}==
Line 1,077 ⟶ 1,167:
An equivalent declaration for such a list type without the special syntax would look like this:
<
A declaration like the one required in the task, with an integer as element type and a mutable link, would be
<
but that would be really awkward to use.
=={{header|Odin}}==
<syntaxhighlight lang="odin">Node :: struct {
data: rune,
next: ^Node,
}</syntaxhighlight>
=={{header|Oforth}}==
<
=={{header|ooRexx}}==
The simplest ooRexx version is similar in form to the Java or C++ versions:
<syntaxhighlight lang="oorexx">
list = .linkedlist~new
index = list~insert("abc") -- insert a first item, keeping the index
Line 1,228 ⟶ 1,325:
</syntaxhighlight>
A link element can hold a reference to any ooRexx object.
Line 1,234 ⟶ 1,331:
=={{header|Pascal}}==
<
PLink = ^TLink;
TLink = record
FNext: PLink;
FData: integer;
end;</
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
type Node<T> = auto class
data: T;
next: Node<T>;
end;
</syntaxhighlight>
=={{header|Perl}}==
Line 1,245 ⟶ 1,350:
However, if all you got is an algorithm in a foreign language, you can use references to accomplish the translation.
<
data => 'say what',
next => \%foo_node,
);
$node{next} = \%bar_node; # mutable</
=={{header|Phix}}==
In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use something like
<!--<
<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;">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>
<!--</
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),
Line 1,284 ⟶ 1,389:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
declare 1 node based (p),
2 value fixed,
2 link pointer;
</syntaxhighlight>
=={{header|Pop11}}==
Line 1,294 ⟶ 1,399:
List are built in into Pop11, so normally on would just use them:
<
lvars l1 = [1 2 three 'four'];
;;; Allocate a single list node, with value field 1 and the link field
Line 1,308 ⟶ 1,413:
l1 -> back(l2);
;;; Print l2
l2 =></
If however one wants to definite equivalent user-defined type, one can do this:
<
define :class ListNode;
slot value = [];
Line 1,327 ⟶ 1,432:
;;; of l1
consListNode(2, []) -> next(l1);
l1 =></
=={{header|PureBasic}}==
<
*next.MyData
Value.i
EndStructure</
=={{header|Python}}==
Line 1,340 ⟶ 1,445:
The Node class implements also iteration for more Pythonic iteration over linked lists.
<
"""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!
Line 1,366 ⟶ 1,471:
while cursor:
yield cursor.value
cursor = cursor.next</
'''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,374 ⟶ 1,479:
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
(mcons 1 (mcons 2 (mcons 3 '()))) ; a mutable list
</syntaxhighlight>
=={{header|Raku}}==
Line 1,386 ⟶ 1,491:
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:
<syntaxhighlight lang="raku"
However, because this is not the primary purpose of the <tt>Pair</tt> type, it suffers from the following limitations:
Line 1,398 ⟶ 1,503:
For more flexibility, one would create a custom type:
<syntaxhighlight lang="raku"
has $.value is rw;
has Cell $.next is rw;
Line 1,407 ⟶ 1,512:
sub cons ($value, $next) { Cell.new(:$value, :$next) }
my $list = cons 10, (cons 20, (cons 30, Nil));</
=={{header|REXX}}==
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).
<
@.=0 /*define a null linked list. */
call set@ 3 /*linked list: 12 Proth Primes. */
Line 1,449 ⟶ 1,554:
@..y=n /*set a locator pointer to self. */
@.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/
return /*return to invoker of this sub. */</
'''output'''
<pre>
Line 1,470 ⟶ 1,575:
=={{header|Ruby}}==
<
attr_accessor :value, :succ
Line 1,497 ⟶ 1,602:
end
list = ListNode.from_array([1,2,3,4])</
=={{header|Run BASIC}}==
<
link = 10
dim node{data,link} </
=={{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.
<
elem: T,
next: Option<Box<Node<T>>>,
}</
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.
<
pub struct List<T> { // User-facing interface for list
head: Link<T>,
Line 1,528 ⟶ 1,633:
List { head: None }
// Add other methods here
}</
Then a separate program could utilize the basic implementation above like so:
<
use LinkedList::List;
Line 1,538 ⟶ 1,643:
let list = List::new();
// Do stuff
}</
=={{header|Scala}}==
Immutable lists that you can use with pattern matching.
<
sealed trait List[+A]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
Line 1,552 ⟶ 1,657:
if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*))
}
</syntaxhighlight>
Basic usage
<
def main(args: Array[String]): Unit = {
val words = List("Rosetta", "Code", "Scala", "Example")
}
</syntaxhighlight>
=={{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:
<syntaxhighlight lang
The value and next-link parts of the pair can be deconstructed using the <tt>car</tt> and <tt>cdr</tt> functions, respectively:
<
(cdr my-list) ; returns the remainder of the list</
Each of these parts are mutable and can be set using the <tt>set-car!</tt> and <tt>set-cdr!</tt> functions, respectively:
<
(set-cdr! my-list new-next)</
=={{header|Sidef}}==
<
data => 'say what',
next => foo_node,
);
node{:next} = bar_node; # mutable</
=={{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:
<
01111000000000000000000000000000 27. 30
10000000000000000000000000000000 28. 1
01011000000000000000000000000000 29. 26
11000000000000000000000000000000 30. 3
00000000000000000000000000000000 31. 0</
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,606 ⟶ 1,711:
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.
<
transmorphic scalar value
pointer(struct item scalar) scalar next
Line 1,613 ⟶ 1,718:
struct list {
pointer(struct item scalar) scalar head, tail
}</
=== Test if empty ===
<
return(a.head == NULL)
}</
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,625 ⟶ 1,730:
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.
<
struct item scalar i
i.value = x
Line 1,660 ⟶ 1,765:
a.tail = &i
}
}</
=== Traversal ===
Line 1,666 ⟶ 1,771:
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.
<
real scalar n
pointer(struct item scalar) scalar p
Line 1,687 ⟶ 1,792:
}
}
}</
=== Return nth item ===
The function returns a pointer to the nth list item. If there are not enough elements, NULL is returned.
<
real scalar n) {
Line 1,703 ⟶ 1,808:
}
return(p)
}</
=== Remove and return first element ===
Line 1,709 ⟶ 1,814:
The following function "pops" the first element of the list. If the list is empty, Mata will throw an error.
<
transmorphic scalar x
if (a.head == NULL) {
Line 1,721 ⟶ 1,826:
}
return(x)
}</
=== Remove and return nth element ===
<
real scalar n) {
Line 1,761 ⟶ 1,866:
}
return(x)
}</
=== Examples ===
Line 1,767 ⟶ 1,872:
Adding to the head:
<
list_insert(a, 10)
list_insert(a, 20)
list_insert(a, 30)
list_length(a)
list_show(a);</
'''Output'''
Line 1,784 ⟶ 1,889:
Adding to the tail:
<
list_insert_end(a, 10)
list_insert_end(a, 20)
list_insert_end(a, 30)
list_length(a)
list_show(a);</
'''Output'''
Line 1,801 ⟶ 1,906:
Adding after an element:
<
list_show(a);</
'''Output'''
Line 1,815 ⟶ 1,920:
Pop the first element:
<syntaxhighlight lang
'''Output'''
Line 1,825 ⟶ 1,930:
=== Linked-list task ===
<
list_insert_end(a, "A")
list_insert_end(a, "B")
list_insert_after(a, list_get(a, 1), "C")
list_show(a)</
'''Output'''
Line 1,841 ⟶ 1,946:
=== Stack behavior ===
<
for (i = 1; i <= 4; i++) {
list_insert(a, i)
Line 1,847 ⟶ 1,952:
while (!list_empty(a)) {
printf("%f\n", list_pop(a))
}</
'''Output'''
Line 1,860 ⟶ 1,965:
=== Queue behavior ===
<
for (i = 1; i <= 4; i++) {
list_insert_end(a, i)
Line 1,866 ⟶ 1,971:
while (!list_empty(a)) {
printf("%f\n", list_pop(a))
}</
'''Output'''
Line 1,878 ⟶ 1,983:
=={{header|Swift}}==
<
var data: T
var next: Node? = nil
init(input: T){
data = input
next = nil
}
}
</syntaxhighlight>
=={{header|Tcl}}==
Line 1,892 ⟶ 1,997:
{{Works with|Tcl|8.6}} or {{libheader|TclOO}}
<
variable content next
constructor {value {list ""}} {
Line 1,916 ⟶ 2,021:
return $values
}
}</
=={{header|Wren}}==
{{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.
<
var n1 = Node.new(1)
Line 1,927 ⟶ 2,032:
n1.next = n2
System.print(["node 1", "data = %(n1.data)", "next = %(n1.next)"])
System.print(["node 2", "data = %(n2.data)", "next = %(n2.next)"])</
{{out}}
Line 1,938 ⟶ 2,043:
------------------------------------------------------------------------------
This file will be included in the singly-linked list operation implementations
<
; x86_64 Linux NASM
; Linked_List_Definition.asm
Line 1,952 ⟶ 2,057:
%endif
</syntaxhighlight>
------------------------------------------------------------------------------
{{works with|NASM}}
<
struct link
.next: resd 1
.data: resd 1
endstruc
</syntaxhighlight>
Of course, ASM not natively having structures we can simply do..
<
link resb 16
</syntaxhighlight>
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}}
<
link struct
next dd ?
data dd ?
link ends
</syntaxhighlight>
{{works with|FASM}}
<
{
.next dd next
.data dd data
}</
=={{header|XPL0}}==
<
int Node, List, N;
def IntSize = 4; \number of bytes in an integer
Line 1,999 ⟶ 2,104:
Node:= Node(Link); \move to next node
];
]</
{{out}}
Line 2,007 ⟶ 2,112:
=={{header|Zig}}==
<
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
Line 2,048 ⟶ 2,153:
}
};
}</
=={{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.
<
ROList(fcn{"foobar"}); T('+);</
{{omit from|GUISS}}
|