Doubly-linked list/Element definition: Difference between revisions

{{task|Data Structures}}

 

{{Template:See also lists}}

=={{header|Ada}}==

type Link_Access is access Link;

type Link is record

Prev : Link_Access := null;

Data : Integer;

Using generics, the specification might look like this:

type Element_Type is private;

package Linked_List is

Traversing : Boolean := False; -- True when in a traversal.

end record;

In Ada 2005 this example can be written without declaration of an access type:

Next : not null access Link := Link'Unchecked_Access;

Prev : not null access Link := Link'Unchecked_Access;

Data : Integer;

Here the list element is created already pointing to itself, so that no further initialization is required. The type of the element is marked as ''limited'' indicating that such elements have referential semantics and cannot be copied.

 

Ada's standard container library includes a generic doubly linked list. The structure of the link element is private.

 

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

 

PROC obj link free = (REF OBJLINK free)VOID:

 

=={{header|AutoHotkey}}==

 

=={{header|Axe}}==

r₂→{r₁}ʳ

0→{r₁+2}ʳ

Lbl VALUE

{r₁}ʳ

 

{{works with|BBC BASIC for Windows}}

 

=={{header|C}}==

void *data;

 

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

C++ has doubly linked list class template in standard library. However actual list noded are treated as implementation detail and encapsulated inside list. If we were to reimplement list, then node could look like that:

struct Node

