Singly-linked list/Element definition: Difference between revisions

=={{header|360 Assembly}}==

The program uses DSECT and USING pseudo instruction to define a node.

LISTSINA CSECT

USING LISTSINA,R13 base register

NEXT DS A

YREGS

{{out}}

<pre>

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.

 

;The first node has a value of #$77, the second, #$99.

;create first node

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

 

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program defList.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

 

=={{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)))

 

Output:

 

=={{header|Action!}}==

 

TYPE ListNode=[

BYTE data

{{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

}

}

 

=={{header|Ada}}==

 

type Link_Access is access Link;

type Link is record

Next : Link_Access := null;

Data : Integer;

 

=={{header|ALGOL 68}}==

{{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]}}

CO REQUIRES:

MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked #

 

PROC obj nextlink free = (REF OBJNEXTLINK free)VOID:

 

=={{header|ALGOL W}}==

record ListI ( integer iValue; reference(ListI) next );

 

 

% create a list of integers %

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program defList.s */

pop {r0,r1,r2,r7,lr} @ restaur registers

bx lr @ return

 

=={{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’. *)

case+ lst of

| rclist_vt_nil () => ()

 

=={{header|AutoHotkey}}==

 

=={{header|AWK}}==

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

return linkAndValue[part]

}

 

=={{header|Axe}}==

r₂→{r₁}ʳ

0→{r₁+2}ʳ

Lbl VALUE

{r₁}ʳ

 

{{works with|BBC BASIC for Windows}}

 

=={{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=)

Example of use:

& new$link:?link2

& first thing:?(link1..data)

& secundus:?(link2..data)

& '$link2:(=?(link1..next))

The last line returns

<pre>secundus</pre>

 

=={{header|C}}==

struct link *next;

int data;

 

=={{header|C sharp|C#}}==

 

{

public int Value { get; set; }

Next = next;

}

 

A generic version:

{

public T Value { get; set; }

Next = next;

}

 

The most C-like possible version is basically C.

public link* next;

public int data;

 

=={{header|C++}}==

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}}==

 

 

=={{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.

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;

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.

 

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 ;

 

=={{header|Diego}}==

 

add_struct(link)_arg({link},next,{int},data);

add_link(primeNumbers)_arg([],2)_link()_arg([],3)_link()_arg([],5)_link()_arg(null,7);

 

 

=={{header|E}}==

 

def empty implements LinkedListStamp {

to null() { return true }

}

return link

 

=={{header|Elena}}==

{

constructor(int item, Link next)

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:

new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ).

For the whole module see [[Singly-linked_list/Element_insertion]]

 

=={{header|Factor}}==

 

: <linked-list> ( data -- linked-list )

 

=={{header|Fantom}}==

 

class Node

{

}

}

 

=={{header|Forth}}==

Idiomatically,

 

: push ( n -- )

 

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 ;

 

 

: .numbers ( list -- )

 

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.

=={{header|Fortran}}==

In ISO Fortran 95 or later:

real :: data

type( node ), pointer :: next => null()

!. . . .

!

 

=={{header|FreeBASIC}}==

n as integer

nxt as ll_int ptr

 

=={{header|Go}}==

Data interface{}

Next *Ele

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)

 

 

Output:

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|Icon}}===

 

record Node (value, successor)

 

==={{header|Unicon}}===

 

class Node (value, successor)

initially (value, successor)

self.successor := successor

end

 

With either the record or the class definition, new linked lists are easily created and manipulated:

 

procedure main ()

n := Node(1, Node (2))

write (n.successor.value)

end

 

=={{header|J}}==

However, for illustrative purposes:

 

 

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.

To create such a list with one element which contains number 42, we can do the following:

 

list

 

Now list contains one item, with index of the next item and value.

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

+-+---------+

|_|some text|

 

=={{header|Java}}==

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;

}

 

 

=={{header|jq}}==

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);

 

else ($x.item) == ($y.item)

and equal_singly_linked_lists($x.next; $y.next)

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

 

struct EmptyNode{T} <: AbstractNode{T} end

pop!(lst) # 3

pop!(lst) # 2

 

=={{header|Kotlin}}==

 

class Node<T: Number>(var data: T, var next: Node<T>? = null) {

val n = Node(1, Node(2, Node(3)))

println(n)

 

{{out}}

1 -> 2 -> 3

</pre>

 

=={{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

 

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.

 

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

 

=={{header|Modula-2}}==

 

Link = POINTER TO LinkRcd;

LinkRcd = RECORD

Next: Link;

Data: INTEGER

 

=={{header|Modula-3}}==

Link = REF LinkRcd;

LinkRcd = RECORD

Next: Link;

Data: INTEGER

 

=={{header|Nanoquery}}==

The simplest version in Nanoquery is similar to the C version:

declare data

declare next

 

Like Java, it is possible to add a constructor that allows us to set the values on initialization.

declare data

declare next

this.next = next

end

 

This allows us to define an entire list in a single (albeit confusing) line of source.

 

=={{header|Nim}}==

 

Node[T] = ref object

next: Node[T]

for i in 1..5: list.append(i)

for i in 6..10: list.prepend(i)

 

{{out}}

=={{header|Objective-C}}==

 

 

@interface RCListElement<T> : NSObject

datum = d;

}

 

=={{header|OCaml}}==

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|Oforth}}==

 

 

