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.

C

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

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

typedef struct sListEntry {

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

} *ListEntry, *LinkedList;

typedef struct sListIterator{

   ListEntry  link;
   LinkedList head;

} *LIterator;

LinkedList NewList() {

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

}

int LL_Append(LinkedList ll, char *newVal) {

   ListEntry le = (ListEntry)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, char *newVal) {

   ListEntry crnt = iter->link;
   ListEntry le = (ListEntry)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 = (LIterator)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;

} 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(int argc, char *argv[]) {

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

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

   iter = LL_GetIterator(ll);
   printf("forward\n");
   while(LLI_Next(iter)) 
       printf("value=%s\n", LLI_Value(iter));
   
   LLI_Delete(iter)
   printf("\nreverse\n");
   iter = LL_GetIterator(ll);
   while(LLI_Prev(iter)) 
       printf("value=%s\n", LLI_Value(iter));
   return 0;

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

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.