Singly-linked list/Element definition: Difference between revisions

 

{{Template:See also lists}}

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

C

</pre>

 

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

<pre>(8 6 7 5 3 0 9)</pre>

 

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

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

 

def empty implements LinkedListStamp {

to null() { return true }

}

return link

=={{header|Elena}}==

{

 

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

The Icon version works in both Icon and Unicon. Unicon also permits a class-based definition.

 

 

record Node (value, successor)

 

 

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

 

proc newNode[T](data: T): Node[T] =

Node[T](data: data)

 

 

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

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

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

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

Node:= List; \traverse the linked list

 

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