Doubly-linked list/Traversal: Difference between revisions

Content added Content deleted

Inline

Revision as of 08:27, 30 May 2015

Traverse from the beginning of a doubly-linked list to the end, and from the end to the beginning.

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

ALGOL 68

LinkedList.alg: <lang algol68># Node struct - contains next and prev NODE pointers and DATA # MODE NODE = STRUCT(

   DATA data, 
   REF NODE prev, 
   REF NODE next 
   );

List structure - contains head and tail NODE pointers #

MODE LIST = STRUCT(

   REF NODE head, 
   REF NODE tail 
   );

--- PREPEND - Adds a node to the beginning of the list ---#

PRIO PREPEND = 1; #/* Declares the priority of the operation */# OP PREPEND = (REF LIST list, DATA data) VOID: (

   HEAP NODE n := (data, NIL, NIL); # Creates new node on heap #
   IF head OF list IS REF NODE(NIL) THEN
       head OF list := tail OF list := n 
   ELSE
       next OF n := head OF list; 
       prev OF head OF list := head OF list := n
   FI

);

--- APPEND - Adds a node to the end of the list ---#

PRIO APPEND = 1; OP APPEND = (REF LIST list, DATA data) VOID: (

   HEAP NODE n := (data, NIL, NIL);
   IF head OF list IS REF NODE(NIL) THEN
       head OF list := tail OF list := n     
   ELSE
       prev OF n := tail OF list;
       next OF tail OF list := tail OF list := n
   FI

);

--- REMOVE_FIRST - removes & returns node at end of the list ---#

PRIO REMOVE_FIRST = 1; OP REMOVE_FIRST = (REF LIST list) DATA: (

   IF head OF list ISNT REF NODE(NIL) THEN
       DATA d := data OF head OF list;
       prev OF next OF head OF list := NIL;
       head OF list := next OF head OF list;
       d # return d #
   FI

);

--- REMOVE_LAST: removes & returns node at front of list --- #

PRIO REMOVE_LAST = 1; OP REMOVE_LAST = (REF LIST list) DATA: (

   IF head OF list ISNT REF NODE(NIL) THEN
       DATA d := data OF tail OF list;
       next OF prev OF tail OF list := NIL;
       tail OF list := prev OF tail OF list;
       d # return d #
   FI

);

--- PURGE - removes all elements from the list ---#

PRIO PURGE = 2; OP PURGE = (REF LIST list) VOID: (

   head OF list := tail OF list := NIL 
   #/* sets the refs to NIL, allowing the heap to take back the   
  memory */#

);

--- returns the data at the end of the list ---#

PRIO LAST_IN = 2; OP LAST_IN = (REF LIST list) DATA: (

   IF head OF list ISNT REF NODE(NIL) THEN
       data OF tail OF list  
   FI

);

--- returns the data at the front of the list ---#

PRIO FIRST_IN = 2; OP FIRST_IN = (REF LIST list) DATA: (

   IF head OF list ISNT REF NODE(NIL) THEN 
       data OF head OF list 
   FI

);

--- Traverses through the list forwards ---#

PROC forward traversal = (LIST list) VOID: (

   REF NODE travel := head OF list;
   WHILE travel ISNT REF NODE(NIL) DO
       list visit(data OF travel); # call user defined visit #
       travel := next OF travel
   OD

);

--- Traverses through the list backwards ---#

PROC backward traversal = (LIST list) VOID: (

   REF NODE travel := tail OF list;
   WHILE travel ISNT REF NODE(NIL) DO
       list visit(data OF travel);
       travel := prev OF travel
   OD

)</lang>

<lang algol68>PR READ "LinkedList.alg" PR;

MODE EMPLOYEE = STRUCT(STRING name, INT salary, INT years); MODE DATA = EMPLOYEE; #Sets the data type that is in the list#

Function that traversals call for each node in list #

PROC list visit = (REF DATA data) VOID: (

   print((
       "EMPLOYEE NAME  :  ", name OF data ,  newline,
       "         SALARY: " , salary OF data, newline,
       "         YEARS : " , years OF data,  newline
   ))

);

