Doubly-linked list/Definition: Difference between revisions

Content added Content deleted

Inline

Revision as of 21:53, 8 February 2017

Define the data structure for a complete Doubly Linked List.

The structure should support adding elements to the head, tail and middle of the list.
The structure should not allow circular loops

See also

Array
Associative array: Creation, Iteration
Collections
Compound data type
Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
Linked list
Queue: Definition, Usage
Set
Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
Stack

Ada

Works with: Ada 2005

Examples already in other doubly-linked list tasks: see Doubly-linked list/Element insertion#Ada and Doubly-linked list/Traversal#Ada.

Ada 2005 defines doubly-linked lists in A.18.3 The Package Containers.Doubly_Linked_Lists.

ALGOL 68

Translation of: C

Works with: ALGOL 68 version Revision 1 - one extension to language used - PRAGMA READ - a non standard feature similar to C's #include directive.

Works with: ALGOL 68G version Any - tested with release algol68g-2.7

Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

File: prelude/Doubly-linked_list_Link.a68<lang algol68># -*- coding: utf-8 -*- # COMMENT REQUIRES:

 MODE VALUE = ~;

For example: #

 MODE VALUE = UNION(INT, REAL, COMPL)

END COMMENT

MODE LINKNEW = STRUCT (

 LINK next, prev,
 VALUE value

);

MODE LINK = REF LINKNEW;

SKIP</lang>File: prelude/Doubly-linked_list_Operator.a68<lang algol68># -*- coding: utf-8 -*- # MODE LISTNEW = LINKNEW; MODE LIST = REF LISTNEW;

OP LISTINIT = (LIST self)LIST: (

 self := (self, self, ~);
 self

);

OP ISEMPTY = (LIST self)BOOL:

 (LIST(prev OF self) :=: LIST(self)) AND (LIST(self) :=: LIST(next OF self));

OP HEAD = (LIST self)LINK: next OF self;

OP TAIL = (LIST self)LINK: prev OF self;

insert after #

OP +:= = (LINK cursor, LINK link)LINK: (

 next OF link := next OF cursor;
 prev OF link := cursor;
 next OF cursor := link;
 prev OF next OF link := link;
 link

);

insert before #

OP +=: = (LINK link, LINK cursor)LINK: prev OF cursor +:= link;

delete current and step forward #

OP -:= = (LIST ignore, LINK link)LINK: (

 next OF prev OF link := next OF link;
 prev OF next OF link := prev OF link;
 next OF link := prev OF link := NIL; # garbage collection hint #
 link

);

delete current and step backward #

PRIO -=: = 1; OP -=: = (LIST link, LIST ignore)LINK: (

 ignore -:= link; prev OF link

);

PRIO ISIN = 1; # low priority #

OP ISIN = (LINK link, LIST self)BOOL:

 link ISNT LINK(self);

SKIP</lang>File: test/Doubly-linked_list_Operator_Usage.a68<lang algol68>#!/usr/bin/a68g --script #

-*- coding: utf-8 -*- #

MODE VALUE = STRING; # user defined data type # PR READ "prelude/Doubly-linked_list_Link.a68" PR; PR READ "prelude/Doubly-linked_list_Operator.a68" PR;

main: (

   []VALUE sample = ("Was", "it", "a", "cat", "I", "saw");
   LIST example list := LISTINIT HEAP LISTNEW;
   LINK this;

Add some data to a list #

   FOR i TO UPB sample DO
       this := HEAP LINKNEW;
       value OF this := sample[i];
       TAIL example list +:= this
   OD;

Iterate throught the list forward #

   this := HEAD example list;
   print("Iterate forward: ");
   WHILE this ISIN example list DO
       print((value OF this, " "));
       this := next OF this
   OD;
   print(new line);

Iterate throught the list backward #

   this := TAIL example list;
   print("Iterate backward: ");
   WHILE this ISIN example list DO
       print((value OF this, " "));
       this := prev OF this
   OD;
   print(new line);

Finally empty the list #

   print("Empty from tail: ");
   WHILE NOT ISEMPTY example list DO
         this := (example list -:= TAIL example list);
         print((value OF this, " "))
   OD;
   print(new line)

)</lang>

Output:

Iterate forward: Was it a cat I saw 
Iterate backward: saw I cat a it Was 
Empty from tail: saw I cat a it Was

C++

Works with: C++11

<lang cpp>#include <iostream>

include <list>

int main () {

   std::list<int> numbers {1, 5, 7, 0, 3, 2};
   numbers.insert(numbers.begin(), 9); //Insert at the beginning
   numbers.insert(numbers.end(), 4); //Insert at the end
   auto it = std::next(numbers.begin(), numbers.size() / 2); //Iterator to the middle of the list
   numbers.insert(it, 6); //Insert in the middle
   for(const auto& i: numbers)
       std::cout << i << ' ';
   std::cout << '\n';

}</lang>

Output:

9 1 5 7 6 0 3 2 4

C#

<lang C sharp> using System.Collections.Generic; namespace Doubly_Linked_List {

   class Program
   {
       static void Main(string[] args)
       {
           LinkedList<string> list = new LinkedList<string>();
           list.AddFirst(".AddFirst() adds at the head.");
           list.AddLast(".AddLast() adds at the tail.");
           LinkedListNode<string> head = list.Find(".AddFirst() adds at the head.");
           list.AddAfter(head, ".AddAfter() adds after a specified node.");
           LinkedListNode<string> tail = list.Find(".AddLast() adds at the tail.");
           list.AddBefore(tail, "Betcha can't guess what .AddBefore() does.");

           System.Console.WriteLine("Forward:");
           foreach (string nodeValue in list) { System.Console.WriteLine(nodeValue); }

           System.Console.WriteLine("\nBackward:");
           LinkedListNode<string> current = tail;
           while (current != null)
           {
               System.Console.WriteLine(current.Value);
               current = current.Previous;
           } 
       }
   }

}

