Singly-linked list/Element definition: Difference between revisions

From Rosetta Code
Content added Content deleted
m (C# Changed public fields to properties)
(Single Linked List element defination of generic type)
Line 1: Line 1:
class Node<T>{
{{task|Data Structures}}Define the data structure for a [[singly-linked list]] element. Said element should contain a data member capable of holding a numeric value, and the link to the next element should be mutable.
var data:T?=nil

var next:Node?=nil
{{Template:See also lists}}
init(input:T){
=={{header|ACL2}}==
data=input
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=nil

<lang Lisp>(let ((elem 8)
(next (list 6 7 5 3 0 9)))
(cons elem next))</lang>

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

=={{header|ActionScript}}==
<lang ActionScript>package
{
public class Node
{
public var data:Object = null;
public var link:Node = null;
public function Node(obj:Object)
{
data = obj;
}
}
}</lang>
=={{header|Ada}}==

<lang ada>type Link;
type Link_Access is access Link;
type Link is record
Next : Link_Access := null;
Data : Integer;
end record;</lang>

=={{header|ALGOL 68}}==
{{works with|ALGOL 68|Revision 1}}
{{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'''<lang algol68># -*- coding: utf-8 -*- #
CO REQUIRES:
MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked #
END CO

MODE OBJNEXTLINK = STRUCT(
REF OBJNEXTLINK next,
OBJVALUE value # ... etc. required #
);

PROC obj nextlink new = REF OBJNEXTLINK:
HEAP OBJNEXTLINK;

PROC obj nextlink free = (REF OBJNEXTLINK free)VOID:
next OF free := obj stack empty # give the garbage collector a BIG hint #</lang>'''See also:''' [[Stack#ALGOL_68|Stack]]

=={{header|ALGOL W}}==
<lang algolw> % record type to hold a singly linked list of integers %
record ListI ( integer iValue; reference(ListI) next );

% declare a variable to hold a list %
reference(ListI) head;

% create a list of integers %
head := ListI( 1701, ListI( 9000, ListI( 42, ListI( 90210, null ) ) ) );</lang>

=={{header|AutoHotkey}}==
<lang AutoHotkey>element = 5 ; data
element_next = element2 ; link to next element</lang>

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

<lang awk>
BEGIN {
NIL = 0
HEAD = 1
LINK = 1
VALUE = 2
delete list
initList()
}

function initList() {
delete list
list[HEAD] = makeNode(NIL, NIL)
}

function makeNode(link, value) {
return link SUBSEP value
}

function getNode(part, nodePtr, linkAndValue) {
split(list[nodePtr], linkAndValue, SUBSEP)
return linkAndValue[part]
}
</lang>

=={{header|Axe}}==
<lang axe>Lbl LINK
r₂→{r₁}ʳ
0→{r₁+2}ʳ
r₁
Return
Lbl NEXT
{r₁+2}ʳ
Return
Lbl VALUE
{r₁}ʳ
Return</lang>

=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<lang bbcbasic> DIM node{pNext%, iData%}
</lang>

=={{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.
<lang bracmat>link =
(next=)
(data=)</lang>
Example of use:
<lang bracmat> new$link:?link1
& new$link:?link2
& first thing:?(link1..data)
& secundus:?(link2..data)
& '$link2:(=?(link1..next))
& !(link1..next..data)</lang>
The last line returns
<pre>secundus</pre>

=={{header|C}}==
<lang c>struct link {
struct link *next;
int data;
};</lang>

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

The simplest C++ version looks basically like the C version:

<lang cpp>struct link
{
link* next;
int data;
};</lang>

Initialization of links on the heap can be simplified by adding a constructor:

<lang cpp>struct link
{
link* next;
int data;
link(int a_data, link* a_next = 0): next(a_next), data(a_data) {}
};</lang>

With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement:

<lang cpp> link* small_primes = new link(2, new link(3, new link(5, new link(7))));</lang>

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

<lang cpp>template<typename T> struct link
{
link* next;
T data;
link(T a_data, link* a_next = 0): next(a_next), data(a_data) {}
};</lang>

Note that the generic version works for any type, not only integral types.

=={{header|C sharp|C#}}==
<lang csharp>class Link
{
public int Item { get; set; }
public Link Next { get; set; }

//A constructor is not neccessary, but could be useful
public Link(int item, Link next = null) {
Item = item;
Next = next;
}
}
}</lang>

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

<lang clojure>(cons 1 (cons 2 (cons 3 nil))) ; =>(1 2 3)</lang>

Note: this is an immutable data structure. With cons you are '''cons'''tructing a new seq.

=={{header|Common Lisp}}==

The built-in <code>cons</code> type is used to construct linked lists. Using another type would be unidiomatic and inefficient.

<lang lisp>(cons 1 (cons 2 (cons 3 nil)) => (1 2 3)</lang>

=={{header|Clean}}==
<lang clean>import StdMaybe

:: Link t = { next :: Maybe (Link t), data :: t }</lang>

=={{header|D}}==
Generic template-based node element.

<lang d>struct SLinkedNode(T) {
T data;
typeof(this)* next;
}
}

void main() {
alias SLinkedNode!int N;
N* n = new N(10);
}</lang>
Also the Phobos library contains a singly-linked list, std.container.SList. Tango contains tango.util.collection.LinkSeq.

=={{header|Delphi}}==

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.

<lang delphi>Type
pOneWayList = ^OneWayList;
OneWayList = record
pData : pointer ;
Next : pOneWayList ;
end;</lang>

=={{header|E}}==

<lang e>interface LinkedList guards LinkedListStamp {}
def empty implements LinkedListStamp {
to null() { return true }
}
def makeLink(value :int, var next :LinkedList) {
def link implements LinkedListStamp {
to null() { return false }
to value() { return value }
to next() { return next }
to setNext(new) { next := new }
}
return link
}</lang>

=={{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:
<lang Erlang>
new( Data ) -> erlang:spawn( fun() -> loop( Data, nonext ) end ).
</lang>
For the whole module see [[Singly-linked_list/Element_insertion]]

=={{header|Factor}}==
<lang>TUPLE: linked-list data next ;

: <linked-list> ( data -- linked-list )
linked-list new swap >>data ;</lang>

=={{header|Fantom}}==

<lang fantom>
class Node
{
const Int value // keep value fixed
Node? successor // allow successor to change, also, can be 'null', for end of list

new make (Int value, Node? successor := null)
{
this.value = value
this.successor = successor
}
}
</lang>

=={{header|Forth}}==

Idiomatically,

<lang forth>0 value numbers
: push ( n -- )
here swap numbers , , to numbers ;</lang>

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:

<lang forth>: length ( list -- u )
0 swap begin dup while 1 under+ @ repeat drop ;

: head ( list -- x )
cell+ @ ;

: .numbers ( list -- )
begin dup while dup head . @ repeat drop ;</lang>

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:
<lang fortran>type node
real :: data
type( node ), pointer :: next => null()
end type node
!
!. . . .
!
type( node ) :: head</lang>

=={{header|Go}}==
<lang go>type Ele struct {
Data interface{}
Next *Ele
}

func (e *Ele) Append(data interface{}) *Ele {
if e.Next == nil {
e.Next = &Ele{data, nil}
} else {
tmp := &Ele{data, e.Next}
e.Next = tmp
}
return e.Next
}

func (e *Ele) String() string {
return fmt.Sprintf("Ele: %v", e.Data)
}</lang>

=={{header|Groovy}}==
Solution:
<lang groovy>class ListNode {
Object payload
ListNode next
String toString() { "${payload} -> ${next}" }
}</lang>

Test:
<lang groovy>def n1 = new ListNode(payload:25)
n1.next = new ListNode(payload:88)

println n1</lang>

Output:
<pre>25 -> 88 -> null</pre>

=={{header|Haskell}}==

This task is not idiomatic for Haskell. Usually, all data in pure functional programming is immutable, and deconstructed through [[Pattern Matching]]. The Prelude already contains a parametrically polymorphic list type that can take any data member type, including numeric values. These lists are then used very frequently. Because of this, lists have additional special syntactic sugar.

An equivalent declaration for such a list type without the special syntax would look like this:

<lang haskell> data List a = Nil | Cons a (List a)</lang>

A declaration like the one required in the task, with an integer as element type and a mutable link, would be

<lang haskell> data IntList s = Nil | Cons Integer (STRef s (IntList s))</lang>

but that would be really awkward to use.

== Icon and Unicon ==

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

=== {{header|Icon}} ===

<lang Icon>
record Node (value, successor)
</lang>

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

<lang Unicon>
class Node (value, successor)
initially (value, successor)
self.value := value
self.successor := successor
end
</lang>

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

<lang Icon>
procedure main ()
n := Node(1, Node (2))
write (n.value)
write (n.successor.value)
end
</lang>

=={{header|J}}==

This task is not idomatic in J -- J has lists natively and while using lists to emulate lists is quite possible, it creates additional overhead at every step of the way. (J's native lists are probably best thought of as arrays with values all adjacent to each other, though they also support constant time append.)

However, for illustrative purposes:

<lang J>list=: 0 2$0
list</lang>

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:

<lang J> list=: ,: _ 42
list
_ 42</lang>

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:

<lang J> list=: 0 2$a: NB. creates list with 0 items
list
list=: ,: (<_) , <'some text' NB. creates list with 1 item
list
+-+---------+
|_|some text|
+-+---------+</lang>

=={{header|Java}}==

The simplest Java version looks basically like the C++ version:

<lang java>class Link
{
Link next;
int data;
}</lang>

Initialization of links on the heap can be simplified by adding a constructor:

<lang java>class Link
{
Link next;
int data;
Link(int a_data, Link a_next) { next = a_next; data = a_data; }
}</lang>

With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement:

<lang java> Link small_primes = new Link(2, new Link(3, new Link(5, new Link(7, null))));</lang>

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

<lang java>class Link<T>
{
Link<T> next;
T data;
Link(T a_data, Link<T> a_next) { next = a_next; data = a_data; }
}</lang>

=={{header|JavaScript}}==
<lang javascript>function LinkedList(value, next) {
this._value = value;
this._next = next;
}
LinkedList.prototype.value = function() {
if (arguments.length == 1)
this._value = arguments[0];
else
return this._value;
}
LinkedList.prototype.next = function() {
if (arguments.length == 1)
this._next = arguments[0];
else
return this._next;
}

// convenience function to assist the creation of linked lists.
function createLinkedListFromArray(ary) {
var head = new LinkedList(ary[0], null);
var prev = head;
for (var i = 1; i < ary.length; i++) {
var node = new LinkedList(ary[i], null);
prev.next(node);
prev = node;
}
return head;
}

var head = createLinkedListFromArray([10,20,30,40]);</lang>

=={{header|Julia}}==
Julia does not have null, so we let node reference itself to indicate it is the last node.
<lang julia>
type Node{T}
data::T
next::Node{T}
function Node(data::T)
n = new()
n.data = data
# mark the end of the list. Julia does not have nil or null.
n.next = n
n
end
end

# convenience. Let use write Node(10) or Node(10.0) instead of Node{Int64}(10), Node{Float64}(10.0)
function Node(data)
return Node{typeof(data)}(data)
end

islast(n::Node) = (n == n.next)

function append{T}(n::Node{T}, data::T)
tmp = Node(data)
if !islast(n)
tmp.next = n.next
end
n.next = tmp
end
</lang>

Example of making a linked list
<lang julia>
head = Node(1)
n = append(head, 2)
n = append(n, 3)
</lang>

=={{header|Logo}}==
As with other list-based languages, simple lists are represented easily in Logo.

<lang logo>fput item list ; add item to the head of a list

first list ; get the data
butfirst list ; get the remainder
bf list ; contraction for "butfirst"</lang>

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.

<lang logo>.setfirst list value
.setbf list remainder</lang>

=={{header|Mathematica}}==
<lang Mathematica>Append[{}, x]
-> {x}</lang>

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

<lang modula2>TYPE
Link = POINTER TO LinkRcd;
LinkRcd = RECORD
Next: Link;
Data: INTEGER
END;</lang>

=={{header|Modula-3}}==
<lang modula3>TYPE
Link = REF LinkRcd;
LinkRcd = RECORD
Next: Link;
Data: INTEGER
END;</lang>

=={{header|Nim}}==
<lang nim>type Node[T] = ref object
next: Node[T]
data: T

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

var a = newNode 12
var b = newNode 13
var c = newNode 14</lang>

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

<lang objc>#import <Foundation/Foundation.h>

@interface RCListElement<T> : NSObject
{
RCListElement<T> *next;
T datum;
}
- (RCListElement<T> *)next;
- (T)datum;
- (RCListElement<T> *)setNext: (RCListElement<T> *)nx;
- (void)setDatum: (T)d;
@end

@implementation RCListElement
- (RCListElement *)next
{
return next;
}
- (id)datum
{
return datum;
}
- (RCListElement *)setNext: (RCListElement *)nx
{
RCListElement *p = next;
next = nx;
return p;
}
- (void)setDatum: (id)d
{
datum = d;
}
@end</lang>

=={{header|OCaml}}==

This task is not idiomatic for OCaml. OCaml already contains a built-in parametrically polymorphic list type that can take any data member type, including numeric values. These lists are then used very frequently. Because of this, lists have additional special syntactic sugar. OCaml's built-in lists, like most functional data structures, are immutable, and are deconstructed through [[Pattern Matching]].

An equivalent declaration for such a list type without the special syntax would look like this:

<lang ocaml> type 'a list = Nil | Cons of 'a * 'a list</lang>

A declaration like the one required in the task, with an integer as element type and a mutable link, would be

<lang ocaml> type int_list = Nil | Cons of int * int_list ref</lang>

but that would be really awkward to use.

=={{header|Oforth}}==

<lang Oforth>Collection Class new: LinkedList(data, mutable next)</lang>

=={{header|ooRexx}}==

The simplest ooRexx version is similar in form to the Java or C++ versions:
<lang ooRexx>
list = .linkedlist~new
index = list~insert("abc") -- insert a first item, keeping the index
list~insert("def") -- adds to the end
list~insert("123", .nil) -- adds to the begining
list~insert("456", index) -- inserts between "abc" and "def"
list~remove(index) -- removes "abc"

say "Manual list traversal"
index = list~first -- demonstrate traversal
loop while index \== .nil
say index~value
index = index~next
end

say
say "Do ... Over traversal"
do value over list
say value
end

-- the main list item, holding the anchor to the links.
::class linkedlist
::method init
expose anchor

-- create this as an empty list
anchor = .nil

-- return first link element
::method first
expose anchor
return anchor

-- return last link element
::method last
expose anchor

current = anchor
loop while current \= .nil
-- found the last one
if current~next == .nil then return current
current = current~next
end
-- empty
return .nil

-- insert a value into the list, using the convention
-- followed by the built-in list class. If the index item
-- is omitted, add to the end. If the index item is .nil,
-- add to the end. Otherwise, just chain to the provided link.
::method insert
expose anchor
use arg value

newLink = .link~new(value)
-- adding to the end
if arg() == 1 then do
if anchor == .nil then anchor = newLink
else self~last~insert(newLink)
end
else do
use arg ,index
if index == .nil then do
if anchor \== .nil then newLink~next = anchor
anchor = newLink
end
else index~insert(newLink)
end
-- the link item serves as an "index"
return newLink

-- remove a link from the chain
::method remove
expose anchor

use strict arg index

-- handle the edge case
if index == anchor then anchor = anchor~next
else do
-- no back link, so we need to scan
previous = self~findPrevious(index)
-- invalid index, don't return any item
if previous == .nil then return .nil
previous~next = index~next
end
-- belt-and-braces, remove the link and return the value
index~next = .nil
return index~value

-- private method to find a link predecessor
::method findPrevious private
expose anchor
use strict arg index

-- we're our own precessor if this first
if index == anchor then return self

current = anchor
loop while current \== .nil
if current~next == index then return current
current = current~next
end
-- not found
return .nil

-- helper method to allow DO ... OVER traversal
::method makearray
expose anchor
array = .array~new

current = anchor
loop while current \= .nil
array~append(current~value)
current = current~next
end
return array

::class link
::method init
expose value next
-- by default, initialize both data and next to empty.
use strict arg value = .nil, next = .nil

-- allow external access to value and next link
::attribute value
::attribute next

::method insert
expose next
use strict arg newNode
newNode~next = next
next = newNode


</lang>

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

=={{header|Pascal}}==

<lang pascal>type
PLink = ^TLink;
TLink = record
FNext: PLink;
FData: integer;
end;</lang>

=={{header|Perl}}==
Just use an array. You can traverse and splice it any way. Linked lists are way too low level.

However, if all you got is an algorithm in a foreign language, you can use references to accomplish the translation.
<lang perl>my %node = (
data => 'say what',
next => \%foo_node,
);
$node{next} = \%bar_node; # mutable</lang>
=={{header|Perl 6}}==
The <tt>Pair</tt> constructor is exactly equivalent to a cons cell.
<lang perl6>my $elem = 42 => $nextelem;</lang>

=={{header|PicoLisp}}==
In PicoLisp, the singly-linked list is the most important data structure. Many
built-in functions deal with linked lists. A list consists of interconnected
"cells". Cells are also called "cons pairs", because they are constructed with
the function '[http://software-lab.de/doc/refC.html#cons cons]'.

Each cell consists of two parts: A CAR and a CDR. Both may contain (i.e. point
to) arbitrary data (numbers, symbols, other cells, or even to itself). In the
case of a linked list, the CDR points to the rest of the list.

The CAR of a cell can be manipulated with
'[http://software-lab.de/doc/refS.html#set set]'
and the CDR with '[http://software-lab.de/doc/refC.html#con con]'.

=={{header|PL/I}}==
<lang PL/I>
declare 1 node based (p),
2 value fixed,
2 link pointer;
</lang>

=={{header|Pop11}}==

List are built in into Pop11, so normally on would just use them:

<lang pop11>;;; Use shorthand syntax to create list.
lvars l1 = [1 2 three 'four'];
;;; Allocate a single list node, with value field 1 and the link field
;;; pointing to empty list
lvars l2 = cons(1, []);
;;; print first element of l1
front(l1) =>
;;; print the rest of l1
back(l1) =>
;;; Use index notation to access third element
l1(3) =>
;;; modify link field of l2 to point to l1
l1 -> back(l2);
;;; Print l2
l2 =></lang>

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

<lang pop11>uses objectclass;
define :class ListNode;
slot value = [];
slot next = [];
enddefine;
;;; Allocate new node and assign to l1
newListNode() -> l1;
;;; Print it
l1 =>
;;; modify value
1 -> value(l1);
l1 =>
;;; Allocate new node with initialized values and assign to link field
;;; of l1
consListNode(2, []) -> next(l1);
l1 =></lang>

=={{header|PureBasic}}==

<lang PureBasic>Structure MyData
*next.MyData
Value.i
EndStructure</lang>

=={{header|Python}}==

The Node class implements also iteration for more Pythonic iteration over linked lists.

<lang python>class LinkedList(object):
"""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!
"""
class Node(object):
def __init__(self, item):
self.value = item
self.next = None
def __init__(self, item=None):
if item is not None:
self.head = Node(item); self.tail = self.head
else:
self.head = None; self.tail = None
def append(self, item):
if not self.head:
self.head = Node(item)
self.tail = self.head
elif self.tail:
self.tail.next = Node(item)
self.tail = self.tail.next
else:
self.tail = Node(item)
def __iter__(self):
cursor = self.head
while cursor:
yield cursor.value
cursor = cursor.next</lang>

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

=={{header|Racket}}==

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>
#lang racket
(mcons 1 (mcons 2 (mcons 3 '()))) ; a mutable list
</lang>

=={{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).
<lang rexx>/*REXX program demonstrates how to create and show a single-linked list.*/
@.=0 /*define a null linked list. */
call set@ 3 /*linked list: 12 Proth Primes. */
call set@ 5
call set@ 13
call set@ 17
call set@ 41
call set@ 97
call set@ 113
call set@ 193
call set@ 241
call set@ 257
call set@ 353
call set@ 449
w=@.max_width /*use the maximum width of nums. */
call list@ /*list all the elements in list. */
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────LIST@ subroutine────────────────────*/
list@: say; w=max(7, @.max_width ) /*use the max width of nums or 7.*/
say center('item',6) center('value',w) center('next',6)
say center('' ,6,'─') center('' ,w,'─') center('' ,6,'─')
p=1
do j=1 until p==0 /*show all entries of linked list*/
say right(j,6) right(@.p._value,w) right(@.p._next,6)
p=@.p._next
end /*j*/
return
/*──────────────────────────────────SET@ subroutine─────────────────────*/
set@: procedure expose @.; parse arg y /*get element to be added to list*/
_=@._last /*set the previous last element. */
n=_+1 /*bump last ptr in linked list. */
@._._next=n /*set the next pointer value. */
@._last=n /*define next item in linked list*/
@.n._value=y /*set item to the value specified*/
@.n._next=0 /*set the next pointer value. */
@..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. */</lang>
'''output'''
<pre>
item value next
────── ─────── ──────
1 3 2
2 5 3
3 13 4
4 17 5
5 41 6
6 97 7
7 113 8
8 193 9
9 241 10
10 257 11
11 353 12
12 449 0
</pre>

=={{header|Ruby}}==

<lang ruby>class ListNode
attr_accessor :value, :succ

def initialize(value, succ=nil)
self.value = value
self.succ = succ
end

def each(&b)
yield self
succ.each(&b) if succ
end

include Enumerable

def self.from_array(ary)
head = self.new(ary[0], nil)
prev = head
ary[1..-1].each do |val|
node = self.new(val, nil)
prev.succ = node
prev = node
end
head
end
end

list = ListNode.from_array([1,2,3,4])</lang>

=={{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.
<lang Rust> struct Node<T> {
elem: T,
next: Option<Box<Node<T>>>,
}</lang>

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.

<lang Rust>type Link<T> = Option<Box<Node<T>>>; // Type alias
pub struct List<T> { // User-facing interface for list
head: Link<T>,
}

struct Node<T> { // Private implementation of Node
elem: T,
next: Link<T>,
}

impl<T> List<T> {
#[inline]
pub fn new() -> Self { // List constructor
List { head: None }
// Add other methods here
}</lang>

Then a separate program could utilize the basic implementation above like so:
<lang rust>extern crate LinkedList; // Name is arbitrary here

use LinkedList::List;

fn main() {
let list = List::new();
// Do stuff
}</lang>

=={{header|Run BASIC}}==
<lang runbasic>data = 10
link = 10
dim node{data,link} </lang>

=={{header|Scala}}==
<lang scala>class Node(n: Int, link: Node) {
var data = n
var next = link
}
</lang>

The one below is more inline with the built-in definition

<lang scala>class Node {
var data: Int
var next = this
def this(n: Int, link: Node) {
this()
if (next != null){
data = n
next = link
}
}
</lang>

=={{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:
<lang scheme>(cons value next)</lang>

The value and next-link parts of the pair can be deconstructed using the <tt>car</tt> and <tt>cdr</tt> functions, respectively:
<lang scheme>(car my-list) ; returns the first element of the list
(cdr my-list) ; returns the remainder of the list</lang>

Each of these parts are mutable and can be set using the <tt>set-car!</tt> and <tt>set-cdr!</tt> functions, respectively:
<lang scheme>(set-car! my-list new-elem)
(set-cdr! my-list new-next)</lang>

=={{header|Sidef}}==
<lang ruby>var node = Hash.new(
data => 'say what',
next => foo_node,
);

node{:next} = bar_node; # mutable</lang>


=={{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:
<lang ssem>01000000000000000000000000000000 26. 2
01111000000000000000000000000000 27. 30
10000000000000000000000000000000 28. 1
01011000000000000000000000000000 29. 26
11000000000000000000000000000000 30. 3
00000000000000000000000000000000 31. 0</lang>
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]].

=={{header|Tcl}}==
While it is highly unusual to implement linked lists in Tcl, since the language has a built-in list type (that internally uses arrays of references), it is possible to simulate it with objects.

{{Works with|Tcl|8.6}} or {{libheader|TclOO}}
<lang tcl>oo::class create List {
variable content next
constructor {value {list ""}} {
set content $value
set next $list
}
method value args {
set content {*}$args
}
method attach {list} {
set next $list
}
method detach {} {
set next ""
}
method next {} {
return $next
}
method print {} {
for {set n [self]} {$n ne ""} {set n [$n next]} {
lappend values [$n value]
}
return $values
}
}</lang>

=={{header|X86 Assembly}}==
{{works with|NASM}}

<lang asm>
struct link
.next: resd 1
.data: resd 1
endstruc
</lang>
Of course, ASM not natively having structures we can simply do..
<lang asm>
link resb 16
</lang>
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}}
<lang asm>
link struct
next dd ?
data dd ?
link ends
</lang>
{{works with|FASM}}
<lang asm>struc link next,data
{
.next dd next
.data dd data
}</lang>

=={{header|XPL0}}==
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations
def IntSize=4; \number of bytes in an integer
def Size=10; \number of nodes in this linked list
int Link, List, Node;
[Link:= 0; \build linked list, starting at the end
for Node:= 0 to Size-1 do
[List:= Reserve(IntSize*2); \get some memory to hold link and data
List(0):= Link;
List(1):= Node*Node; \insert example data
Link:= List; \Link now points to newly created node
];
Node:= List; \traverse the linked list
repeat IntOut(0, Node(1)); CrLf(0); \display the example data
Node:= Node(0); \move to next node
until Node=0; \end of the list
]</lang>

=={{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.
<lang zkl>List(1,"two",3.14); L(1,"two",3.14);
ROList(fcn{"foobar"}); T('+);</lang>

{{omit from|GUISS}}

Revision as of 06:49, 16 January 2017

class Node<T>{ 

   var data:T?=nil
   var next:Node?=nil
   init(input:T){
       data=input
       next=nil
   }

}

Retrieved from "https://rosettacode.org/wiki/Singly-linked_list/Element_definition?oldid=27845"