main: (

   EMPLOYEE empl;
   name OF empl := "one";
   salary OF empl := 100;
   years OF empl := 10;
   
   LIST list := (NIL, NIL);

   list PREPEND empl; 
   name OF empl := "two";
   salary OF empl := 200;
   years OF empl := 20;
   list APPEND empl; 
   name OF empl := "three";
   salary OF empl := 300;
   years OF empl := 30;
   list APPEND empl; 
   salary OF empl := 400;
   years OF empl := 40;
   name OF empl := "four";
   list APPEND empl;

   forward traversal(list);
   PURGE list;
   forward traversal(list);

)</lang>

Output:

EMPLOYEE NAME  :  one                                                                                                
         SALARY:        +100                                                                                         
         YEARS :         +10                                                                                         
EMPLOYEE NAME  :  two                                                                                                
         SALARY:        +200                                                                                         
         YEARS :         +20                                                                                         
EMPLOYEE NAME  :  three                                                                                              
         SALARY:        +300                                                                                         
         YEARS :         +30                                                                                         
EMPLOYEE NAME  :  four                                                                                               
         SALARY:        +400                                                                                         
         YEARS :         +40

BBC BASIC

Works with: BBC BASIC for Windows

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

     DIM a{} = node{}, b{} = node{}, c{} = node{}
     
     a.pNext% = b{}
     a.iData% = 123
     b.pPrev% = a{}
     b.iData% = 789
     c.iData% = 456
     
     PROCinsert(a{}, c{})
     
     PRINT "Traverse forwards:"
     pnode% = a{}
     REPEAT
       !(^node{}+4) = pnode%
       PRINT node.iData%
       pnode% = node.pNext%
     UNTIL pnode% = 0
     
     PRINT "Traverse backwards:"
     pnode% = b{}
     REPEAT
       !(^node{}+4) = pnode%
       PRINT node.iData%
       pnode% = node.pPrev%
     UNTIL pnode% = 0
     
     END
     
     DEF PROCinsert(here{}, new{})
     LOCAL temp{} : DIM temp{} = node{}
     new.pNext% = here.pNext%
     new.pPrev% = here{}
     !(^temp{}+4) = new.pNext%
     temp.pPrev% = new{}
     here.pNext% = new{}
     ENDPROC

</lang> Output:

Traverse forwards:
       123
       456
       789
Traverse backwards:
       789
       456
       123

C#

<lang csharp>using System; using System.Collections.Generic;

namespace RosettaCode.DoublyLinkedList {

   internal static class Program
   {
       private static void Main()
       {
           var list = new LinkedList<char>("hello");

           var current = list.First;
           do
           {
               Console.WriteLine(current.Value);
           } while ((current = current.Next) != null);

           Console.WriteLine();

           current = list.Last;
           do
           {
               Console.WriteLine(current.Value);
           } while ((current = current.Previous) != null);
       }
   }

}</lang> Output:

h
e
l
l
o

o
l
l
e
h

Clojure

Given the definition in Doubly-linked list/Definition#Clojure, <lang Clojure>(def dl (double-list [:a :b :c :d]))

=> #'user/dl

((juxt seq rseq) dl)

=> [(: a :b :c :d) (:d :c :b :a)]

(take-while identity (iterate get-next (get-head dl)))

