⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

{{task|Data Structures}}

;Task: Define the data structure for a [[Linked_List#Doubly-Linked_List|doubly-linked list]] element.

The element should include a data member to hold its value and pointers to both the next element in the list and the previous element in the list.

The pointers should be mutable.

{{Template:See also lists}}


type Link;
type Link_Access is access Link;
type Link is record
  Next : Link_Access := null;
  Prev : Link_Access := null;
  Data : Integer;
end record;

Using generics, the specification might look like this:

   type Element_Type is private;
package Linked_List is
   type List_Type is limited private;
   type List_Element;
   type List_Element_Ptr is access list_element;
   type List_Element is
	 Prev : List_Element_Ptr;
	 Data : Element_Type;
	 Next : List_Element_Ptr;
      end record;
   type List_Type is
	 Head        : List_Element_Ptr;     -- Pointer to first element.
	 Tail        : List_Element_Ptr;     -- Pointer to last element.
	 Cursor      : List_Element_Ptr;     -- Pointer to cursor element.
	 Count       : Natural := 0;         -- Number of items in list.
	 Traversing  : Boolean := False;     -- True when in a traversal.
      end record;
end Linked_List;

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

type Link is limited record
   Next : not null access Link := Link'Unchecked_Access;
   Prev : not null access Link := Link'Unchecked_Access;
   Data : Integer;
end record;

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.


{{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/link.a68'''

# -*- coding: utf-8 -*- #
  MODE OBJVALUE = ~ # Mode/type of actual obj to be queued #

  OBJVALUE value # ... etc. required #


PROC obj link free = (REF OBJLINK free)VOID:
   prev OF free := next OF free := obj queue empty # give the garbage collector a big hint #

'''See also:''' [[Queue/Usage#ALGOL_68|Queue/Usage]]

ARM Assembly

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI  */

/* structure Node Doublylinked List*/
    .struct  0
NDlist_next:                    @ next element
    .struct  NDlist_next + 4
NDlist_prev:                    @ previous element
    .struct  NDlist_prev + 4
NDlist_value:                   @ element value or key
    .struct  NDlist_value + 4


see [[Doubly-linked list/AutoHotkey]]







{{works with|BBC BASIC for Windows}}

      DIM node{pPrev%, pNext%, iData%}


link=(prev=) (next=) (data=)


struct link
  struct link *next;
  struct link *prev;
  void  *data;
  size_t type;


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:

template <typename T>

struct Node
    Node* next;
    Node* prev;
    T data;


class Link
    public int Item { get; set; }
    public Link Prev { get; set; }
    public Link Next { get; set; }

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


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

(defrecord Node [prev next data])

(defn new-node [prev next data]
  (Node. (ref prev) (ref next) data))

Common Lisp

(defstruct dlist head tail)
(defstruct dlink content prev next)

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


A default constructor is implicit:

struct Node(T) {
    T data;
    typeof(this)* prev, next;

void main() {
    alias N = Node!int;
    N* n = new N(10);


struct Node(T) {


    pList = ^List ;

    list = record
       data : pointer ;
       prev : pList ;
       next : pList ;



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 element.getNext().getPrev() == element. See [[Doubly-Linked List#E]] for an actual implementation (which uses slightly more elaborate nodes than this).

def makeElement(var value, var next, var prev) {
    def element {
        to setValue(v) { value := v }
        to getValue() { return value }

        to setNext(n) { next := n }
        to getNext() { return next }

        to setPrev(p) { prev := p }
        to getPrev() { return prev }

    return element


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

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


In ISO Fortran 95 or later:

type node
   real :: data
   type(node), pointer :: next => null(), previous => null()
end type node
! . . . .
type( node ), target :: head


type 'a DLElm = {
    mutable prev: 'a DLElm option
    data: 'a
    mutable next: 'a DLElm option


type dlNode struct {
    next, prev *dlNode

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

import "container/list"

var node list.Element
// and using: node.Next(), node.Prev(), node.Value


Haskell in general doesn't have mutability so the following 'mutator' functions use lazy evaluation instead.

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)

updateLeft _ Leaf = Leaf
updateLeft Leaf (Node _ v r) = Node Leaf v r
updateLeft new@(Node nl _ _) (Node _ v r) = current
    where current = Node prev v r
          prev = updateLeft nl new

updateRight _ Leaf = Leaf
updateRight Leaf (Node l v _) = Node l v Leaf
updateRight new@(Node _ _ nr) (Node l v _) = current
    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.value := value
    self.prev_link := prev_link    # links are 'null' if not given
    self.next_link := next_link


As discussed in [[Doubly-linked_list/Definition#J]], doubly linked lists are antithetical to J's design. Defining individual elements as independent structures is even worse. Now each element of the list must contain three arrays (everything in J is an array), all so that we can implement a list.

Yo Dawg, we heard you like lists, so we put lists in your lists so you can list while you list.

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

create=:3 :0
  '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''


{{works with|Java|1.5+}}

   private T element;
   private Node<T> next, prev;

   public Node<T>(){
      next = prev = element = null;

   public Node<T>(Node<T> n, Node<T> p, T elem){
      next = n;
      prev = p;
      element = elem;

   public void setNext(Node<T> n){
      next = n;

   public Node<T> getNext(){
      return next;

   public void setElem(T elem){
      element = elem;

   public T getElem(){
      return element;

   public void setNext(Node<T> n){
      next = n;

   public Node<T> setPrev(Node<T> p){
      prev = p;

   public getPrev(){
      return prev;

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


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

function DoublyLinkedList(value, next, prev) {
    this._value = value;
    this._next = next;
    this._prev = prev;
// from LinkedList, inherit: value(), next(), traverse(), print()
DoublyLinkedList.prototype = new LinkedList();

DoublyLinkedList.prototype.prev = function() {
    if (arguments.length == 1)
        this._prev = arguments[0];
        return this._prev;

function createDoublyLinkedListFromArray(ary) {
    var node, prev, head = new DoublyLinkedList(ary[0], null, null);
    prev = head;
    for (var i = 1; i < ary.length; i++) {
        node = new DoublyLinkedList(ary[i], null, prev);
        prev = node;
    return head;

var head = createDoublyLinkedListFromArray([10,20,30,40]);


{{works with|Julia|0.6}}

abstract type AbstractNode{T} end

struct EmptyNode{T} <: AbstractNode{T} end
mutable struct Node{T} <: AbstractNode{T}


// version 1.1.2

class Node<T: Number>(var data: T, var prev: Node<T>? = null, var next: Node<T>? = null) {
    override fun toString(): String {
        val sb = StringBuilder(this.data.toString())
        var node = this.next
        while (node != null) {
            sb.append(" -> ", node.data.toString())
            node = node.next
        return sb.toString()

fun main(args: Array<String>) {
    val n1 = Node(1)
    val n2 = Node(2, n1)
    n1.next = n2
    val n3 = Node(3, n2)
    n2.next = n3


1 -> 2 -> 3
2 -> 3


  Link = POINTER TO LinkRcd;
  LinkRcd = RECORD
    Prev, Next: Link;
    Data: INTEGER


  Node[T] = ref TNode[T]

  TNode[T] = object
    next, prev: Node[T]
    data: T


        Object* = POINTER TO ObjectDesc;
	ObjectDesc* = (* ABSTRACT *) RECORD

        (* ... *)
END Box.

MODULE Collections;
	Node* = POINTER TO NodeDesc;
	NodeDesc* = (* ABSTRACT *) RECORD
		prev-,next-: Node;
                value-: Box.Object;

        (* ... *)
END Collections.


class ListNode {
  @value : Base;
  @next : ListNode;
  @previous: ListNode;

  New(value : Base) {
    @value := value;

  method : public : Set(value : Base) ~ Nil {
    @value := value;

  method : public : Get() ~ Base {
    return @value;

  method : public : SetNext(next :  Collection.ListNode) ~ Nil {
    @next := next;

  method : public : GetNext() ~ ListNode {
    return @next;

  method : public : SetPrevious(previous :  Collection.ListNode) ~ Nil {
    @previous := previous;

  method : public : GetPrevious() ~ ListNode {
    return @previous;



type 'a dlink = {
  mutable data: 'a;
  mutable next: 'a dlink option;
  mutable prev: 'a dlink option;

let dlink_of_list li =
  let f prev_dlink x =
    let dlink = {
      data = x;
      prev = None;
      next = prev_dlink }
    begin match prev_dlink with
    | None -> ()
    | Some prev_dlink ->
        prev_dlink.prev <- Some dlink
    Some dlink
  List.fold_left f None (List.rev li)

let list_of_dlink =
  let rec aux acc = function
  | None -> List.rev acc
  | Some{ data = d;
          prev = _;
          next = next } -> aux (d::acc) next
  aux []

let iter_forward_dlink f =
  let rec aux = function
  | None -> ()
  | Some{ data = d;
          prev = _;
          next = next } -> f d; aux next
# let dl = dlink_of_list [1;2;3;4;5] in
  iter_forward_dlink (Printf.printf "%d\n") dl ;;
- : unit = ()


The previous implementation is the strict equivalent of the other 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:

type 'a nav_list = 'a list * 'a * 'a list

The middle element is the pointed item, and the two lists are the previous and the following items. Here are the associated functions:

let nav_list_of_list = function
  | hd::tl -> [], hd, tl
  | [] -> invalid_arg "empty list"

let current = function
  | _, item, _ -> item

let next = function
  | prev, item, next::next_tl ->
      item::prev, next, next_tl
  | _ ->
      failwith "end of nav_list reached"

let prev = function
  | prev::prev_tl, item, next ->
      prev_tl, prev, item::next
  | _ ->
      failwith "begin of nav_list reached"
# let nl = nav_list_of_list [1;2;3;4;5] ;;
val nl : 'a list * int * int list = ([], 1, [2; 3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([1], 2, [3; 4; 5])
# let nl = next nl ;;
val nl : int list * int * int list = ([2; 1], 3, [4; 5])

# current nl ;;
- : int = 3


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

Object Class new: DNode(value, mutable prev, mutable next)


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

fun {CreateNewNode Value}
   node(prev:{NewCell _}
	next:{NewCell _}

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


type link_ptr = ^link;
     data_ptr = ^data; (* presumes that type 'data' is defined above *)
     link = record
              prev: link_ptr;
              next: link_ptr;
              data: data_ptr;


my %node = (
     data => 'say what',
     next => \%foo_node,
     prev => \%bar_node,
$node{next} = \%quux_node;  # mutable

Perl 6

role DLElem[::T] {
    has DLElem[T] $.prev is rw;
    has DLElem[T] $.next is rw;
    has T $.payload = T;

    method pre-insert(T $payload) {
        die "Can't insert before beginning" unless $!prev;
        my $elem = ::?CLASS.new(:$payload);
        $!prev.next = $elem;
        $elem.prev = $!prev;
        $elem.next = self;
        $!prev = $elem;

    method post-insert(T $payload) {
        die "Can't insert after end" unless $!next;
        my $elem = ::?CLASS.new(:$payload);
        $!next.prev = $elem;
        $elem.next = $!next;
        $elem.prev = self;
        $!next = $elem;

    method delete {
        die "Can't delete a sentinel" unless $!prev and $!next;
        $!next.prev = $!prev;
        $!prev.next = $!next;   # conveniently returns next element


In Phix, types are used for validation and debugging rather than specification purposes. For extensive run-time checking you could use

type slnode(object x)
    return (sequence(x) and length(x)=DATA and <i>udt</i>(x[DATA]) and integer(x[NEXT] and integer(x[PREV]))
end type

But more often you would just use the builtin sequences. See also [[Singly-linked_list/Element_definition#Phix|Singly-linked_list/Element_definition]].

Memory is automatically reclaimed the moment items are no longer needed.


We use (in addition to the header structure described in [[Doubly-linked list/Definition#PicoLisp]]) two cells per doubly-linked list element:

     +-----+-----+     +-----+-----+
     | Val |  ---+---> |  |  |  ---+---> next
     +-----+-----+     +--+--+-----+
                 prev <---+

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

(de 2tail (X DLst)
   (let L (cdr DLst)
      (con DLst (cons X L NIL))
      (if L
         (con (cdr L) (cdr DLst))
         (set DLst (cdr DLst)) ) ) )

(de 2head (X DLst)
   (let L (car DLst)                  # Get current data list
      (set DLst (cons X NIL L))       # Prepend two new cons pairs
      (if L                           # Unless DLst was empty
         (set (cdr L) (car DLst))     # set new 'prev' link
         (con DLst (car DLst)) ) ) )  # otherwise set 'end' link

# We prepend 'not' to the list in the previous example
(2head 'not *DLst)

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


define structure
   1 Node,
      2 value        fixed decimal,
      2 back_pointer handle(Node),
      2 fwd_pointer  handle(Node);

P = NEW(: Node :); /* Creates a node, and lets P point at it.       */
get (P => value);  /* Reads in a value to the node we just created. */

/* Assuming that back_pointer and fwd_pointer point at other nodes, */
/* we can say ...                                                   */
P = P => fwd_pointer; /* P now points at the next node.             */
P = P => back_pointer; /* P now points at the previous node.        */


uses objectclass;
define :class Link;
    slot next = [];
    slot prev = [];
    slot data = [];


Structure node


class Node(object):
     def __init__(self, data = None, prev = None, next = None):
         self.prev = prev
         self.next = next
         self.data = data
     def __str__(self):
         return str(self.data)
     def __repr__(self):
         return repr(self.data)
     def iter_forward(self):
         c = self
         while c != None:
             yield c
             c = c.next
     def iter_backward(self):
         c = self
         while c != None:
             yield c
             c = c.prev


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


REXX doesn't have linked lists, as there are no pointers (or handles).

However, linked lists can be simulated with lists in REXX.

    ║        ☼☼☼☼☼☼☼☼☼☼☼ Functions of the  List Manager ☼☼☼☼☼☼☼☼☼☼☼           ║
    ║   @init      ─── initializes the List.                                  ║
    ║                                                                         ║
    ║   @size      ─── returns the size of the List  [could be a  0  (zero)]. ║
    ║                                                                         ║
    ║   @show      ─── shows (displays) the complete List.                    ║
    ║   @show k,1  ─── shows (displays) the  Kth  item.                       ║
    ║   @show k,m  ─── shows (displays)  M  items,  starting with  Kth  item. ║
    ║   @show ,,─1 ─── shows (displays) the complete List backwards.          ║
    ║                                                                         ║
    ║   @get  k    ─── returns the  Kth  item.                                ║
    ║   @get  k,m  ─── returns the  M  items  starting with the  Kth  item.   ║
    ║                                                                         ║
    ║   @put  x    ─── adds the  X  items to the  end  (tail) of the List.    ║
    ║   @put  x,0  ─── adds the  X  items to the start (head) of the List.    ║
    ║   @put  x,k  ─── adds the  X  items to before of the  Kth  item.        ║
    ║                                                                         ║
    ║   @del  k    ─── deletes the item  K.                                   ║
    ║   @del  k,m  ─── deletes the   M  items  starting with item  K.         ║
/*REXX program implements various List Manager functions  (see the documentation above).*/
call sy 'initializing the list.'            ;  call @init
call sy 'building list: Was it a cat I saw' ;  call @put "Was it a cat I saw"
call sy 'displaying list size.'             ;  say  "list size="@size()
call sy 'forward list'                      ;  call @show
call sy 'backward list'                     ;  call @show ,,-1
call sy 'showing 4th item'                  ;  call @show 4,1
call sy 'showing 5th & 6th items'           ;  call @show 5,2
call sy 'adding item before item 4: black'  ;  call @put "black",4
call sy 'showing list'                      ;  call @show
call sy 'adding to tail: there, in the ...' ;  call @put "there, in the shadows, stalking its prey (and next meal)."
call sy 'showing list'                      ;  call @show
call sy 'adding to head: Oy!'               ;  call @put  "Oy!",0
call sy 'showing list'                      ;  call @show
exit                                             /*stick a fork in it,  we're all done. */
p:       return word(arg(1), 1)                  /*pick the first word out of many items*/
sy:      say;   say left('', 30) "───" arg(1) '───';              return
@init:   $.@=;    @adjust: $.@=space($.@);   $.#=words($.@);      return
@hasopt: arg o;                                                   return pos(o, opt)\==0
@size:   return $.#
@del:    procedure expose $.;     arg k,m;          call @parms 'km'
         _=subword($.@, k, k-1)   subword($.@, k+m)
         $.@=_;                   call @adjust;                                return
@get:    procedure expose $.;     arg k,m,dir,_
         call @parms 'kmd'
                                  do j=k  for m  by dir  while  j>0  &  j<=$.#
                                  _=_ subword($.@, j, 1)
                                  end   /*j*/
         return strip(_)
@parms:  arg opt                                 /*define a variable based on an option.*/
         if @hasopt('k')  then k=min($.#+1, max(1, p(k 1)))
         if @hasopt('m')  then m=p(m 1)
         if @hasopt('d')  then dir=p(dir 1);                                   return
@put:    procedure expose $.;     parse arg x,k;        k=p(k $.#+1);      call @parms 'k'
         $.@=subword($.@, 1, max(0, k-1))   x   subword($.@, k);           call @adjust
@show:   procedure expose $.;     parse arg k,m,dir;    if dir==-1  &  k==''   then k=$.#
         m=p(m $.#);              call @parms 'kmd';    say @get(k,m, dir);    return


                               ─── initializing the list. ───

                               ─── building list: Was it a cat I saw ───

                               ─── displaying list size. ───
list size=6

                               ─── forward list ───
Was it a cat I saw

                               ─── backward list ───
saw I cat a it Was

                               ─── showing 4th item ───

                               ─── showing 6th & 6th items ───
I saw

                               ─── adding item before item 4: black ───

                               ─── showing list ───
Was it a black cat I saw

                               ─── adding to tail: there, in the ... ───

                               ─── showing list ───
Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).

                               ─── adding to head: Oy! ───

                               ─── showing list ───
Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).


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

class DListNode < ListNode
  attr_accessor :prev
  # accessors :succ and :value are inherited

  def initialize(value, prev=nil, succ=nil)
    @value = value
    @prev = prev
    @prev.succ = self if prev
    @succ = succ
    @succ.prev = self if succ

  def self.from_values(*ary)
    ary << (f = ary.pop)
    ary.map! {|i| new i }
    ary.inject(f) {|p, c| p.succ = c; c.prev = p; c }

list = DListNode.from_values 1,2,3,4


Simply using the standard library

use std::collections::LinkedList;
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 std 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]).

The standard library uses the (currently) unstable Shared<T> type which indicates that the ownership of its contained type has shared ownership. It is guaranteed not to be null, is variant over T (meaning that an &Shared<&'static T> may be used where a &Shared<&'a T> is expected, indicates to the compiler that it may own a T) and may be dereferenced to a mutable pointer (*mut T). All of the above may be accomplished in standard stable Rust, except for the non-null guarantee which allows the compiler to make a few extra optimizations.

    head: Option<Shared<Node<T>>>,
    tail: Option<Shared<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>, // Indicates that we logically own a boxed (owned pointer) Node<T>>

struct Node<T> {
    next: Option<Shared<Node<T>>>,
    prev: Option<Shared<Node<T>>>,
    element: T,


var node = Hash.new(
     data => 'say what',
     next => foo_node,
     prev => bar_node,

node{:next} = quux_node;  # mutable


{{eff note|Tcl|list}} {{works with|Tcl|8.6}} or {{libheader|TclOO}}

oo::class create List {
    variable content next prev
    constructor {value {list ""}} {
        set content $value
        set next $list
        set prev ""
        if {$next ne ""} {
            $next previous [self]
    method value args {
        set content {*}$args
    method next args {
        set next {*}$args
    method previous args {
        set prev {*}$args

Visual Basic .NET

Public Class Node(Of T)
   Public Value As T
   Public [Next] As Node(Of T)
   Public Previous As Node(Of T)
End Class


class Node{
   fcn init(_value,_prev=Void,_next=Void)
      { var value=_value, prev=_prev, next=_next; }
   fcn toString{ value.toString() }
a.next=b; b.prev=a;
println(a.next,"  ",b.prev);


three  1

{{omit from|ACL2}} {{omit from|TI-83 BASIC}} {{omit from|TI-89 BASIC}}