=={{header|ooRexx}}==

 

The simplest ooRexx version is similar in form to the Java or C++ versions:

list = .linkedlist~new

index = list~insert("abc") -- insert a first item, keeping the index

 

 

 

A link element can hold a reference to any ooRexx object.

=={{header|Pascal}}==

 

PLink = ^TLink;

TLink = record

FNext: PLink;

FData: integer;

 

=={{header|Perl}}==

 

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,

);

 

=={{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),

 

=={{header|PL/I}}==

declare 1 node based (p),

2 value fixed,

2 link pointer;

 

=={{header|Pop11}}==

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

l1 -> back(l2);

;;; Print l2

 

If however one wants to definite equivalent user-defined type, one can do this:

 

define :class ListNode;

slot value = [];

;;; of l1

consListNode(2, []) -> next(l1);

 

=={{header|PureBasic}}==

 

*next.MyData

Value.i

 

=={{header|Python}}==

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!

while cursor:

yield cursor.value

 

'''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.

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.

 

#lang racket

(mcons 1 (mcons 2 (mcons 3 '()))) ; a mutable list

 

=={{header|Raku}}==

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:

 

 

However, because this is not the primary purpose of the <tt>Pair</tt> type, it suffers from the following limitations:

For more flexibility, one would create a custom type:

 

has $.value is rw;

has Cell $.next is rw;

sub cons ($value, $next) { Cell.new(:$value, :$next) }

 

 

=={{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. */

@..y=n /*set a locator pointer to self. */

@.max_width=max(@.max_width,length(y)) /*set maximum width of any value.*/

'''output'''

<pre>

=={{header|Ruby}}==

 

attr_accessor :value, :succ

 

end

 

 

=={{header|Run BASIC}}==

link = 10

 

=={{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>,

List { head: None }

// Add other methods here

 

Then a separate program could utilize the basic implementation above like so:

 

use LinkedList::List;

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]

if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*))

}

 

Basic usage

 

def main(args: Array[String]): Unit = {

val words = List("Rosetta", "Code", "Scala", "Example")

}

 

=={{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:

 

The value and next-link parts of the pair can be deconstructed using the <tt>car</tt> and <tt>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:

 

=={{header|Sidef}}==

data => 'say what',

next => foo_node,

);

 

 

=={{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

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]].

 

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

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.

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

a.tail = &i

}

 

=== Traversal ===

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

}

}

 

=== 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) {

}

return(p)

 

=== Remove and return first element ===

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) {

}

return(x)

 

=== Remove and return nth element ===

 

real scalar n) {

}

return(x)

 

=== Examples ===

Adding to the head:

 

list_insert(a, 10)

list_insert(a, 20)

list_insert(a, 30)

list_length(a)

 

'''Output'''

Adding to the tail:

 

list_insert_end(a, 10)

list_insert_end(a, 20)

list_insert_end(a, 30)

list_length(a)

 

'''Output'''

Adding after an element:

 

 

'''Output'''

Pop the first element:

 

 

'''Output'''

=== Linked-list task ===

 

list_insert_end(a, "A")

list_insert_end(a, "B")

list_insert_after(a, list_get(a, 1), "C")

 

'''Output'''

=== Stack behavior ===

 

for (i = 1; i <= 4; i++) {

list_insert(a, i)

while (!list_empty(a)) {

printf("%f\n", list_pop(a))

 

'''Output'''

=== Queue behavior ===

 

for (i = 1; i <= 4; i++) {

list_insert_end(a, i)

while (!list_empty(a)) {

printf("%f\n", list_pop(a))

 

'''Output'''

 

=={{header|Swift}}==

}

}

 

=={{header|Tcl}}==

 

{{Works with|Tcl|8.6}} or {{libheader|TclOO}}

variable content next

constructor {value {list ""}} {

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)

n1.next = n2

System.print(["node 1", "data = %(n1.data)", "next = %(n1.next)"])

 

{{out}}

------------------------------------------------------------------------------

This file will be included in the singly-linked list operation implementations

; x86_64 Linux NASM

; Linked_List_Definition.asm

 

%endif

------------------------------------------------------------------------------

 

{{works with|NASM}}

 

struct link

.next: resd 1

.data: resd 1

endstruc

Of course, ASM not natively having structures we can simply do..

link resb 16

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

{{works with|FASM}}

{

.next dd next

.data dd data

 

=={{header|XPL0}}==

int Node, List, N;

def IntSize = 4; \number of bytes in an integer

Node:= Node(Link); \move to next node

];

 

{{out}}

 

=={{header|Zig}}==

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);

}

};

 

=={{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.

 

{{omit from|GUISS}}