=> (#: double_list.Node{:prev nil, :next #<Object...>, :data :a, :key #<Object...>}
=> #: double_list.Node{:prev #<Object...>, :next #<Object...>, :data :b, :key #<Object...>}
=> #: double_list.Node{:prev #<Object...>, :next #<Object...>, :data :c, :key #<Object...>}
=> #: double_list.Node{:prev #<Object...>, :next nil, :data :d, :key #<Object...>})

(take-while identity (iterate get-prev (get-tail dl)))

=> (#: double_list.Node{:prev #<Object...>, :next nil, :data :d, :key #<Object...>}
=> #: double_list.Node{:prev #<Object...>, :next #<Object...>, :data :c, :key #<Object...>}
=> #: double_list.Node{:prev #<Object...>, :next #<Object...>, :data :b, :key #<Object...>}
=> #: double_list.Node{:prev nil, :next #<Object...>, :data :a, :key #<Object...>})</lang>

E

This example is incorrect. Please fix the code and remove this message.

Details: Doesn't work, probably due to a bug in the list definition: runs over the beginning of the list. Needs debugging.

Given the definition in Doubly-linked list/Definition#E, <lang e>def traverse(list) {

   var node := list.atFirst() 
   while (true) {
       println(node[])
       if (node.hasNext()) {
           node := node.next()
       } else {
           break
       }
   }
   while (true) {
       println(node[])
       if (node.hasPrev()) {
           node := node.prev()
       } else {
           break
       }
   }

}</lang>

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

value: <>

? list.push(1) ? list.push(2) ? list.push(3)

? traverse(list) 1 2 3 3 2 1</lang>

Erlang

The task in Doubly-linked_list/Element_insertion uses traversal as proof that the insertion worked.

Fortran

see Doubly-linked list/Definition#Fortran

Code is identical to that for task Doubly-linked list/Element insertion except for addition of section at the end of main noted "traverse from end to beginning." Traversal from beginning to end is adequately demonstrated by the String method of dlList.

Also note that there is a doubly linked list in the Go standard library in package container/list. <lang go>package main

import "fmt"

type dlNode struct {

   string
   next, prev *dlNode

}

type dlList struct {

   head, tail *dlNode

}

func (list *dlList) String() string {

   if list.head == nil {
       return fmt.Sprint(list.head)
   }
   r := "[" + list.head.string
   for p := list.head.next; p != nil; p = p.next {
       r += " " + p.string
   }
   return r + "]"

}

func (list *dlList) insertTail(node *dlNode) {

   if list.tail == nil {
       list.head = node
   } else {
       list.tail.next = node
   }
   node.next = nil
   node.prev = list.tail
   list.tail = node

}

func (list *dlList) insertAfter(existing, insert *dlNode) {

   insert.prev = existing
   insert.next = existing.next
   existing.next.prev = insert
   existing.next = insert
   if existing == list.tail {
       list.tail = insert
   }

}

func main() {

   dll := &dlList{}
   fmt.Println(dll)
   a := &dlNode{string: "A"}
   dll.insertTail(a)
   dll.insertTail(&dlNode{string: "B"})
   fmt.Println(dll)
   dll.insertAfter(a, &dlNode{string: "C"})
   fmt.Println(dll)

   // traverse from end to beginning
   fmt.Print("From tail:")
   for p := dll.tail; p != nil; p = p.prev {
       fmt.Print(" ", p.string)
   }
   fmt.Println("")

}</lang> Output:

<nil>
[A B]
[A C B]
From tail: B C A

Haskell

<lang haskell>main = print . traverse True $ create [10,20,30,40]

data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) }

create = go Leaf

   where go _    []     = Leaf
         go prev (x:xs) = current
             where current = Node prev x next
                   next    = go current xs

isLeaf Leaf = True isLeaf _ = False

lastNode Leaf = Leaf lastNode dl = until (isLeaf.next) next dl

traverse _ Leaf = [] traverse True (Node l v Leaf) = v : v : traverse False l traverse dir (Node l v r) = v : traverse dir (if dir then r else l)</lang>

Icon and Unicon

Uses Unicon classes. <lang Unicon>class DoubleLink (value, prev_link, next_link)

 # insert given node after this one, removing its existing connections
 method insert_after (node)
   node.prev_link := self
   if (\next_link) then next_link.prev_link := node
   node.next_link := next_link
   self.next_link := node
 end

 # use a generator to traverse 
 # - keep suspending the prev/next link until a null node is reached
 method traverse_backwards () 
   current := self
   while \current do { 
     suspend current
     current := current.prev_link
   }
 end

 method traverse_forwards () 
   current := self
   while \current do {
     suspend current
     current := current.next_link
   }
 end

 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

end

procedure main ()

 l1 := DoubleLink (1)
 l2 := DoubleLink (2)
 l1.insert_after (l2)
 l1.insert_after (DoubleLink (3))

 write ("Traverse from beginning to end")
 every (node := l1.traverse_forwards ()) do  
   write (node.value)

 write ("Traverse from end to beginning")
 every (node := l2.traverse_backwards ()) do  
   write (node.value)

end</lang>

Output:

Traverse from beginning to end
1
3
2
Traverse from end to beginning
2
3
1

J

<lang j>traverse=:1 :0

 work=. result=. conew 'DoublyLinkedListHead'
 current=. y
 while. y ~: current=. successor__current do.
   work=. (work;result;<u data__current) conew 'DoublyLinkedListElement'
 end.
 result

)</lang>

This traverses a doubly linked list, applying the verb u to the data in each list element and creates a new doubly linked list containing the results. A reference to the new doubly linked list is returned.

Java

<lang java>import java.util.LinkedList;

