Singly-linked list/Element definition: Difference between revisions

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

 

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

 

=={{header|AutoHotkey}}==

 

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

Generic template-based node element.

 

T data;

 

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

 

pOneWayList = ^OneWayList;

OneWayList = record

pData : pointer ;

Next : pOneWayList ;

 

=={{header|E}}==

 

def empty implements LinkedListStamp {

to null() { return true }

}

return link

 

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

 

 

 

 

{

}

@end

 

@implementation RCListElement

- (RCListElement *)next

{

- (RCListElement *)setNext: (RCListElement *)nx

{

next = nx;

return p;

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

'[http://software-lab.de/doc/refS.html#set set]'

and the CDR with '[http://software-lab.de/doc/refC.html#con con]'.

 

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

 

=={{header|Ruby}}==

 

attr_accessor :value, :succ

 

end

 

 

=={{header|Scala}}==

}

 

 

 

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

 

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

variable content next

constructor {value {list ""}} {

return $values

}

 

=={{header|X86 Assembly}}==

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

 

{{omit from|GUISS}}