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


/* 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 the 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;