public static void main(){

   LinkedList<String> LL = new LinkedList<String>();
   traverse(LL.iterator());
   traverse(LL.descendingIterator());

}

private static void traverse(Iterator<String> iter){

   while(iter.hasNext()){
       iter.next();
   }

}</lang>

JavaScript

See Doubly-Linked List (element)#JavaScript. The traverse() and print() functions have been inherited from Singly-Linked List (traversal)#JavaScript. <lang javascript>DoublyLinkedList.prototype.getTail = function() {

   var tail;
   this.traverse(function(node){tail = node;});
   return tail;

} DoublyLinkedList.prototype.traverseBackward = function(func) {

   func(this);
   if (this.prev() != null)
       this.prev().traverseBackward(func);

} DoublyLinkedList.prototype.printBackward = function() {

   this.traverseBackward( function(node) {print(node.value())} );

}

var head = createDoublyLinkedListFromArray([10,20,30,40]); head.print(); head.getTail().printBackward();</lang>

outputs:

Uses the print() function from Rhino or SpiderMonkey.

Liberty BASIC

<lang lb> struct block,nxt as ulong,prev as ulong,nm as char[20],age as long'Our structure of the blocks in our list.

global hHeap global hFirst global hLast global blockCount global blockSize blockSize=len(block.struct)

   call Init
   if hHeap=0 then
       print "Error occured! Could not create heap, exiting..."
       end
   end if

   FirstUser=New("David",20)
   notImportant=New("Jessica",35)
   notImportant=New("Joey",38)
   MiddleUser=New("Jack",56)
   notImportant=New("Amy",17)
   notImportant=New("Bob",28)
   LastUser=New("Kenny",56)

   print "-Traversing the list forwards"

   hCurrent=hFirst
   while hCurrent<>0
       print tab(2);dechex$(hCurrent);"   ";Block.name$(hCurrent);"   ";Block.age(hCurrent)
       hCurrent=Block.next(hCurrent)
   wend

   print
   print "-Deleting first, middle, and last person."

   call Delete FirstUser'1
   call Delete MiddleUser'2
   call Delete LastUser'3

   print
   print "-Traversing the list backwards"
   hCurrent=hLast
   while hCurrent<>0
       print tab(2);dechex$(hCurrent);"   ";Block.name$(hCurrent);"   ";Block.age(hCurrent)
       hCurrent=Block.prev(hCurrent)
   wend

call Uninit

end

function Block.next(hBlock)

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   Block.next=block.nxt.struct

end function

function Block.prev(hBlock)

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   Block.prev=block.prev.struct

end function

function Block.age(hBlock)

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   Block.age=block.age.struct

end function

function Block.name$(hBlock)

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   Block.name$=block.nm.struct

end function

sub Block.age hBlock,age

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   block.age.struct=age
   calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void

end sub

sub Block.name hBlock,name$

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   block.nm.struct=name$
   calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void

end sub

sub Block.next hBlock,nxt

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   block.nxt.struct=nxt
   calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void

end sub

sub Block.prev hBlock,prev

   calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
   block.prev.struct=prev
   calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void

end sub

function New(name$,age)

   calldll #kernel32,"HeapAlloc",hHeap as ulong,_HEAP_ZERO_MEMORY as ulong,blockSize as long,New as ulong
   if New<>0 then
       blockCount=blockCount+1
       if hFirst=0 then
           hFirst=New
           hLast=New
       else
           call Block.next hLast,New
           call Block.prev New,hLast
           hLast=New
       end if
       call Block.name New,name$
       call Block.age New,age
   end if

end function

sub Delete hBlock

   if hBlock<>0 then
       blockCount=blockCount-1
       if blockCount=0 then
           hFirst=0
           hLast=0
       else
           if hBlock=hFirst then
               hFirst=Block.next(hBlock)
               call Block.prev hFirst,0
           else
               if hBlock=hLast then
                   hLast=Block.prev(hBlock)
                   call Block.next hLast,0
               else
                   call Block.next Block.prev(hBlock),Block.next(hBlock)
                   call Block.prev Block.next(hBlock),Block.prev(hBlock)
               end if
           end if
       end if
       calldll #kernel32,"HeapFree",hHeap as ulong,0 as long,hBlock as ulong,ret as void
   end if

end sub

sub Init

   calldll #kernel32,"HeapCreate",0 as long,10000 as long,0 as long,hHeap as ulong