/* Output: Forward: .AddFirst() adds at the head. .AddAfter() adds after a specified node. Betcha can't guess what .AddBefore() does. .AddLast() adds at the tail.

Backward: .AddLast() adds at the tail. Betcha can't guess what .AddBefore() does. .AddAfter() adds after a specified node. .AddFirst() adds at the head.

/

</lang>

Clojure

<lang Clojure>(ns double-list)

(defprotocol PDoubleList

 (get-head [this])
 (add-head [this x])
 (get-tail [this])
 (add-tail [this x])
 (remove-node [this node])
 (add-before [this node x])
 (add-after [this node x])
 (get-nth [this n]))

(defrecord Node [prev next data])

(defn make-node

 "Create an internal or finalized node"
 ([prev next data] (Node. prev next data))
 ([m key] (when-let [node (get m key)]
           (assoc node :m m :key key))))

(defn get-next [node] (make-node (:m node) (:next node))) (defn get-prev [node] (make-node (:m node) (:prev node)))

(defn- seq* [m start next]

 (seq
  (for [x (iterate #(get m (next %)) (get m start))
        :while x]
    (:data x))))

(defmacro when->

 ([x pred form] `(let [x# ~x] (if ~pred (-> x# ~form) x#)))
 ([x pred form & more] `(when-> (when-> ~x ~pred ~form) ~@more)))

(declare get-nth-key)

(deftype DoubleList [m head tail]

 Object
   (equals [this x]
     (and (instance? DoubleList x)
          (= m (.m ^DoubleList x))))
   (hashCode [this] (hash (or this ())))
 clojure.lang.Sequential
 clojure.lang.Counted
   (count [_] (count m))
 clojure.lang.Seqable
   (seq [_] (seq* m head :next))
 clojure.lang.Reversible
   (rseq [_] (seq* m tail :prev))
 clojure.lang.IPersistentCollection
   (empty [_] (DoubleList. (empty m) nil nil))
   (equiv [this x]
     (and (sequential? x)
          (= (seq x) (seq this))))
   (cons [this x] (.add-tail this x))
 PDoubleList
   (get-head [_] (make-node m head))
   (add-head [this x]
     (let [new-key (Object.)
           m (when-> (assoc m new-key (make-node nil head x))
               head (assoc-in [head :prev] new-key))
           tail (if tail tail new-key)]
       (DoubleList. m new-key tail)))
   (get-tail [_] (make-node m tail))
   (add-tail [this x]
     (if-let [tail (.get-tail this)]
       (.add-after this tail x)
       (.add-head this x)))
   (remove-node [this node]
     (if (get m (:key node))
       (let [{:keys [prev next key]} node
             head (if prev head next)
             tail (if next tail prev)
             m (when-> (dissoc m key)
                 prev (assoc-in [prev :next] next)
                 next (assoc-in [next :prev] prev))]
         (DoubleList. m head tail))
       this))
   (add-after [this node x]
     (if (get m (:key node))
       (let [{:keys [prev next key]} node
             new-key (Object.)
             m (when-> (-> (assoc m new-key  (make-node key next x))
                           (assoc-in , [key :next] new-key))
                 next (assoc-in [next :prev] new-key))
             tail (if next tail new-key)]
         (DoubleList. m head tail))
       this))
   (add-before [this node x]
     (if (:prev node)
       (.add-after this (get-prev node) x)
       (.add-head this x)))
   (get-nth [this n] (make-node m (get-nth-key this n))))

(defn get-nth-key [^DoubleList this n]

 (if (< -1 n (.count this))
   (let [[start next n] (if (< n (/ (.count this) 2))
                          [(.head this) :next n]
                          [(.tail this) :prev (- (.count this) n 1)])]
     (nth (iterate #(get-in (.m this) [% next]) start) n))
   (throw (IndexOutOfBoundsException.))))

(defn double-list

 ([] (DoubleList. nil nil nil))
 ([coll] (into (double-list) coll)))

(defmethod print-method DoubleList [dl w]

 (print-method (interpose '<-> (seq dl)) w))

(defmethod print-method Node [n w]

 (print-method (symbol "#:double_list.Node") w)
 (print-method (into {} (dissoc n :m)) w))</lang>

Usage: <lang Clojure>(use 'double-list)

=> nil

(def dl (double-list (range 10)))

=> #'user/dl

dl

=> (0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9)

(remove-node dl (get-tail dl))

=> (0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8)

dl

=> (0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9)

((juxt seq rseq) dl)

=> [(0 1 2 3 4 5 6 7 8 9) (9 8 7 6 5 4 3 2 1 0)]

(remove-node dl (get-nth dl 5))

=> (0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 6 <-> 7 <-> 8 <-> 9)

(add-after *1 (get-nth *1 4) 10)

=> (0 <-> 1 <-> 2 <-> 3 <-> 4 <-> 10 <-> 6 <-> 7 <-> 8 <-> 9)

(get-head *1)

=> #: double_list.Node{:prev nil, :next #<Object ...>, :data 0, :key <Object ...>}

(get-next *1)

=> #: double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}

(get-prev *1)

=> #: double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}</lang>

Common Lisp

<lang lisp>(defstruct dlist head tail) (defstruct dlink content prev next)

(defun insert-between (dlist before after data)

 "Insert a fresh link containing DATA after existing link BEFORE if not nil and before existing link AFTER if not nil"
 (let ((new-link (make-dlink :content data :prev before :next after)))
   (if (null before)
       (setf (dlist-head dlist) new-link)
       (setf (dlink-next before) new-link))
   (if (null after)
       (setf (dlist-tail dlist) new-link)
       (setf (dlink-prev after) new-link))
   new-link))

(defun insert-before (dlist dlink data)

 "Insert a fresh link containing DATA before existing link DLINK"
 (insert-between dlist (dlink-prev dlink) dlink data))

(defun insert-after (dlist dlink data)

 "Insert a fresh link containing DATA after existing link DLINK"
 (insert-between dlist dlink (dlink-next dlink) data))

(defun insert-head (dlist data)

 "Insert a fresh link containing DATA at the head of DLIST"
 (insert-between dlist nil (dlist-head dlist) data))

(defun insert-tail (dlist data)

 "Insert a fresh link containing DATA at the tail of DLIST"
 (insert-between dlist (dlist-tail dlist) nil data))

(defun remove-link (dlist dlink)

 "Remove link DLINK from DLIST and return its content"
 (let ((before (dlink-prev dlink))
       (after (dlink-next dlink)))
   (if (null before)
       (setf (dlist-head dlist) after)
       (setf (dlink-next before) after))
   (if (null after)
       (setf (dlist-tail dlist) before)
       (setf (dlink-prev after) before))))

(defun dlist-elements (dlist)

 "Returns the elements of DLIST as a list"
 (labels ((extract-values (dlink acc)
            (if (null dlink)
                acc
                (extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
   (reverse (extract-values (dlist-head dlist) nil))))</lang>

The following produces (1 2 3 4).

<lang lisp>(let ((dlist (make-dlist)))

 (insert-head dlist 1)
 (insert-tail dlist 4)
 (insert-after dlist (dlist-head dlist) 2)
 (let* ((next-to-last (insert-before dlist (dlist-tail dlist) 3))
        (bad-link (insert-before dlist next-to-last 42)))
   (remove-link dlist bad-link))
 (print (dlist-elements dlist)))</lang>

D

<lang d>import std.stdio;

class LinkedList(T) {

Node!(T) head, tail;

/** Iterate in the forward direction. */
int opApply (int delegate(uint, Node!(T)) dg)
{
 uint i = 0;
 auto link = head;
 int result = 0;
 while (link)
 {
  result = dg (i, link);
  if (result) return result;
  i++;
  link = link.next;
 }
 return result;
}

static LinkedList!(T) fromArray (T[] array)
{
 Node!(T) link = null;
 auto head = link;
 auto self = new LinkedList!(T);
 foreach (elem; array)
 {
  link = new Node!(T)(null, link, elem, self);
  if (!head)
   head = link;
 }
 return self;
}

}

