Doubly-linked list/Traversal
From Rosetta Code
(Redirected from Doubly-Linked List (traversal))
Doubly-linked list/Traversal is a programming task. Visitors like you are encouraged to solve it according to the task description, using any language they may happen to know.
Traverse from the beginning of a doubly-linked list to the end, and from the end to the beginning.
Contents |
[edit] C
// A doubly linked list of strings;
#include <stdio.h>
#include <stdlib.h>
#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 = (ListEntry)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 = (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, const 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;
}
#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;
}
[edit] JavaScript
See Doubly-Linked List (element)#JavaScript. The traverse() and print() functions have been inherited from Singly-Linked List (traversal)#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();
outputs:
10 20 30 40 40 30 20 10
Uses the print() function from Rhino or SpiderMonkey.
[edit] 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)
[edit] Oz
Warning: Highly unidiomatic code. (Use built-in lists instead.)
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}
[edit] 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;
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
[edit] 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())
[edit] 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}
[edit] Tcl
Assuming that the List class from this other task is already present...
# 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 }
Which produces this output:
Forward... a b c d Backward... d c b a
[edit] 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.
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
This produces the desired output. However, I expect most python programmers would do the following instead:
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)
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.
Categories: Programming Tasks | Data Structures | Iteration | C | JavaScript | Haskell | Oz | PL/I | PureBasic | Ruby | Tcl | Python