end sub

sub Uninit

   calldll #kernel32,"HeapDestroy",hHeap as ulong,ret as void

end sub </lang>

Nim

<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

iterator traverseForward[T](l: List[T]): T =

 var n = l.head
 while n != nil:
   yield n.data
   n = n.next

iterator traverseBackward[T](l: List[T]): T =

 var n = l.tail
 while n != nil:
   yield n.data
   n = n.prev

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)

for i in l.traverseForward():

 echo "> ", i

for i in l.traverseBackward():

 echo "< ", i</lang>

Objeck

<lang objeck> class Traverse {

  function : Main(args : String[]) ~ Nil {
     list := Collection.IntList->New();
     list->Insert(100);
     list->Insert(50);
     list->Insert(25);
     list->Insert(10);
     list->Insert(5);

     "-- forward --"->PrintLine();
     list->Rewind();
     while(list->More()) {
        list->Get()->PrintLine();
        list->Next();
     };

     "-- backward --"->PrintLine();
     list->Forward();
     while(list->More()) {
        list->Get()->PrintLine();
        list->Previous();
     };
  }

} </lang>

-- forward --
100
5
10
25
50
-- backward --
50
25
10
5
100

Oz

Warning: Highly unidiomatic code. (Use built-in lists instead.) <lang oz>declare

 proc {Walk Node Action}
    case Node of nil then skip
    [] node(value:V next:N ...) then

{Action V} {Walk @N Action}

    end
 end

 proc {WalkBackwards Node Action}
    Tail = {GetLast Node}
    proc {Loop N}

case N of nil then skip [] node(value:V prev:P ...) then {Action V} {Loop @P} end

    end
 in
    {Loop Tail}
 end

 fun {GetLast Node}
    case @(Node.next) of nil then Node
    [] NextNode=node(...) then {GetLast NextNode}
    end
 end
 
 fun {CreateNewNode Value}
    node(prev:{NewCell nil}
         next:{NewCell nil}
         value:Value)
 end

 proc {InsertAfter Node NewNode}
    Next = Node.next
 in
    (NewNode.next) := @Next
    (NewNode.prev) := Node
    case @Next of nil then skip
    [] node(prev:NextPrev ...) then
       NextPrev := NewNode
    end
    Next := NewNode
 end

 A = {CreateNewNode a}
 B = {CreateNewNode b}
 C = {CreateNewNode c}

in

 {InsertAfter A B}
 {InsertAfter A C}
 {Walk A Show}
 {WalkBackwards A Show}</lang>

Pascal

See Delphi

Perl 6

Since the list routines are supplied by the generic roles defined in Doubly-linked_list/Definition#Perl_6, it suffices to say: <lang perl6>say $dll.list; say $dll.reverse;</lang> These automatically return just the payloads, hiding the elements containing the forward and backward pointers.

PicoLisp

<lang PicoLisp># Print the elements a doubly-linked list (de 2print (DLst)

  (for (L (car DLst) L (cddr L))
     (printsp (car L)) )
  (prinl) )

Print the elements a doubly-linked list in reverse order

(de 2printReversed (DLst)

  (for (L (cdr DLst) L (cadr L))
     (printsp (car L)) )
  (prinl) )</lang>

Output for the example data produced in Doubly-linked list/Definition#PicoLisp and Doubly-linked list/Element definition#PicoLisp:

: (2print *DLst)                 # Print the list
not was it a cat I saw

: (2printReversed *DLst)         # Print it in reversed order
saw I cat a it was not

Output for the example data produced in Doubly-linked list/Element insertion#PicoLisp:

: (2print *DL)                   # Print the list
A C B

: (2printReversed *DL)           # Print it in reversed order
B C A

PL/I