class Node(T) {

Node!(T) next;
Node!(T) previous;
LinkedList!(T) parent;
T value;

this (Node!(T) next, Node!(T) previous, T value, LinkedList!(T) parent)
in
{
 assert (parent !is null);
}
body
{
 this.next = next;
 if (next)
  next.previous = this;
 if (previous)
  previous.next = this;
 this.previous = previous;
 this.value = value;
 this.parent = parent;

 if (parent.head == next)
  parent.head = this;
 if (parent.tail == previous)
  parent.tail = this;
}

/** Insert an element after this one. */
void insertAfter (T value)
{
 new Node!(T)(next, this, value, parent);
}

/** Insert an element before this one. */
void insertBefore (T value)
{
 new Node!(T)(this, previous, value, parent);
}

/** Remove the current node from the list. */
void remove ()
{
 if (next)
  next.previous = previous;
 if (previous)
  previous.next = next;
 if (parent.tail == this)
  parent.tail = previous;
 if (parent.head == this)
  parent.head = next;
}

}

void main () {

string[] sample = ["was", "it", "a", "cat", "I", "saw"];
auto list = LinkedList!string.fromArray (sample);
for (auto elem = list.head; elem; elem = elem.next)
{
 writef ("%s ", elem.value);
 if (elem.value == "it") elem.insertAfter("really");
}
writeln;
for (auto elem = list.tail; elem; elem = elem.previous)
{
 writef ("%s ", elem.value);
}
writeln;

}</lang>

Output:

Iterate forward: Was it really a cat I saw 
Iterate backward: saw I cat a really it Was 
Empty from tail: saw I cat a really it Was

E

<lang e>def makeDLList() {

   def firstINode
   def lastINode
   
   def makeNode(var value, var prevI, var nextI) {
       # To meet the requirement that the client cannot create a loop, the 
       # inter-node refs are protected: clients only get the external facet 
       # with invariant-preserving operations.
       def iNode
       
       def node { # external facet
           
           to get() { return value }
           to put(new) { value := new }
           
           /** Return the value of the element of the list at the specified offset
               from this element. */
           to get(index :int) {
               if (index > 0 && node.hasNext()) {
                   return nextI.node().get(index - 1)
               } else if (index < 0 && node.hasPrev()) {
                   return prevI.node().get(index + 1)
               } else if (index <=> 0) {
                   return value
               } else {
                   throw("index out of range in dlList")
               }
           }
           to hasPrev() {
               return prevI != firstINode && prevI != null
           }
           to prev() {
               if (!node.hasPrev()) {
                   throw("there is no previous node")
               }
               return prevI.node()
           }
           to hasNext() {
               return nextI != lastINode && nextI != null
           }
           to next() {
               if (!node.hasNext()) {
                   throw("there is no next node")
               }
               return nextI.node()
           }
           to remove() {
               if (prevI == null || nextI == null) { return }
               prevI.setNextI(nextI)
               nextI.setPrevI(prevI)
               prevI := null
               nextI := null
           }
           to insertAfter(newValue) {
               def newI := makeNode(newValue, iNode, nextI)
               nextI.setPrevI(newI)
               nextI := newI
           }
           to insertBefore(newValue) {
               prevI.node().insertAfter(newValue)
           }
       }
       
       bind iNode { # internal facet
           to node() { return node }
           to nextI() { return nextI }
           to prevI() { return prevI }
           to setNextI(new) { nextI := new }
           to setPrevI(new) { prevI := new }
       }
       
       return iNode
   } # end makeNode

   bind firstINode := makeNode(null, Ref.broken("no first prev"), lastINode)
   bind lastINode := makeNode(null, firstINode, Ref.broken("no last next"))

   def dlList {
       to __printOn(out) {
           out.print("<")
           var sep := ""
           for x in dlList {
               out.print(sep)
               out.quote(x)
               sep := ", "
           }
           out.print(">")
       }
       to iterate(f) {
           var n := firstINode
           while (n.node().hasNext()) {
               n := n.nextI()
               f(n.node(), n.node()[])
           }
       }
       to atFirst() { return firstINode.nextI().node() }
       to atLast() { return lastINode.prevI().node() }
       to insertFirst(new) { return firstINode.node().insertAfter(new) }
       to push(new) { return lastINode.node().insertBefore(new) }
       
       /** Return the node which has the specified value */
       to nodeOf(value) {
           for node => v ? (v == value) in dlList { return node }
       }
   }
   return dlList

}</lang>

<lang e>? def list := makeDLList()

value: <>

? list.push(1) ? list

value: <1>

? list.push(10) ? list.push(100) ? list

value: <1, 10, 100>

? list.atFirst().insertAfter(5) ? list

value: <1, 5, 10, 100>

? list.insertFirst(0) ? list

value: <0, 1, 5, 10, 100>

? list.atLast().prev().remove() ? list

value: <0, 1, 5, 100>

? list.atLast()[] := 10 ? list

value: <0, 1, 5, 10>

? for x in 11..20 { list.push(x) } ? list

value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20></lang>

Erlang

As with Singly-linked_list/Element_insertion a process is used to get mutability in Erlang's single assignment world. <lang Erlang> -module( doubly_linked_list ).

-export( [append/2, foreach_next/2, foreach_previous/2, free/1, insert/3, new/1, task/0] ).

append( New, Start ) -> Start ! {append, New}.

foreach_next( Fun, Start ) -> Start ! {foreach_next, Fun}.

foreach_previous( Fun, Start ) -> Start ! {foreach_previous, Fun}.

free( Element ) -> Element ! {free}.

insert( New, After, Start ) -> Start ! {insert, New, After}.

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

task() ->

   A = new( a ),
   B = new( b ),
   append( B, A ),
   C = new( c ),
   insert( C, A, A ),
   foreach_next( fun(Data) -> io:fwrite("foreach_next ~p~n", [Data]) end, A ),
   timer:sleep( 100 ),
   foreach_previous( fun(Data) -> io:fwrite("foreach_previous ~p~n", [Data]) end, B ).

loop( Data, Previous, Next ) ->

     My_pid = erlang:self(),
     receive
     {append, New} ->
            New_next = loop_append( New, Next, My_pid ),
            loop( Data, Previous, New_next );
     {foreach_next, Fun} ->
               catch Fun( Data ),
               loop_foreach_next( Fun, Next ),
               loop( Data, Previous, Next );
     {foreach_previous, Fun} ->
               catch Fun( Data ),
               loop_foreach_previous( Fun, Previous ),
               loop( Data, Previous, Next );
     {free} ->
            ok;
     {insert, New, My_pid} ->

New ! {previous, My_pid},

            loop_append( Next, New, My_pid ),
            loop( Data, Previous, New );
     {insert, New, After} ->
            Next ! {insert, New, After},
            loop( Data, Previous, Next );
     {previous, New_previous} ->
            loop( Data, New_previous, Next )
       end.

