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
<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;
- 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 = 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;
}
- 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>
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
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.
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>
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) )
- 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 } }
}
- 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)
- 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.