<lang PL/I>/* To implement a doubly-linked list -- i.e., a 2-way linked list. */ doubly_linked_list: proc options (main);

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

  declare (head, tail, t) handle (node);
  declare null builtin;
  declare i fixed binary;

  head, tail = bind(:node, null:);

  do i = 1 to 10; /* Add ten items to the tail of the queue. */
     if head = bind(:node, null:) then
        do;
           head,tail = new(:node:);
           get list (head => value);
           put skip list (head => value);
           head => back_pointer,
           head => fwd_pointer = bind(:node, null:); /* A NULL link */
        end;
     else
        do;
           t = new(:node:);
           t => back_pointer = tail; /* Point the new tail back to the old */
                                     /* tail.                              */
           tail => fwd_pointer = t;  /* Point the tail to the new node.    */
           t => back_pointer = tail; /* Point the new tail back to the old */
                                     /*  tail.                             */
           tail = t;                 /* Point at teh new tail.             */
           tail => fwd_pointer = bind(:node, null:);
                                     /* Set the tail link to NULL          */
           get list (tail => value) copy;
           put skip list (tail => value);
        end;
  end;

  if head = bind(:node, null:) then return; /* Empty list. */

  /* Traverse the list from the head. */
  put skip list ('In a forwards direction, the list has:');
  t = head;
  do while (t ^= bind(:node, null:));
     put skip list (t => value);
     t = t => fwd_pointer;
  end;
  /* Traverse the list from the tail to the head. */
  put skip list ('In the reverse direction, the list has:');
  t = tail;
  do while (t ^= bind(:node, null:));
     put skip list (t => value);
     t = t => back_pointer;
  end;

end doubly_linked_list;</lang> Output:

In a forwards direction, the list has: 
       1 
       2 
       3 
       4 
       5 
      16 
       7 
       8 
       9 
      10 
In the reverse direction, the list has: 
      10 
       9 
       8 
       7 
      16 
       5 
       4 
       3 
       2 
       1

PureBasic

<lang PureBasic>NewList MyData.i() ; Create a double linked list holding a single value (integer)

Set up a randomly long linked list in the range 25-125 elements

For i=0 To (Random(100)+25)

 AddElement(MyData())        ; Create a new tailing element
 MyData()=Random(314)        ; Inert a vale into it


Traverse from the beginning of a doubly-linked list to the end.

FirstElement(MyData()) Repeat

 Debug MyData()              ; Present the value in the current cell

Until Not NextElement(MyData())


Traverse from the end to the beginning.

LastElement(MyData()) Repeat

  Debug MyData()             ; Present the value in the current cell

Until Not PreviousElement(MyData())</lang>

Python

This provides two solutions. One that explicitly builds a linked list and traverses it two ways, and another which uses pythons combined list/array class. Unless two lists explicitly needed to be spliced together in O(1) time, or a double linked list was needed for some other reason, most python programmers would probably use the second solution. <lang python>class List:

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

   def append(self, data):
       if self.next == None:
           self.next = List(data, None, self)
           return self.next
       else:
           return self.next.append(data)

Build the list

tail = head = List(10) for i in [ 20, 30, 40 ]:

   tail = tail.append(i)

Traverse forwards

node = head while node != None:

   print(node.data)
   node = node.next

Traverse Backwards

node = tail while node != None:

   print(node.data)
   node = node.prev</lang>

This produces the desired output. However, I expect most python programmers would do the following instead:

<lang python>l = [ 10, 20, 30, 40 ] for i in l:

   print(i)

for i in reversed(l): # reversed produces an iterator, so only O(1) memory is used

   print(i)</lang>

Double-ended queues in python are provided by the collections.deque class and the array/list type can perform all the operations of a C++ vector (and more), so building one's own doubly-linked list would be restricted to very specialized situations.

Racket

See Doubly-Linked List for the structure definitions.