loop_append( New, nonext, My_pid ) ->

       New ! {previous, My_pid},
       New;

loop_append( New, Next, _My_pid ) ->

       Next ! {append, New},
       Next.

loop_foreach_next( _Fun, nonext ) -> ok; loop_foreach_next( Fun, Next ) -> Next ! {foreach_next, Fun}.

loop_foreach_previous( _Fun, noprevious ) -> ok; loop_foreach_previous( Fun, Next ) -> Next ! {foreach_previous, Fun}. </lang>

<lang fsharp>type DListAux<'T> = {mutable prev: DListAux<'T> option; data: 'T; mutable next: DListAux<'T> option} type DList<'T> = {mutable front: DListAux<'T> option; mutable back: DListAux<'T> option} //'

let empty() = {front=None; back=None}

let addFront dlist elt =

 match dlist.front with
 | None ->
     let e = Some {prev=None; data=elt; next=None}
     dlist.front <- e
     dlist.back <- e
 | Some e2 ->
     let e1 = Some {prev=None; data=elt; next=Some e2}
     e2.prev <- e1
     dlist.front <- e1

let addBack dlist elt =

 match dlist.back with
 | None -> addFront dlist elt
 | Some e2 ->
     let e1 = Some {prev=Some e2; data=elt; next=None}
     e2.next <- e1
     dlist.back <- e1

let addAfter dlist link elt =

 if link.next = dlist.back then addBack dlist elt else
   let e = Some {prev=Some link; data=elt; next=link.next}
   link.next <- e</lang>

Fortran

Tested with g95 and gfortran v. 4.6. <lang fortran> module dlist

 implicit none
 type node
    type(node), pointer :: next => null()
    type(node), pointer :: prev => null()
    integer :: data
 end type node

 type dll
    type(node), pointer :: head => null()
    type(node), pointer :: tail => null()
    integer :: num_nodes = 0
 end type dll

 public  :: node, dll, append, prepend, insert, dump, reverse_dump, tidy
 private :: init

contains

 ! Create a new doubly-linked list
 elemental type(dll) function new_dll()
   new_dll = dll(null(),null(),0)
   return
 end function new_dll

 ! Append an element to the end of the list
 elemental subroutine append(dl2, value)
   type(dll), intent(inout) :: dl2
   integer, intent(in)      :: value

   type(node), pointer :: np

   ! If the list is empty
   if (dl2%num_nodes == 0) then
      call init(dl2, value)
      return
   end if

   ! Add new element to the end
   dl2%num_nodes = dl2%num_nodes + 1
   np => dl2%tail
   allocate(dl2%tail)
   dl2%tail%data = value
   dl2%tail%prev => np
   dl2%tail%prev%next => dl2%tail
 end subroutine append

 ! Prepend an element to the beginning of the list
 elemental subroutine prepend(dl2, value)
   type(dll), intent(inout) :: dl2
   integer, intent(in)      :: value

   type(node), pointer :: np

   if (dl2%num_nodes == 0) then
      call init(dl2, value)
      return
   end if

   dl2%num_nodes = dl2%num_nodes + 1
   np => dl2%head
   allocate(dl2%head)
   dl2%head%data = value
   dl2%head%next => np
   dl2%head%next%prev => dl2%head
 end subroutine prepend

 ! Insert immediately before the given index
 elemental subroutine insert(dl2, index, value)
   type(dll), intent(inout) :: dl2
   integer, intent(in)      :: index
   integer, intent(in)      :: value

   type(node), pointer :: element
   type(node), pointer :: np1, np2
   integer             :: i

   if (dl2%num_nodes == 0) then
      call init(dl2, value)
      return
   end if

   ! If index is beyond the end then append
   if (index > dl2%num_nodes) then
      call append(dl2, value)
      return
   end if

   ! If index is less than 1 then prepend
   if (index <= 1) then
      call prepend(dl2, value)
      return
   end if

   ! Find the node at position 'index' counting from 1
   np1 => dl2%head
   do i=1, index-2
      np1 => np1%next
   end do
   np2 => np1%next

   ! Create the new node
   allocate(element)
   element%data = value

   ! Connect it up
   element%prev => np1
   element%next => np2
   np1%next => element
   np2%prev => element
   dl2%num_nodes = dl2%num_nodes + 1
 end subroutine insert

 subroutine dump(dl2)
   type(dll), intent(in) :: dl2
   type(node), pointer :: current
   integer :: i

   write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - fwd = '
   current => dl2%head
   i = 1
   write(*,fmt='(i0,a)',advance='no') current%data,', '
   do
      current => current%next
      if (.not. associated(current)) then
         exit
      end if
      i = i + 1
      if (i == dl2%num_nodes) then
         write(*,'(i0)') current%data
      else
         write(*,fmt='(i0,a)',advance='no') current%data,', '
      end if
   end do
 end subroutine dump

 subroutine reverse_dump(dl2)
   type(dll), intent(in) :: dl2
   type(node), pointer :: current
   integer :: i

   write(*,fmt='(a,i0,a)',advance='no') 'Doubly-linked list has ',dl2%num_nodes,' element - bwd = '
   current => dl2%tail
   write(*,fmt='(i0,a)',advance='no') current%data,', '
   i = 1
   do
      current => current%prev
      if (.not. associated(current)) then
         exit
      end if
      i = i + 1
      if (i == dl2%num_nodes) then
         write(*,'(i0)') current%data
      else
         write(*,fmt='(i0,a)',advance='no') current%data,', '
      end if
   end do
 end subroutine reverse_dump

 ! Deallocate all allocated memory
 elemental subroutine tidy(dl2)
   type(dll), intent(inout) :: dl2
   type(node), pointer :: current, last

   current => dl2%head
   do
      last => current
      current => current%next
      if (associated(last)) then
         deallocate(last)
      end if
      if (associated(current, dl2%tail)) then
         deallocate(current)
         exit
      end if
   end do
 end subroutine tidy

 elemental subroutine init(dl2, value)
   type(dll), intent(inout) :: dl2
   integer, intent(in)      :: value
   allocate(dl2%head)
   dl2%tail => dl2%head
   dl2%tail%data = value
   dl2%num_nodes = 1
   return
 end subroutine init

end module dlist

program dl

 use dlist
 implicit none

 type(dll) :: mydll

 mydll = new_dll()
 call append(mydll, 5)
 call append(mydll, 7)
 call prepend(mydll, 3)
 call prepend(mydll, 1)
 call insert(mydll, 3, 4)
 call dump(mydll)

 call reverse_dump(mydll)

 call tidy(mydll)

end program dl </lang>

Output:

Doubly-linked list has 5 element - fwd = 1, 3, 4, 5, 7
Doubly-linked list has 5 element - bwd = 7, 5, 4, 3, 1

Go

Go has nothing like an enforced invariant. Responsibility for preventing circular loops must be shared by all code that modifies the list. Given that, the following declaration enables code to do that efficiently. <lang go>type dlNode struct {

   int
   next, prev *dlNode

}

