Doubly-linked list/Traversal

Doubly-linked list/Traversal
You are encouraged to solve this task according to the task description, using any language you may know.

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

Ada

Works with: Ada 2005

<lang Ada>with Ada.Containers.Doubly_Linked_Lists; with Ada.Text_IO;

procedure Traversing is

  package Char_Lists is new Ada.Containers.Doubly_Linked_Lists (Character);

  procedure Print (Position : in Char_Lists.Cursor) is
  begin
     Ada.Text_IO.Put (Char_Lists.Element (Position));
  end Print;

  My_List : Char_Lists.List;

begin

  My_List.Append ('R');
  My_List.Append ('o');
  My_List.Append ('s');
  My_List.Append ('e');
  My_List.Append ('t');
  My_List.Append ('t');
  My_List.Append ('a');

  My_List.Iterate (Print'Access);
  Ada.Text_IO.New_Line;

  My_List.Reverse_Iterate (Print'Access);
  Ada.Text_IO.New_Line;

end Traversing;</lang>

AutoHotkey

see Doubly-linked list/AutoHotkey

C

<lang c>// A doubly linked list of strings;

1. include <stdio.h>
2. include <stdlib.h>
3. include <string.h>

typedef struct sListEntry {

   const char *value;
   struct sListEntry *next;
   struct sListEntry *prev;

} *ListEntry, *LinkedList;

typedef struct sListIterator{

   ListEntry  link;
   LinkedList head;

} *LIterator;

LinkedList NewList() {

   ListEntry le = malloc(sizeof(struct sListEntry));
   if (le) {
       le->value = NULL;
       le->next = le->prev = NULL;
   }
   return le;

}

int LL_Append(LinkedList ll, const char *newVal) {

   ListEntry le = malloc(sizeof(struct sListEntry));
   if (le) {
       le->value = strdup(newVal);
       le->prev = ll->prev;
       le->next = NULL;
       if (le->prev) 
           le->prev->next = le;
       else
           ll->next = le;
       ll->prev = le;
   }
   return (le!= NULL);

}

int LI_Insert(LIterator iter, const char *newVal) {

   ListEntry crnt = iter->link;
   ListEntry le = malloc(sizeof(struct sListEntry));
   if (le) {
       le->value = strdup(newVal);
       if ( crnt == iter->head) {
           le->prev = NULL;
           le->next = crnt->next;
           crnt->next = le;
           if (le->next)
               le->next->prev = le;
           else 
               crnt->prev = le;
       }
       else {
           le->prev = ( crnt == NULL)? iter->head->prev : crnt->prev;
           le->next = crnt;
           if (le->prev)
               le->prev->next = le;
           else
               iter->head->next = le;
           if (crnt) 
               crnt->prev = le;
           else 
               iter->head->prev = le;
       }
   }
   return (le!= NULL);

}

LIterator LL_GetIterator(LinkedList ll ) {

   LIterator liter = malloc(sizeof(struct sListIterator));
   liter->head = ll;
   liter->link = ll;
   return liter;

}

1. define LLI_Delete( iter ) \

   {free(iter); \
   iter = NULL;}

int LLI_AtEnd(LIterator iter) {

   return iter->link == NULL;

} const char *LLI_Value(LIterator iter) {

   return (iter->link)? iter->link->value: NULL;

} int LLI_Next(LIterator iter) {

   if (iter->link) iter->link = iter->link->next;
   return(iter->link != NULL);

} int LLI_Prev(LIterator iter) {

   if (iter->link) iter->link = iter->link->prev;
   return(iter->link != NULL);

}

int main() {

   static const char *contents[] = {"Read", "Orage", "Yeller", 
                                    "Glean", "Blew", "Burple"};
   int ix;
   LinkedList ll = NewList();    //new linked list
   LIterator iter;

   for (ix=0; ix<6; ix++)        //insert contents
       LL_Append(ll, contents[ix]);

   iter = LL_GetIterator(ll);    //get an iterator
   printf("forward\n");
   while(LLI_Next(iter))         //iterate forward
       printf("value=%s\n", LLI_Value(iter));    
   LLI_Delete(iter);             //delete iterator

   printf("\nreverse\n");
   iter = LL_GetIterator(ll);
   while(LLI_Prev(iter))         //iterate reverse 
       printf("value=%s\n", LLI_Value(iter));
   LLI_Delete(iter);
                       //uhhh-- delete list??
   return 0;

}</lang>

C#

<lang C sharp> using System; using System.Collections.Generic;

public class DoubleLinkedList {

   public static void Main(String[] args)
   {

       var ll = new LinkedList<char>(new[] { 'h', 'e', 'l', 'l', 'o' });
       foreach (var c in ll)
       {
           Console.Out.WriteLine(c);
       }

       Console.WriteLine();

       var cur = ll.Last;
       do
       {
           Console.WriteLine(cur.Value);
           cur = cur.Previous;
       } while (cur != 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>

D

<lang>import std.stdio;

struct Node(T) {

   T data;
   Node* prev, next;

   this(T data_, Node* prev_=null, Node* next_=null) {
       data = data_;
       prev = prev_;
       next = next_;
   }

}

void prepend(T)(ref Node!(T)* head, T item) {

   auto newNode = new Node!T(item, null, head);
   if (head)
       head.prev = newNode;
   head = newNode;

}

void main() {

   Node!(string)* head;
   prepend(head, "D");
   prepend(head, "C");
   prepend(head, "B");
   prepend(head, "A");

   auto p = head;
   auto last = p;
   while (p) {
       write(p.data, " ");
       last = p;
       p = p.next;
   }
   writeln();

   while (last) {
       write(last.data, " ");
       last = last.prev;
   }
   writeln();

}</lang> Output:

A B C D 
D C B A 

Delphi

<lang> uses system ;

type

  // declare the list pointer type
  plist = ^List ;

  // declare the list type, a generic data pointer prev and next pointers
  List = record
     data : pointer ;
     prev : pList ;
     next : pList ;
  end;

// since this task is just showing the traversal I am not allocating the memory and setting up the root node etc. // Note the use of the carat symbol for de-referencing the pointer.

begin

  // beginning to end
  while not (pList^.Next = NIL) do pList := pList^.Next ;

  // end to beginning
  while not (pList^.prev = NIL) do pList := pList^.prev ;   

end;

</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()

1. value: <>

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

? traverse(list) 1 2 3 3 2 1</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:

10
20
30
40
40
30
20
10

Uses the print() function from Rhino or SpiderMonkey.

Go

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. <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 (DList a) a (DList a)

create = worker Leaf

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

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>

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

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:

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

</lang>

PicoLisp

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

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

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

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

Next

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>

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

/*===========================subroutines================================*/ sy: say; say left(,30) "---" arg(1) '---'; return p: return word(arg(1),1) @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
        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 meal).

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>

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

}

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

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)

1. Build the list

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

   tail = tail.append(i)

1. Traverse forwards

node = head while node != None:

   print(node.data)
   node = node.next

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