{

Node* prev;

T data;

 

=={{header|Clojure}}==

This sort of mutable structure is not idiomatic in Clojure. [[../Definition#Clojure]] or a finger tree implementation would be better.

 

 

(defn new-node [prev next data]

 

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

 

 

See the functions on the [[Doubly-Linked List]] page for the usage of these structures.

=={{header|D}}==

A default constructor is implicit:

T data;

typeof(this)* prev, next;

alias N = Node!int;

N* n = new N(10);

 

=={{header|Delphi}}==

 

type

end;

 

 

=={{header|E}}==

This does no type-checking, under the assumption that it is being used by a containing doubly-linked list object which enforces that invariant along with others such as that <code>element.getNext().getPrev() == element</code>. See [[Doubly-Linked List#E]] for an actual implementation (which uses slightly more elaborate nodes than this).

 

def element {

to setValue(v) { value := v }

return element

 

=={{header|Erlang}}==

Using the code in [[Doubly-linked_list/Definition]] the element is defined by:

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

 

=={{header|Fortran}}==

In ISO Fortran 95 or later:

real :: data

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

! . . . .

!

 

=={{header|Go}}==

string

next, prev *dlNode

Or, using the [http://golang.org/pkg/container/list/#Element container/list] package:

 

var node list.Element

 

=={{header|Haskell}}==

Note that unlike naive pointer manipulation which could corrupt the doubly-linked list, updateLeft and updateRight will always yield a well-formed data structure.

 

data DList a = Leaf | Node (DList a) a (DList a)

 

where current = Node l v next

next = updateRight nr new

 

==Icon and {{header|Unicon}}==

Uses Unicon classes.

 

class DoubleLink (value, prev_link, next_link)

initially (value, prev_link, next_link)

self.next_link := next_link

end

 

=={{header|J}}==

Nevertheless, this is doable, though it necessarily departs from the definition specified at [[Doubly-linked_list/Definition#J]].

 

create=:3 :0

this=:coname''

'predecessor successor data'=:y

successor__predecessor=: predecessor__successor=: this

 

Here, when we create a new list element, we need to specify its successor node and its predecessor node and the data to be stored in the node. To start a new list we will need a node that can be the head and the tail of the list -- this will be the successor node for the last element of the list and the predecessor node for the first element of the list:

 

create=:3 :0

predecessor=:successor=:this=: coname''

 

=={{header|Java}}==

{{works with|Java|1.5+}}

private T element;

private Node<T> next, prev;

return prev;

}

 

For use with [[Java]] 1.4 and below, delete all "<T>"s and replace T's with "Object".

=={{header|JavaScript}}==

Inherits from LinkedList (see [[Singly-Linked_List_(element)#JavaScript]])

this._value = value;

this._next = next;

}

 

 

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

 

Link = POINTER TO LinkRcd;

LinkRcd = RECORD

Prev, Next: Link;

Data: INTEGER

 

=={{header|Nim}}==

Node[T] = ref TNode[T]

 

TNode[T] = object

next, prev: Node[T]

 

=={{header|Objeck}}==

@value : Base;

@next : ListNode;

return @previous;

}

 

=={{header|OCaml}}==

===Imperative===

mutable data: 'a;

mutable next: 'a dlink option;

in

aux

 

iter_forward_dlink (Printf.printf "%d\n") dl ;;

1

4

5

 

===Functional===

examples of this page and its task, but in regular OCaml these kind of imperative structures can be advantageously replaced by a functional equivalent, that can be use in the same area, which is to have a list of elements and be able to point to one of these. We can use this type:

 

 

The middle element is the pointed item, and the two lists are the

previous and the following items.

Here are the associated functions:

| hd::tl -> [], hd, tl

| [] -> invalid_arg "empty list"

prev_tl, prev, item::next

| _ ->

val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])

# let nl = next nl ;;

 

# current nl ;;

 

=={{header|Oforth}}==

Complete definition is here : [[../Definition#Oforth]]

 

 

=={{header|Oz}}==

We show how to create a new node as a record value.

node(prev:{NewCell _}

next:{NewCell _}

value:Value)

Note: this is for illustrative purposes only. In a real Oz program, you would use one of the existing data types.

 

=={{header|Pascal}}==

 

data_ptr = ^data; (* presumes that type 'data' is defined above *)

link = record

next: link_ptr;

data: data_ptr;

 

=={{header|Perl}}==

 

data => 'say what',

next => \%foo_node,

prev => \%bar_node,

);

 

 

 

 

=={{header|PicoLisp}}==

With that, 'cddr' can be used to access the next, and 'cadr' to access the

previous element.

(let L (car DLst) # Get current data list

(set DLst (cons X NIL L)) # Prepend two new cons pairs

 

# We prepend 'not' to the list in the previous example

For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].

 

=={{header|Pop11}}==

 

define :class Link;

slot next = [];

slot prev = [];

slot data = [];

=={{header|PureBasic}}==

*prev.node

*next.node

value.i

 

=={{header|Python}}==

 

def __init__(self, data = None, prev = None, next = None):

self.prev = prev

while c != None:

yield c

 

=={{header|Racket}}==

 

(define-struct dlist (head tail) #:mutable)

(define-struct dlink (content prev next) #:mutable)

 

See the functions on the [[Doubly-Linked List]] page for the usage of these structures.

 

 

 

 

 

 

'''output'''

─── initializing the list. ───

 

=={{header|Ruby}}==

Extending [[Singly-Linked List (element)#Ruby]]

attr_accessor :prev

# accessors :succ and :value are inherited

end

 

 

=={{header|Rust}}==

 

=== Simply using the standard library ===

fn main() {

// Doubly linked list containing 32-bit integers

let list = LinkedList::<i32>::new();

 

=== The behind-the-scenes implementation ===

Doubly linked lists present a problem in Rust due to its ownership model. There cannot be two mutable references to the same object, so what are we to do? Below are the relevant lines (with added comments) from the <code>std</code> implementation ([https://doc.rust-lang.org/std/collections/struct.LinkedList.html Documentation] [https://github.com/rust-lang/rust/blob/master/src/libcollections/linked_list.rs Source]).

 

 

}

 

struct Node<T> {

 

=={{header|Sidef}}==

data => 'say what',

next => foo_node,

);

 

 

=={{header|Tcl}}==

{{eff note|Tcl|list}}

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

variable content next prev

constructor {value {list ""}} {

set prev {*}$args

}

 

=={{header|Visual Basic .NET}}==

 

Public Value As T

Public [Next] As Node(Of T)

Public Previous As Node(Of T)

 

{{omit from|ACL2}}