// Field 'members' allows loops to be prevented. All nodes // inserted should be added to members. Code that operates // on the list can check any pointer against members to // find out if the pointer is already in the list. type dlList struct {

   members map[*dlNode]int
   head, tail **dlNode

}</lang> Or, just use the container/list package: <lang go>package main

import "fmt" import "container/list"

func main() {

       // Create a new list and put some values in it.
       l := list.New()
       e4 := l.PushBack(4)
       e1 := l.PushFront(1)
       l.InsertBefore(3, e4)
       l.InsertAfter("two", e1)
       
       // Iterate through list and print its contents.
       for e := l.Front(); e != nil; e = e.Next() {
           fmt.Println(e.Value)
       }

}</lang>

Haskell

For an efficient implementation, see the Data.FDList module provided by liboleg. But before using doubly linked lists at all, see this discussion on Stack Overflow.

<lang haskell>import qualified Data.Map as M

type NodeID = Maybe Rational data Node a = Node

  {vNode :: a,
   pNode, nNode :: NodeID}

type DLList a = M.Map Rational (Node a)

empty = M.empty

singleton a = M.singleton 0 $ Node a Nothing Nothing

fcons :: a -> DLList a -> DLList a fcons a list | M.null list = singleton a

            | otherwise   = M.insert newid new $
                            M.insert firstid changed list
 where (firstid, Node firstval _ secondid) = M.findMin list
       newid = firstid - 1
       new     = Node a        Nothing      (Just firstid)
       changed = Node firstval (Just newid) secondid

rcons :: a -> DLList a -> DLList a rcons a list | M.null list = singleton a

            | otherwise   = M.insert lastid changed $
                            M.insert newid new list
 where (lastid, Node lastval penultimateid _) = M.findMax list
       newid = lastid + 1
       changed = Node lastval penultimateid (Just newid)
       new     = Node a       (Just lastid) Nothing

mcons :: a -> Node a -> Node a -> DLList a -> DLList a mcons a n1 n2 = M.insert n1id left .

   M.insert midid mid . M.insert n2id right
 where Node n1val farleftid   (Just n2id) = n1
       Node n2val (Just n1id) farrightid  = n2
       midid = (n1id + n2id) / 2   -- Hence the use of Rationals.
       mid = Node a (Just n1id) (Just n2id)
       left  = Node n1val farleftid    (Just midid)
       right = Node n2val (Just midid) farrightid

firstNode :: DLList a -> Node a firstNode = snd . M.findMin

lastNode :: DLList a -> Node a lastNode = snd . M.findMax

nextNode :: DLList a -> Node a -> Maybe (Node a) nextNode l n = nNode n >>= flip M.lookup l

prevNode :: DLList a -> Node a -> Maybe (Node a) prevNode l n = pNode n >>= flip M.lookup l

fromList = foldr fcons empty

toList = map vNode . M.elems</lang>

An example of use:

<lang haskell>main = putStrLn $ toList l

 where l = mcons 'M' n1 n2 x
       x = rcons 'Z' $ fcons 'a' $ fcons 'q' $ singleton 'w'
       n1 = firstNode x
       Just n2 = nextNode x n1</lang>

Icon and Unicon

Uses Unicon's classes.

The DoubleList is made from elements of DoubleLink. Doubly-Linked List (element)#Icon_and_Unicon, Doubly-Linked List (element insertion)#Icon_and_Unicon and Doubly-Linked List (traversal)#Icon_and_Unicon

<lang Unicon> class DoubleList (item)

 method head ()
   node := item
   every (node := node.traverse_backwards ()) # move to start of list
   return node
 end

 method tail ()
   node := item
   every (node := node.traverse_forwards ()) # move to end of list
   return node
 end
 
 method insert_at_head (value)
   head().insert_before (DoubleLink(value))
 end

 method insert_at_tail (value)
   tail().insert_after (DoubleLink (value))
 end

 # insert a node for new_value after that for target_value, 
 # i.e. in the middle of the list
 method insert_after (target_value, new_value)
   node := head ()
   every node := head().traverse_forwards () do 
     if (node.value = target_value) 
       then { 
         node.insert_after (DoubleLink (new_value))
        break 
       }
 end

 # constructor initiates a list making a node from given value
 initially (value)
   self.item := DoubleLink (value)

end </lang>

An insert_before method was added to the DoubleLink class:

 # insert given node before this one, losing its existing connections
 method insert_before (node)
   if (\prev_link) then prev_link.next_link := node
   node.prev_link := prev_link
   node.next_link := self
   self.prev_link := node
 end

</lang>

To test the double-linked list:

<lang Unicon> procedure main ()

 dlist := DoubleList (5)
 every i := 4 to 1 by -1 do 
   dlist.insert_at_head (i)
 every i := 6 to 10 do
   dlist.insert_at_tail (i)

 dlist.insert_after (3, 11)

 every node := dlist.head().traverse_forwards () do
   write (node.value)

end </lang>

Output:

J

Doubly linked lists are antithetical to J.

First, J already has a built in list data type which is heavily optimized, and micromanaging issues like list traversal bypasses all of that design and architecture.

Second, an implementation of "doubly linked" conflicts with the "once and only once" character of many good implementations. In a doubly linked list order must be specified redundantly and that redundancy creates maintenance costs which are justified only in rare cases.

So, first, here is a native J list:

  list=: 2 3 5 7 11

To implement a doubly linked list, one could create a list of successor indices and another list of predecessor indices.

First, let us define a different order for our list element, so we can easily show that our doubly linked list is logically distinct from the built in list. If we use "alphabeted order by names of numbers" we would have the list 11 5 7 3 2

  data=:11 5 7 3 2

3 is followed by 2
5 is followed by 7
7 is followed by 3
11 is followed by 5

and

2 is preceded by 3
3 is preceded by 7
5 is preceded by 11
7 is preceded by 5

To represent this in J, we can define additional lists with the successor index and predecessor index for each node:

  successors=:   _ 0 3 1 2
  predecessors=: 1 3 4 2 __

Note that the successor for the end of the list is _ and the successor for the beginning of the list is __

To check for loops, look for repeated indices in either of these ordering lists. To add an element to the doubly linked list, you would add an element to the data list, and then update the successor and predecessor list by appending to the end the index of the item designated as the successor/predecessor of the new item and replacing the previous holder of that value with the newly valid index.

Finally, note that we can remove elements from the doubly linked list without removing them from the data list. We might wish to chain removed elements together to facilitate re-use of their positions. If we want to do this, we will need a place to start:

  garbage=: __

When we delete an item we place the old garbage value as its successor index and we define the garbage variable to be the index we just deleted. And when adding to the list we first check if garbage has a valid index and if so we take over that position in the structure and update garbage with the previous value of the successor.

Needless to say, this approach is expensive and inefficient. (But, granted, there will be cases where the cost is worth the expense.)

