Singly-linked list/Element definition

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.

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>

AutoHotkey

<lang AutoHotkey>element = 5 ; data element_next = element2 ; link to next element</lang>

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> DIM node{pNext%, iData%} </lang>

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>

 new$link:?link1

& new$link:?link2 & first thing:?(link1..data) & secundus:?(link2..data) & '$link2:(=?(link1..next)) & !(link1..next..data) </lang> The last line returns <lang>secundus</lang>

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.

C#

<lang csharp>class Link {

   public int item;
   public Link next;

}</lang>

Common Lisp

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

Clean

<lang clean>import StdMaybe

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

D

Generic template-based node element.

<lang D>class Node(T) { public:

   T data;
   Node next;
   this(T d, Node n = null) { data=d; next=n; }

}</lang>

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>

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>

Factor

<lang>TUPLE: linked-list data next ;

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

   linked-list new swap >>data ;</lang>

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>

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.

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>

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>

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:

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.

Icon

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

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>

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:

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>

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

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>

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>

Mathematica

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

Media:Example.ogg

Modula-2

<lang modula2>TYPE

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

Objective-C

This implements a class which has the primitive basic Objective-C class Object as parent.

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

@interface RCListElement : Object {

 RCListElement *next;
 id datum;

} + (RCListElement *)new; - (RCListElement *)next; - (id)datum; - (RCListElement *)setNext: (RCListElement *)nx; - (void)setDatum: (id)d; @end

@implementation RCListElement + (RCListElement *)new {

 RCListElement *m = [super new];
 [m setNext: nil];
 [m setDatum: nil];
 return m;

} - (RCListElement *)next {

 return next;

} - (id)datum {

 return datum;

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

 RCListElement *p;
 p = next;
 next = nx;
 return p;

} - (void)setDatum: (id)d {

 datum = d;

} @end</lang>

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:

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.

Pascal

<lang pascal>type

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

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>

Perl 6

The Pair constructor is exactly equivalent to a cons cell. <lang perl6>my $elem = 42 => $nextelem;</lang>

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 '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 'set' and the CDR with 'con'.

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>

PureBasic

<lang PureBasic>Structure MyData

 *next.MyData
 Value.i

EndStructure</lang>

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.

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>

Scala

<lang scala>class Node(n: Int, link: Node) {

 var data = n
 var next =  link

} </lang>

Can also easily add get/set methods to access/change. Better to use Scala or Java's built-in LinkedList

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 cons function to construct it: <lang scheme>(cons value next)</lang>

The value and next-link parts of the pair can be deconstructed using the car and cdr 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 set-car! and set-cdr! functions, respectively: <lang scheme>(set-car! my-list new-elem) (set-cdr! my-list new-next)</lang>

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 version 8.6

or

Library: 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>

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.

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>