These functions traverse the list in the two directions. They create a native (singly-linked) list by adding to the front, so they traverse in the reverse order from the desired result order. <lang racket>(define (dlist-elements dlist)

 (let loop ([elements '()] [dlink (dlist-tail dlist)])
   (if dlink
       (loop (cons (dlink-content dlink) elements) (dlink-prev dlink))
       elements)))

(define (dlist-elements/reverse dlist)

 (let loop ([elements '()] [dlink (dlist-head dlist)])
   (if dlink
       (loop (cons (dlink-content dlink) elements) (dlink-next dlink))
       elements)))</lang>

REXX

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 that implements various List Manager functions. */ /*┌────────────────────────────────────────────────────────────────────┐ ┌─┘ Functions of the List Manager └─┐ │ │ │ @init ─── initializes the List. │ │ │ │ @size ─── returns the size of the List [could be 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. │ └─┐ ┌─┘

 └────────────────────────────────────────────────────────────────────┘*/

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 6th & 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 done.*/ /*──────────────────────────────────subroutines─────────────────────────*/ p: return word(arg(1),1) sy: say; say left(,30) "───" arg(1) '───'; return @hasopt: arg o; return pos(o,opt)\==0 @size: return $.# @init: $.@=; $.#=0; return 0 @adjust: $.@=space($.@); $.#=words($.@); return 0

@parms: arg opt

        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

@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 0

@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(_)

@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 0

@del: procedure expose $.; arg k,m

        call @parms 'km'
        _=subword($.@,k,k-1) subword($.@,k+m)
        $.@=_
        call @adjust
        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 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

Ruby

<lang ruby>class DListNode

 def get_tail
   # parent class (ListNode) includes Enumerable, so the find method is available to us
   self.find {|node| node.succ.nil?}
 end

 def each_previous(&b)
   yield self
   self.prev.each_previous(&b) if self.prev
 end

end

head = DListNode.from_array([:a, :b, :c]) head.each {|node| p node.value} head.get_tail.each_previous {|node| p node.value}</lang>

Salmon

Without explicit type information: <lang Salmon>class item(init_data)

 {
   variable next,
            previous,
            data := init_data;
 };

function prepend(tail, new_data)

 {
   immutable result := item(new_data);
   result.next := tail;
   result.previous := null;
   if (tail != null)
       tail.previous := result;;
   return result;
 };

variable my_list := null; my_list := prepend(my_list, "R"); my_list := prepend(my_list, "o"); my_list := prepend(my_list, "s"); my_list := prepend(my_list, "e"); my_list := prepend(my_list, "t"); my_list := prepend(my_list, "t"); my_list := prepend(my_list, "a");

"Items in the list going forward:"! variable follow := my_list; while (true)

 {
   follow.data!
   if (follow.next == null)
       break;;
 }

step

   follow := follow.next;;

"Items in the list going backward:"! while (follow != null)

   follow.data!

step

   follow := follow.previous;;</lang>

With explicit type information: <lang Salmon>class item(init_data : string)

 {
   variable next: item | {null},
            previous : item | {null},
            data : string := init_data;
 };

function prepend(tail : item | {null}, new_data : string) returns item

 {
   immutable result := item(new_data);
   result.next := tail;
   result.previous := null;
   if (tail != null)
       tail.previous := result;;
   return result;
 };

variable my_list : item | {null} := null; my_list := prepend(my_list, "R"); my_list := prepend(my_list, "o"); my_list := prepend(my_list, "s"); my_list := prepend(my_list, "e"); my_list := prepend(my_list, "t"); my_list := prepend(my_list, "t"); my_list := prepend(my_list, "a");

"Items in the list going forward:"! variable follow : item | {null} := my_list; while (true)

 {
   follow.data!
   if (follow.next == null)
       break;;
 }

step

   follow := follow.next;;

"Items in the list going backward:"! while (follow != null)

   follow.data!

step

   follow := follow.previous;;</lang>

Both of these produce the following output:

Items in the list going forward:
a
t
t
e
s
o
R
Items in the list going backward:
R
o
s
e
t
t
a

Tcl

Assuming that the List class from this other task is already present... <lang tcl># Modify the List class to add the iterator methods oo::define List {

   method foreach {varName script} {
       upvar 1 $varName v
       for {set node [self]} {$node ne ""} {set node [$node next]} {
           set v [$node value]
           uplevel 1 $script
       }
   }
   method revforeach {varName script} {
       upvar 1 $varName v
       for {set node [self]} {$node ne ""} {set node [$node previous]} {
           set v [$node value]
           uplevel 1 $script
       }
   }

}

Demonstrating...

set first [List new a [List new b [List new c [set last [List new d]]]]] puts "Forward..." $first foreach char { puts $char } puts "Backward..." $last revforeach char { puts $char }</lang> Which produces this output:

Forward...
a
b
c
d
Backward...
d
c
b
a

Doubly-linked list/Traversal: Difference between revisions

Revision as of 08:27, 30 May 2015

Ada

ALGOL 68

AutoHotkey

BBC BASIC

C

C#

Clojure

D

Standard Doubly-linked List

User-defined Doubly-linked list

Delphi

E

Erlang

Fortran

Go

Haskell

Icon and Unicon

J

Java

JavaScript

Liberty BASIC

Nim

Objeck

Oz

Pascal

Perl 6

PicoLisp

PL/I

PureBasic

Python

Racket

REXX

Ruby

Salmon

Tcl