That said, note also that while the native J lists do not support cycles or loops, this high-cost substitute is general enough to support them.

JavaScript

See Doubly-Linked List (element)#JavaScript, Doubly-Linked List (element insertion)#JavaScript and Doubly-Linked List (traversal)#JavaScript

Nim

Nim has a doubly linked list already in the lists module of the standard library. <lang nim>type

 List[T] = object
   head, tail: Node[T]

 Node[T] = ref TNode[T]

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

proc initList[T](): List[T] = discard

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

 new(result)
 result.data = data

proc prepend[T](l: var List[T], n: Node[T]) =

 n.next = l.head
 if l.head != nil: l.head.prev = n
 l.head = n
 if l.tail == nil: l.tail = n

proc append[T](l: var List[T], n: Node[T]) =

 n.next = nil
 n.prev = l.tail
 if l.tail != nil:
   l.tail.next = n
 l.tail = n
 if l.head == nil:
   l.head = n

proc insertAfter[T](l: var List[T], r, n: Node[T]) =

 n.prev = r
 n.next = r.next
 n.next.prev = n
 r.next = n
 if r == l.tail: l.tail = n

proc remove[T](l: var List[T], n: Node[T]) =

 if n == l.tail: l.tail = n.prev
 if n == l.head: l.head = n.next
 if n.next != nil: n.next.prev = n.prev
 if n.prev != nil: n.prev.next = n.next

proc `$`[T](l: var List[T]): string =

 result = ""
 var n = l.head
 while n != nil:
   if result.len > 0: result.add(" -> ")
   result.add($n.data)
   n = n.next

var l = initList[int]() var n = newNode(12) var m = newNode(13) var i = newNode(14) var j = newNode(15) l.append(n) l.prepend(m) l.insertAfter(m, i) l.prepend(j) l.remove(m) echo l

var l2 = initList[string]() l2.prepend newNode("hello") l2.append newNode("world") echo l2</lang>

Output:

15 -> 14 -> 12
hello -> world

Objeck

<lang objeck> use Collection;

class Program {

 function : Main(args : String[]) ~ Nil {
   list := List->New();
   list->AddFront("first");
   list->AddBack("last");
   list->Insert("middle");

   list->Forward();
   do {
     list->Get()->As(String)->PrintLine();
     list->Previous();
   }
   while(list->Get() <> Nil);
 }

}</lang>

Oforth

<lang oforth>Object Class new: DNode(value, mutable prev, mutable next)

DNode method: initialize := next := prev := value ; DNode method: value @value ; DNode method: prev @prev ; DNode method: next @next ; DNode method: setPrev := prev ; DNode method: setNext := next ; DNode method: << @value << ;

DNode method: insertAfter(node)

  node setPrev(self)
  node setNext(@next)
  @next ifNotNull: [ @next setPrev(node) ]
  node := next ;

// Double linked list definition Collection Class new: DList(mutable head, mutable tail) DList method: head @head ; DList method: tail @tail ;

DList method: insertFront(v) | p |

  @head ->p
  DNode new(v, null, p) := head
  p ifNotNull: [ p setPrev(@head) ]
  @tail ifNull: [ @head := tail ] ;

DList method: insertBack(v) | n |

  @tail ->n
  DNode new(v, n, null) := tail 
  n ifNotNull: [ n setNext(@tail) ]
  @head ifNull: [ @tail := head ] ;

DList method: forEachNext

  dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]
  next dup ifNull: [ drop false ] else: [ dup true ] ;

DList method: forEachPrev

  dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ]
  prev dup ifNull: [ drop false ] else: [ dup true ] ;

test // ( -- aDList )

| dl dn |

  DList new ->dl
  dl insertFront("A") 
  dl insertBack("B")
  dl head insertAfter(DNode new("C", null , null))
  dl ;</lang>

Output:

>test .s
[1] (DList) [A, C, B]

Perl 6

This shows a complete example. (Other entries in the section focus on aspects of this solution.) <lang perl6>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; $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; $elem;

   method delete {

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

}

role DLList[::DLE] {

   has DLE $.first;
   has DLE $.last;

   submethod BUILD {

$!first = DLE.new; $!last = DLE.new; $!first.next = $!last; $!last.prev = $!first;

   method list { ($!first.next, *.next ...^ !*.next).map: *.payload }
   method reverse { ($!last.prev, *.prev ...^ !*.prev).map: *.payload }

}

class DLElem_Int does DLElem[Int] {} class DLList_Int does DLList[DLElem_Int] {}

my $dll = DLList_Int.new;

$dll.first.post-insert(1).post-insert(2).post-insert(3); $dll.first.post-insert(0);

$dll.last.pre-insert(41).pre-insert(40).prev.delete; # (deletes 3) $dll.last.pre-insert(42);

say $dll.list; # 0 1 2 40 41 42 say $dll.reverse; # 42 41 40 2 1 0</lang>

Output:

0 1 2 40 41 42
42 41 40 2 1 0

Phix

See Doubly-linked_list/Traversal for a complete example.

PicoLisp

For the list of double-cell structures described in Doubly-linked list/Element definition#PicoLisp, we define a header structure, containing one pointer to the start and one to the end of the list.

           +------------> start
           |
        +--+--+-----+
        |  |  |  ---+---> end
        +-----+-----+

<lang PicoLisp># Build a doubly-linked list (de 2list @

  (let Prev NIL
     (let L
        (make
           (while (args)
              (setq Prev (chain (list (next) Prev))) ) )
        (cons L Prev) ) ) )

(setq *DLst (2list 'was 'it 'a 'cat 'I 'saw))</lang> For output of the example data, see Doubly-linked list/Traversal#PicoLisp.

PL/I

<lang PL/I> define structure

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

</lang>

PowerShell

Create and populate the list: <lang PowerShell> $list = New-Object -TypeName 'Collections.Generic.LinkedList[PSCustomObject]'

for($i=1; $i -lt 10; $i++) {

  $list.AddLast([PSCustomObject]@{ID=$i; X=100+$i;Y=200+$i}) | Out-Null

}

$list </lang>

Output:

Insert a value at the head: <lang PowerShell> $list.AddFirst([PSCustomObject]@{ID=123; X=123;Y=123}) | Out-Null

$list </lang>

Output:

 ID   X   Y
 --   -   -
123 123 123
  1 101 201
  2 102 202
  3 103 203
  4 104 204
  5 105 205
  6 106 206
  7 107 207
  8 108 208
  9 109 209

Insert a value in the middle: <lang PowerShell> $current = $list.First

while(-not ($current -eq $null)) {

  If($current.Value.X -eq 105)
  {
      $list.AddAfter($current, [PSCustomObject]@{ID=345;X=345;Y=345}) | Out-Null
      break
  }

  $current = $current.Next

}

$list </lang>

Output:

 ID   X   Y
 --   -   -
123 123 123
  1 101 201
  2 102 202
  3 103 203
  4 104 204
  5 105 205
345 345 345
  6 106 206
  7 107 207
  8 108 208
  9 109 209

Insert a value at the end: <lang PowerShell> $list.AddLast([PSCustomObject]@{ID=789; X=789;Y=789}) | Out-Null

$list </lang>

Output:

 ID   X   Y
 --   -   -
123 123 123
  1 101 201
  2 102 202
  3 103 203
  4 104 204
  5 105 205
345 345 345
  6 106 206
  7 107 207
  8 108 208
  9 109 209
789 789 789

PureBasic

<lang PureBasic>DataSection

 ;the list of words that will be added to the list
 words:
 Data.s "One", "Two", "Three", "Four", "Five", "Six", "EndOfData"

EndDataSection

Procedure displayList(List x.s(), title$)

 ;display all elements from list of strings
 Print(title$)  
 ForEach x()
   Print(x() + " ")
 Next
 PrintN("")

EndProcedure

OpenConsole()

NewList a.s() ;create a new list of strings

add words to the head of list

Restore words Repeat

 Read.s a$
 If a$ <> "EndOfData"
   ResetList(a()) ;Move to head of list
   AddElement(a()) 
   a() = a$
 EndIf

Until a$ = "EndOfData" displayList(a(),"Insertion at Head: ")

ClearList(a())

add words to the tail of list

Restore words LastElement(a()) ;Move to the tail of the list Repeat

 Read.s a$
 If a$ <> "EndOfData"
   AddElement(a()) ;after insertion the new position is still at the tail 
   a() = a$
 EndIf

Until a$ = "EndOfData" displayList(a(),"Insertion at Tail: ")

ClearList(a())

add words to the middle of list

Restore words ResetList(a()) ;Move to the tail of the list Repeat

 Read.s a$
 If a$ <> "EndOfData"
   c = CountList(a())
   If c > 1
     SelectElement(a(),Random(c - 2)) ;insert after a random element but before tail
   Else
     FirstElement(a())
   EndIf 
   AddElement(a())
   a() = a$
 EndIf

Until a$ = "EndOfData" displayList(a(),"Insertion in Middle: ")

Repeat: Until Inkey() <> ""</lang>

Output:

Insertion at Head: Six Five Four Three Two One
Insertion at Tail: One Two Three Four Five Six
Insertion at Middle: One Five Six Three Four Two

Python

In the high level language Python, its list native datatype should be used. It automatically preserves the integrity of the list w.r.t. loops and allows insertion at any point using list.insert() via an integer index into the list rather than a machine-code level pointer to a list element.

Racket

The following is a port of the Common Lisp solution. The ouput is '(1 2 3 4).

lang racket

(define-struct dlist (head tail) #:mutable #:transparent) (define-struct dlink (content prev next) #:mutable #:transparent)

(define (insert-between dlist before after data)

 ; Insert a fresh link containing DATA after existing link 
 ; BEFORE if not nil and before existing link AFTER if not nil
 (define new-link (make-dlink data before after))
 (if before
     (set-dlink-next! before new-link)
     (set-dlist-head! dlist new-link))
 (if after
     (set-dlink-prev! after new-link)
     (set-dlist-tail! dlist new-link))
   new-link)

(define (insert-before dlist dlink data)

 ; Insert a fresh link containing DATA before existing link DLINK
 (insert-between dlist (dlink-prev dlink) dlink data))

(define (insert-after dlist dlink data)

 ; Insert a fresh link containing DATA after existing link DLINK
 (insert-between dlist dlink (dlink-next dlink) data))

(define (insert-head dlist data)

 ; Insert a fresh link containing DATA at the head of DLIST
 (insert-between dlist #f (dlist-head dlist) data))

(define (insert-tail dlist data)

 ; Insert a fresh link containing DATA at the tail of DLIST
 (insert-between dlist (dlist-tail dlist) #f data))

(define (remove-link dlist dlink)

 ; Remove link DLINK from DLIST and return its content
 (let ((before (dlink-prev dlink))
       (after (dlink-next dlink)))
   (if before
       (set-dlink-next! before after)
       (set-dlist-head! dlist after))
   (if after
       (set-dlink-prev! after before)
       (set-dlist-tail! dlist before))))

(define (dlist-elements dlist)

 ; Returns the elements of DLIST as a list
 (define (extract-values dlink acc)
   (if dlink
       (extract-values (dlink-next dlink) (cons (dlink-content dlink) acc))
       acc))
 (reverse (extract-values (dlist-head dlist) '())))

(let ((dlist (make-dlist #f #f)))

 (insert-head dlist 1)
 (insert-tail dlist 4)
 (insert-after dlist (dlist-head dlist) 2)
 (let* ((next-to-last (insert-before dlist (dlist-tail dlist) 3))
        (bad-link (insert-before dlist next-to-last 42)))
   (remove-link dlist bad-link))
 (dlist-elements dlist))

</lang>

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 doesn't have linked lists, as there are no pointers (or handles).
However, linked lists can be simulated with lists in REXX. <lang rexx>/*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
        return

/*──────────────────────────────────────────────────────────────────────────────────────*/ @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</lang>

output

                               ─── 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 ───
cat

                               ─── showing 5th & 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).

Ruby

See Doubly-Linked List (element)#Ruby, Doubly-Linked List (element insertion)#Ruby and Doubly-Linked List (traversal)#Ruby

Tcl

This task was earlier marked as unfeasible for Tcl. Tcl lists are compact arrays of pointers to values. However, on very long lists, insertions and deletions (if not at end) may require copying a large amount of data. In such cases, the implementation below may be helpful. It provides a single dl command, which is called with the name of a DList, a method name, and possibly more arguments as required. The testcases below should give a good idea. The asList and asList2 methods demonstrate forward and backward traversal.

See also Doubly-Linked List (element) for a TclOO-based version.

<lang Tcl>package require Tcl 8.4 proc dl {_name cmd {where error} {value ""}} {

   upvar 1 $_name N
   switch -- $cmd {
       insert {
           if ![info exists N()] {set N() {"" "" 0}}
           set id [lindex $N() 2]
           lset N() 2 [incr id]
           switch -- $where {
               head {
                   set prev {}
                   set next [lindex $N() 0]
                   lset N() 0 $id
               }
               end {
                   set prev [lindex $N() 1]
                   set next {}
                   lset N() 1 $id
               }
               default {
                   set prev $where
                   set next [lindex $N($where) 1]
                   lset N($where) 1 $id
               }
           }
           if {$prev ne ""} {lset N($prev) 1 $id}
           if {$next ne ""} {lset N($next) 0 $id}
           if {[lindex $N() 1] eq ""} {lset N() 1 $id}
           set N($id) [list $prev $next $value]
           return $id
       }
       delete {
           set i $where
           if {$where eq "head"} {set i [dl N head]}
           if {$where eq "end"}  {set i [dl N end]}
           foreach {prev next} $N($i) break
           if {$prev ne ""} {lset N($prev) 1 $next}
           if {$next ne ""} {lset N($next) 0 $prev}
           if {[dl N head] == $i} {lset N() 0 $next} 
           if {[dl N end] == $i}  {lset N() 1 $prev}
           unset N($i)
       }
       findfrom {
           if {$where eq "head"} {set where [dl N head]}
           for {set i $where} {$i ne ""} {set i [dl N next $i]} {
               if {[dl N get $i] eq $value} {return $i}
           }
       } 
       get    {lindex $N($where) 2}
       set    {lset   N($where) 2 $value; set value}
       head   {lindex $N() 0}
       end    {lindex $N() 1}
       next   {lindex $N($where) 1}
       prev   {lindex $N($where) 0}
       length {expr {[array size N]-1}}
       asList {
           set res {}
           for {set i [dl N head]} {$i ne ""} {set i [dl N next $i]} {
               lappend res [dl N get $i]
           }
           return $res
       } 
       asList2 {
           set res {}
           for {set i [dl N end]} {$i ne ""} {set i [dl N prev $i]} {
               lappend res [dl N get $i]
           }
           return $res
       } 
   }

}</lang> <lang tcl># Testing code set testcases [split {

   dl D insert head foo
   dl D insert end  bar
   dl D insert head hello
   dl D set [dl D head] hi
   dl D insert end  grill
   set i [dl D findfrom head bar]
   dl D set    $i BAR
   dl D insert $i and
   dl D length
   dl D asList2
   dl D delete $i
   dl D findfrom head nix
   dl D delete head
   dl D delete end
   dl D delete end
   dl D delete head
   dl D length

} \n] foreach case $testcases {

   if {[string trim $case] ne ""} {
       puts " $case -> [eval $case] : [dl D asList]"
       if {[lsearch $argv -p] >= 0} {parray D}
   }

}</lang>

Visual Basic .NET

<lang vbnet>Public Class DoubleLinkList(Of T)

  Private m_Head As Node(Of T)
  Private m_Tail As Node(Of T)

  Public Sub AddHead(ByVal value As T)
      Dim node As New Node(Of T)(Me, value)

      If m_Head Is Nothing Then
          m_Head = Node
          m_Tail = m_Head
      Else
          node.Next = m_Head
          m_Head = node
      End If

  End Sub

  Public Sub AddTail(ByVal value As T)
      Dim node As New Node(Of T)(Me, value)

      If m_Tail Is Nothing Then
          m_Head = node
          m_Tail = m_Head
      Else
          node.Previous = m_Tail
          m_Tail = node
      End If
  End Sub

  Public ReadOnly Property Head() As Node(Of T)
      Get
          Return m_Head
      End Get
  End Property

  Public ReadOnly Property Tail() As Node(Of T)
      Get
          Return m_Tail
      End Get
  End Property

  Public Sub RemoveTail()
      If m_Tail Is Nothing Then Return

      If m_Tail.Previous Is Nothing Then 'empty
          m_Head = Nothing
          m_Tail = Nothing
      Else
          m_Tail = m_Tail.Previous
          m_Tail.Next = Nothing
      End If
  End Sub

  Public Sub RemoveHead()
      If m_Head Is Nothing Then Return

      If m_Head.Next Is Nothing Then 'empty
          m_Head = Nothing
          m_Tail = Nothing
      Else
          m_Head = m_Head.Next
          m_Head.Previous = Nothing
      End If
  End Sub

End Class

Public Class Node(Of T)

  Private ReadOnly m_Value As T
  Private m_Next As Node(Of T)
  Private m_Previous As Node(Of T)
  Private ReadOnly m_Parent As DoubleLinkList(Of T)

  Public Sub New(ByVal parent As DoubleLinkList(Of T), ByVal value As T)
      m_Parent = parent
      m_Value = value
  End Sub

  Public Property [Next]() As Node(Of T)
      Get
          Return m_Next
      End Get
      Friend Set(ByVal value As Node(Of T))
          m_Next = value
      End Set
  End Property

  Public Property Previous() As Node(Of T)
      Get
          Return m_Previous
      End Get
      Friend Set(ByVal value As Node(Of T))
          m_Previous = value
      End Set
  End Property

  Public ReadOnly Property Value() As T
      Get
          Return m_Value
      End Get
  End Property

  Public Sub InsertAfter(ByVal value As T)
      If m_Next Is Nothing Then
          m_Parent.AddTail(value)
      ElseIf m_Previous Is Nothing Then
          m_Parent.AddHead(value)
      Else
          Dim node As New Node(Of T)(m_Parent, value)
          node.Previous = Me
          node.Next = Me.Next
          Me.Next.Previous = node
          Me.Next = node
      End If
  End Sub

  Public Sub Remove()
      If m_Next Is Nothing Then
          m_Parent.RemoveTail()
      ElseIf m_Previous Is Nothing Then
          m_Parent.RemoveHead()
      Else
          m_Previous.Next = Me.Next
          m_Next.Previous = Me.Previous
      End If
  End Sub

End Class</lang>

zkl

<lang zkl>class Node{

  fcn init(_value,_prev=Void,_next=Void)
     { var value=_value, prev=_prev, next=_next; }
  fcn toString{ value.toString() }
  fcn append(value){  // loops not allowed: create a new Node
     b,c := Node(value,self,next),next;
     next=b;
     if(c) c.prev=b;
     b
  }
  fcn delete{ 
     if(prev) prev.next=next;
     if(next) next.prev=prev; 
     self 
  }
  fcn last  { n,p := self,self; while(n){ p,n = n,n.next } p }
  fcn first { n,p := self,self; while(n){ p,n = n,n.prev } p }
  fcn walker(forward=True){
     dir:=forward and "next" or "prev";
     Walker(fcn(rn,dir){ 
        if(not (n:=rn.value)) return(Void.Stop);

rn.set(n.setVar(dir));

        n.value;
     }.fp(Ref(self),dir))
  }

}</lang> <lang zkl>a:=Node("a"); a.append("c").append("d"); a.last().append("e"); a.last().first().append("b"); foreach n in (a){ print(n," ") } println(); foreach n in (a.last().walker(False)){ print(n," ") } println();</lang>

Output:

a  b  c  d  e  
e  d  c  b  a

@@ Line 1,640: / Line 1,640: @@
 <pre>0 1 2 40 41 42
 41 40 2 1 0</pre>
+=={{header|Phix}}==
+See [[Doubly-linked_list/Traversal#Phix|Doubly-linked_list/Traversal]] for a complete example.
 =={{header|PicoLisp}}==

Doubly-linked list/Definition: Difference between revisions

Revision as of 21:53, 8 February 2017

Ada

ALGOL 68

AutoHotkey

C

C++

C#

Clojure

Common Lisp

D

E

Erlang

F#

Fortran

Go

Haskell

Icon and Unicon

J

JavaScript

Nim

Objeck

Oforth

Perl 6

Phix

PicoLisp

PL/I

PowerShell

PureBasic

Python

Racket

REXX

Ruby

Tcl

Visual Basic .NET

zkl