Doubly-linked list/Traversal: Difference between revisions
(→{{header|C}}: comment code, minor code fixes) |
m (→{{header|Wren}}: Minor tidy) |
||
(102 intermediate revisions by 64 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Data Structures}} |
{{task|Data Structures}} |
||
[[Category:Iteration]] |
|||
Traverse from the beginning of a doubly-linked list to the end, and from the end to the beginning. |
|||
Traverse from the beginning of a [[Doubly-linked list/Definition|doubly-linked list]] to the end, and from the end to the beginning. |
|||
{{Template:See also lists}} |
|||
<br><br> |
|||
=={{header|Action!}}== |
|||
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
|||
{{libheader|Action! Tool Kit}} |
|||
<syntaxhighlight lang="action!">CARD EndProg ;required for ALLOCATE.ACT |
|||
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
|||
DEFINE PTR="CARD" |
|||
DEFINE NODE_SIZE="6" |
|||
TYPE ListNode=[INT data PTR prv,nxt] |
|||
ListNode POINTER listBegin,listEnd |
|||
PROC Append(INT v) |
|||
ListNode POINTER n |
|||
n=Alloc(NODE_SIZE) |
|||
n.data=v |
|||
n.prv=listEnd |
|||
n.nxt=0 |
|||
IF listEnd THEN |
|||
listEnd.nxt=n |
|||
ELSE |
|||
listBegin=n |
|||
FI |
|||
listEnd=n |
|||
RETURN |
|||
PROC Clear() |
|||
ListNode POINTER n,next |
|||
n=listBegin |
|||
WHILE n |
|||
DO |
|||
next=n.nxt |
|||
Free(n,NODE_SIZE) |
|||
n=next |
|||
OD |
|||
listBegin=0 |
|||
listEnd=0 |
|||
RETURN |
|||
PROC ForwardTraverse() |
|||
ListNode POINTER n |
|||
n=listBegin |
|||
PrintE("Forward traverse:") |
|||
Print("(") |
|||
WHILE n |
|||
DO |
|||
PrintI(n.data) |
|||
IF n.nxt THEN |
|||
Print(", ") |
|||
FI |
|||
n=n.nxt |
|||
OD |
|||
PrintE(")") |
|||
RETURN |
|||
PROC BackwardTraverse() |
|||
ListNode POINTER n |
|||
n=listEnd |
|||
PrintE("Backward traverse") |
|||
Print("(") |
|||
WHILE n |
|||
DO |
|||
PrintI(n.data) |
|||
IF n.prv THEN |
|||
Print(", ") |
|||
FI |
|||
n=n.prv |
|||
OD |
|||
PrintE(")") |
|||
RETURN |
|||
PROC Main() |
|||
INT i |
|||
Put(125) PutE() ;clear screen |
|||
AllocInit(0) |
|||
listBegin=0 |
|||
listEnd=0 |
|||
FOR i=0 TO 50 |
|||
DO |
|||
Append(i*i) |
|||
OD |
|||
ForwardTraverse() |
|||
PutE() |
|||
BackwardTraverse() |
|||
Clear() |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_traversal.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Forward traverse: |
|||
(0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, |
|||
400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, |
|||
1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500) |
|||
Backward traverse |
|||
(2500, 2401, 2304, 2209, 2116, 2025, 1936, 1849, 1764, 1681, 1600, 1521, 1444, 1369, 1296, |
|||
1225, 1156, 1089, 1024, 961, 900, 841, 784, 729, 676, 625, 576, 529, 484, 441, 400, 361, |
|||
324, 289, 256, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1, 0) |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
{{works with|Ada 2005}} |
|||
<syntaxhighlight 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;</syntaxhighlight> |
|||
=={{header|ALGOL 68}}== |
|||
LinkedList.alg:<syntaxhighlight lang="algol68"># Node struct - contains next and prev NODE pointers and DATA # |
|||
MODE NODE = STRUCT( |
|||
DATA data, |
|||
REF NODE prev, |
|||
REF NODE next |
|||
); |
|||
# List structure - contains head and tail NODE pointers # |
|||
MODE LIST = STRUCT( |
|||
REF NODE head, |
|||
REF NODE tail |
|||
); |
|||
# --- PREPEND - Adds a node to the beginning of the list ---# |
|||
PRIO PREPEND = 1; |
|||
OP PREPEND = (REF LIST list, DATA data) VOID: |
|||
( |
|||
HEAP NODE n := (data, NIL, NIL); |
|||
IF head OF list IS REF NODE(NIL) THEN |
|||
head OF list := tail OF list := n |
|||
ELSE |
|||
next OF n := head OF list; |
|||
prev OF head OF list := head OF list := n |
|||
FI |
|||
); |
|||
#--- APPEND - Adds a node to the end of the list ---# |
|||
PRIO APPEND = 1; |
|||
OP APPEND = (REF LIST list, DATA data) VOID: |
|||
( |
|||
HEAP NODE n := (data, NIL, NIL); |
|||
IF head OF list IS REF NODE(NIL) THEN |
|||
head OF list := tail OF list := n |
|||
ELSE |
|||
prev OF n := tail OF list; |
|||
next OF tail OF list := tail OF list := n |
|||
FI |
|||
); |
|||
#--- REMOVE_FIRST - removes & returns node at end of the list ---# |
|||
PRIO REMOVE_FIRST = 1; |
|||
OP REMOVE_FIRST = (REF LIST list) DATA: |
|||
( |
|||
IF head OF list ISNT REF NODE(NIL) THEN |
|||
DATA d := data OF head OF list; |
|||
prev OF next OF head OF list := NIL; |
|||
head OF list := next OF head OF list; |
|||
d # return d # |
|||
FI |
|||
); |
|||
#--- REMOVE_LAST: removes & returns node at front of list --- # |
|||
PRIO REMOVE_LAST = 1; |
|||
OP REMOVE_LAST = (REF LIST list) DATA: |
|||
( |
|||
IF head OF list ISNT REF NODE(NIL) THEN |
|||
DATA d := data OF tail OF list; |
|||
next OF prev OF tail OF list := NIL; |
|||
tail OF list := prev OF tail OF list; |
|||
d # return d # |
|||
FI |
|||
); |
|||
#--- PURGE - removes all elements from the list ---# |
|||
PRIO PURGE = 2; |
|||
OP PURGE = (REF LIST list) VOID: |
|||
( |
|||
head OF list := tail OF list := NIL |
|||
); |
|||
#--- returns the data at the end of the list ---# |
|||
PRIO LAST_IN = 2; |
|||
OP LAST_IN = (REF LIST list) DATA: ( |
|||
IF head OF list ISNT REF NODE(NIL) THEN |
|||
data OF tail OF list |
|||
FI |
|||
); |
|||
#--- returns the data at the front of the list ---# |
|||
PRIO FIRST_IN = 2; |
|||
OP FIRST_IN = (REF LIST list) DATA: ( |
|||
IF head OF list ISNT REF NODE(NIL) THEN |
|||
data OF head OF list |
|||
FI |
|||
); |
|||
#--- Traverses through the list forwards ---# |
|||
PROC forward traversal = (LIST list) VOID: |
|||
( |
|||
REF NODE travel := head OF list; |
|||
WHILE travel ISNT REF NODE(NIL) DO |
|||
list visit(data OF travel); |
|||
travel := next OF travel |
|||
OD |
|||
); |
|||
#--- Traverses through the list backwards ---# |
|||
PROC backward traversal = (LIST list) VOID: |
|||
( |
|||
REF NODE travel := tail OF list; |
|||
WHILE travel ISNT REF NODE(NIL) DO |
|||
list visit(data OF travel); |
|||
travel := prev OF travel |
|||
OD |
|||
)</syntaxhighlight> |
|||
main.alg:<syntaxhighlight lang="algol68">PR READ "LinkedList.alg" PR; |
|||
MODE EMPLOYEE = STRUCT(STRING name, INT salary, INT years); |
|||
MODE DATA = EMPLOYEE; #Sets the data type that is in the list# |
|||
# Function that traversals call for each node in list # |
|||
PROC list visit = (REF DATA data) VOID: |
|||
( |
|||
print(( |
|||
"EMPLOYEE NAME : ", name OF data , newline, |
|||
" SALARY: " , salary OF data, newline, |
|||
" YEARS : " , years OF data, newline |
|||
)) |
|||
); |
|||
#***************************************************************# |
|||
main: |
|||
( |
|||
EMPLOYEE empl; |
|||
name OF empl := "one"; |
|||
salary OF empl := 100; |
|||
years OF empl := 10; |
|||
LIST list := (NIL, NIL); |
|||
list PREPEND empl; |
|||
name OF empl := "two"; |
|||
salary OF empl := 200; |
|||
years OF empl := 20; |
|||
list APPEND empl; |
|||
name OF empl := "three"; |
|||
salary OF empl := 300; |
|||
years OF empl := 30; |
|||
list APPEND empl; |
|||
salary OF empl := 400; |
|||
years OF empl := 40; |
|||
name OF empl := "four"; |
|||
list APPEND empl; |
|||
forward traversal(list); |
|||
PURGE list; |
|||
forward traversal(list) |
|||
)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
EMPLOYEE NAME : one |
|||
SALARY: +100 |
|||
YEARS : +10 |
|||
EMPLOYEE NAME : two |
|||
SALARY: +200 |
|||
YEARS : +20 |
|||
EMPLOYEE NAME : three |
|||
SALARY: +300 |
|||
YEARS : +30 |
|||
EMPLOYEE NAME : four |
|||
SALARY: +400 |
|||
YEARS : +40 |
|||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
Using the element type and insertion routine from the Doubly Linked List/Eleemnt Insertion task. |
|||
<syntaxhighlight lang="algolw">begin |
|||
% record type to hold an element of a doubly linked list of integers % |
|||
record DListIElement ( reference(DListIElement) prev |
|||
; integer iValue |
|||
; reference(DListIElement) next |
|||
); |
|||
% additional record types would be required for other element types % |
|||
% inserts a new element into the list, before e % |
|||
reference(DListIElement) procedure insertIntoDListIBefore( reference(DListIElement) value e |
|||
; integer value v |
|||
); |
|||
begin |
|||
reference(DListIElement) newElement; |
|||
newElement := DListIElement( null, v, e ); |
|||
if e not = null then begin |
|||
% the element we are inserting before is not null % |
|||
reference(DListIElement) ePrev; |
|||
ePrev := prev(e); |
|||
prev(newElement) := ePrev; |
|||
prev(e) := newElement; |
|||
if ePrev not = null then next(ePrev) := newElement |
|||
end if_e_ne_null ; |
|||
newElement |
|||
end insertIntoDListiAfter ; |
|||
begin |
|||
reference(DListIElement) head, e, last; |
|||
head := null; |
|||
head := insertIntoDListIBefore( head, 1701 ); |
|||
head := insertIntoDListIBefore( head, 9000 ); |
|||
e := insertIntoDListIBefore( next(head), 90210 ); |
|||
e := insertIntoDListIBefore( next(e), 4077 ); |
|||
e := head; |
|||
last := null; |
|||
write( "Forward:" ); |
|||
while e not = null do begin |
|||
write( i_w := 1, s_w := 0, " ", iValue(e) ); |
|||
last := e; |
|||
e := next(e) |
|||
end while_e_ne_null ; |
|||
write( "Backward:" ); |
|||
e := last; |
|||
while e not = null do begin |
|||
write( i_w := 1, s_w := 0, " ", iValue(e) ); |
|||
last := e; |
|||
e := prev(e) |
|||
end while_e_ne_null |
|||
end |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Forward: |
|||
9000 |
|||
90210 |
|||
4077 |
|||
1701 |
|||
Backward: |
|||
1701 |
|||
4077 |
|||
90210 |
|||
9000 |
|||
</pre> |
|||
=={{header|Applesoft BASIC}}== |
|||
<syntaxhighlight lang="gwbasic"> 100 REM BUILD THE LIST |
|||
110 FOR I = 20 TO 40 STEP 10 |
|||
120 LET S$ = STR$ (I): GOSUB 260"APPEND" |
|||
130 NEXT I |
|||
140 REM TRAVERSE FORWARDS |
|||
150 LET N = HEAD |
|||
160 FOR Q = 1 TO 1 |
|||
170 IF N < > NIL THEN PRINT S$(N)" ";:N = N(N):Q = 0 |
|||
180 NEXT Q |
|||
190 PRINT |
|||
200 REM TRAVERSE BACKWARDS |
|||
210 LET N = TAIL |
|||
220 FOR Q = 1 TO 1 |
|||
230 IF N < > NIL THEN PRINT S$(N)" ";:N = P(N):Q = 0 |
|||
240 NEXT Q |
|||
250 END |
|||
260 REM APPEND S$ |
|||
270 LET NIL = - 1 |
|||
280 LET P(L) = NIL |
|||
290 LET N(L) = NIL |
|||
300 REM TRAVERSE UNTIL LAST NODE FOUND |
|||
310 FOR Q = 1 TO 1 |
|||
320 IF N(N) < > NIL THEN N = N(N):Q = 0 |
|||
330 NEXT Q |
|||
340 REM NEW NODE |
|||
350 LET S$(L) = S$ |
|||
360 LET N(L) = NIL |
|||
370 IF N < > L THEN P(L) = N |
|||
380 REM POINT THE LAST NODE AT THE NEW NODE |
|||
390 IF N < > L THEN N(N) = L |
|||
400 LET TAIL = L |
|||
410 LET N = TAIL |
|||
420 LET L = L + 1 |
|||
430 RETURN</syntaxhighlight> |
|||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi}} |
|||
<syntaxhighlight lang="arm assembly"> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program transDblList.s */ |
|||
/* REMARK 1 : this program use routines in a include file |
|||
see task Include a file language arm assembly |
|||
for the routine affichageMess conversion10S |
|||
see at end of this program the instruction include */ |
|||
/* Constantes */ |
|||
.equ STDOUT, 1 @ Linux output console |
|||
.equ EXIT, 1 @ Linux syscall |
|||
.equ READ, 3 |
|||
.equ WRITE, 4 |
|||
/*******************************************/ |
|||
/* Structures */ |
|||
/********************************************/ |
|||
/* structure Doublylinkedlist*/ |
|||
.struct 0 |
|||
dllist_head: @ head node |
|||
.struct dllist_head + 4 |
|||
dllist_tail: @ tail node |
|||
.struct dllist_tail + 4 |
|||
dllist_fin: |
|||
/* structure Node Doublylinked List*/ |
|||
.struct 0 |
|||
NDlist_next: @ next element |
|||
.struct NDlist_next + 4 |
|||
NDlist_prev: @ previous element |
|||
.struct NDlist_prev + 4 |
|||
NDlist_value: @ element value or key |
|||
.struct NDlist_value + 4 |
|||
NDlist_fin: |
|||
/* Initialized data */ |
|||
.data |
|||
szMessInitListe: .asciz "List initialized.\n" |
|||
szMessListInv: .asciz "Display list inverse :\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
szMessErreur: .asciz "Error detected.\n" |
|||
/* datas message display */ |
|||
szMessResult: .ascii "Result value :" |
|||
sValue: .space 12,' ' |
|||
.asciz "\n" |
|||
/* UnInitialized data */ |
|||
.bss |
|||
dllist1: .skip dllist_fin @ list memory place |
|||
/* code section */ |
|||
.text |
|||
.global main |
|||
main: |
|||
ldr r0,iAdrdllist1 |
|||
bl newDList @ create new list |
|||
ldr r0,iAdrszMessInitListe |
|||
bl affichageMess |
|||
ldr r0,iAdrdllist1 @ list address |
|||
mov r1,#10 @ value |
|||
bl insertHead @ insertion at head |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 |
|||
mov r1,#20 |
|||
bl insertTail @ insertion at tail |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 @ list address |
|||
mov r1,#10 @ value to after insered |
|||
mov r2,#15 @ new value |
|||
bl insertAfter |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 @ list address |
|||
mov r1,#20 @ value to after insered |
|||
mov r2,#25 @ new value |
|||
bl insertAfter |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 |
|||
bl transHeadTail @ display value head to tail |
|||
ldr r0,iAdrszMessListInv |
|||
bl affichageMess |
|||
ldr r0,iAdrdllist1 |
|||
bl transTailHead @ display value tail to head |
|||
b 100f |
|||
99: |
|||
ldr r0,iAdrszMessErreur |
|||
bl affichageMess |
|||
100: @ standard end of the program |
|||
mov r7, #EXIT @ request to exit program |
|||
svc 0 @ perform system call |
|||
iAdrszMessInitListe: .int szMessInitListe |
|||
iAdrszMessErreur: .int szMessErreur |
|||
iAdrszMessListInv: .int szMessListInv |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrdllist1: .int dllist1 |
|||
/******************************************************************/ |
|||
/* create new list */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
newDList: |
|||
push {r1,lr} @ save registers |
|||
mov r1,#0 |
|||
str r1,[r0,#dllist_tail] |
|||
str r1,[r0,#dllist_head] |
|||
pop {r1,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* list is empty ? */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r0 return 0 if empty else return 1 */ |
|||
isEmpty: |
|||
//push {r1,lr} @ save registers |
|||
ldr r0,[r0,#dllist_head] |
|||
cmp r0,#0 |
|||
movne r0,#1 |
|||
//pop {r1,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value at list head */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value */ |
|||
insertHead: |
|||
push {r1-r4,lr} @ save registers |
|||
mov r4,r0 @ save address |
|||
mov r0,r1 @ value |
|||
bl createNode |
|||
cmp r0,#-1 @ allocation error ? |
|||
beq 100f |
|||
ldr r2,[r4,#dllist_head] @ load address first node |
|||
str r2,[r0,#NDlist_next] @ store in next pointer on new node |
|||
mov r1,#0 |
|||
str r1,[r0,#NDlist_prev] @ store zero in previous pointer on new node |
|||
str r0,[r4,#dllist_head] @ store address new node in address head list |
|||
cmp r2,#0 @ address first node is null ? |
|||
strne r0,[r2,#NDlist_prev] @ no store adresse new node in previous pointer |
|||
streq r0,[r4,#dllist_tail] @ else store new node in tail address |
|||
100: |
|||
pop {r1-r4,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value at list tail */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value */ |
|||
insertTail: |
|||
push {r1-r4,lr} @ save registers |
|||
mov r4,r0 @ save list address |
|||
mov r0,r1 @ value |
|||
bl createNode @ new node |
|||
cmp r0,#-1 |
|||
beq 100f @ allocation error |
|||
ldr r2,[r4,#dllist_tail] @ load address last node |
|||
str r2,[r0,#NDlist_prev] @ store in previous pointer on new node |
|||
mov r1,#0 @ store null un next pointer |
|||
str r1,[r0,#NDlist_next] |
|||
str r0,[r4,#dllist_tail] @ store address new node on list tail |
|||
cmp r2,#0 @ address last node is null ? |
|||
strne r0,[r2,#NDlist_next] @ no store address new node in next pointer |
|||
streq r0,[r4,#dllist_head] @ else store in head list |
|||
100: |
|||
pop {r1-r4,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value after other element */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value to search*/ |
|||
/* r2 contains value to insert */ |
|||
insertAfter: |
|||
push {r1-r5,lr} @ save registers |
|||
mov r4,r0 |
|||
bl searchValue @ search node with this value in r1 |
|||
cmp r0,#-1 |
|||
beq 100f @ not found -> error |
|||
mov r5,r0 @ save address of node find |
|||
mov r0,r2 @ new value |
|||
bl createNode @ create new node |
|||
cmp r0,#-1 |
|||
beq 100f @ allocation error |
|||
ldr r2,[r5,#NDlist_next] @ load pointer next of find node |
|||
str r0,[r5,#NDlist_next] @ store new node in pointer next |
|||
str r5,[r0,#NDlist_prev] @ store address find node in previous pointer on new node |
|||
str r2,[r0,#NDlist_next] @ store pointer next of find node on pointer next on new node |
|||
cmp r2,#0 @ next pointer is null ? |
|||
strne r0,[r2,#NDlist_prev] @ no store address new node in previous pointer |
|||
streq r0,[r4,#dllist_tail] @ else store in list tail |
|||
100: |
|||
pop {r1-r5,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* search value */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains the value to search */ |
|||
/* r0 return address of node or -1 if not found */ |
|||
searchValue: |
|||
push {r2,lr} @ save registers |
|||
ldr r0,[r0,#dllist_head] @ load first node |
|||
1: |
|||
cmp r0,#0 @ null -> end search not found |
|||
moveq r0,#-1 |
|||
beq 100f |
|||
ldr r2,[r0,#NDlist_value] @ load node value |
|||
cmp r2,r1 @ equal ? |
|||
beq 100f |
|||
ldr r0,[r0,#NDlist_next] @ load addresse next node |
|||
b 1b @ and loop |
|||
100: |
|||
pop {r2,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* transversal for head to tail */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
transHeadTail: |
|||
push {r2,lr} @ save registers |
|||
ldr r2,[r0,#dllist_head] @ load first node |
|||
1: |
|||
ldr r0,[r2,#NDlist_value] |
|||
ldr r1,iAdrsValue |
|||
bl conversion10S |
|||
ldr r0,iAdrszMessResult |
|||
bl affichageMess |
|||
ldr r2,[r2,#NDlist_next] |
|||
cmp r2,#0 |
|||
bne 1b |
|||
100: |
|||
pop {r2,lr} @ restaur registers |
|||
bx lr @ return |
|||
iAdrszMessResult: .int szMessResult |
|||
iAdrsValue: .int sValue |
|||
/******************************************************************/ |
|||
/* transversal for tail to head */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
transTailHead: |
|||
push {r2,lr} @ save registers |
|||
ldr r2,[r0,#dllist_tail] @ load last node |
|||
1: |
|||
ldr r0,[r2,#NDlist_value] |
|||
ldr r1,iAdrsValue |
|||
bl conversion10S |
|||
ldr r0,iAdrszMessResult |
|||
bl affichageMess |
|||
ldr r2,[r2,#NDlist_prev] |
|||
cmp r2,#0 |
|||
bne 1b |
|||
100: |
|||
pop {r2,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* Create new node */ |
|||
/******************************************************************/ |
|||
/* r0 contains the value */ |
|||
/* r0 return node address or -1 if allocation error*/ |
|||
createNode: |
|||
push {r1-r7,lr} @ save registers |
|||
mov r4,r0 @ save value |
|||
@ allocation place on the heap |
|||
mov r0,#0 @ allocation place heap |
|||
mov r7,#0x2D @ call system 'brk' |
|||
svc #0 |
|||
mov r5,r0 @ save address heap for output string |
|||
add r0,#NDlist_fin @ reservation place one element |
|||
mov r7,#0x2D @ call system 'brk' |
|||
svc #0 |
|||
cmp r0,#-1 @ allocation error |
|||
beq 100f |
|||
mov r0,r5 |
|||
str r4,[r0,#NDlist_value] @ store value |
|||
mov r2,#0 |
|||
str r2,[r0,#NDlist_next] @ store zero to pointer next |
|||
str r2,[r0,#NDlist_prev] @ store zero to pointer previous |
|||
100: |
|||
pop {r1-r7,lr} @ restaur registers |
|||
bx lr @ return |
|||
/***************************************************/ |
|||
/* ROUTINES INCLUDE */ |
|||
/***************************************************/ |
|||
.include "../affichage.inc" |
|||
</syntaxhighlight> |
|||
=={{header|AutoHotkey}}== |
|||
see [[Doubly-linked list/AutoHotkey]] |
|||
=={{header|Axe}}== |
|||
<syntaxhighlight lang="axe">LINK(L₁,1)→A |
|||
LINK(L₁+10,2)→B |
|||
LINK(L₁+50,3)→C |
|||
INSERT(A,B) |
|||
INSERT(A,C) |
|||
A→I |
|||
While I≠0 |
|||
Disp VALUE(I)▶Dec,i |
|||
NEXT(I)→I |
|||
End |
|||
Disp "-----",i |
|||
B→I |
|||
While I≠0 |
|||
Disp VALUE(I)▶Dec,i |
|||
PREV(I)→I |
|||
End</syntaxhighlight> |
|||
=={{header|BBC BASIC}}== |
|||
{{works with|BBC BASIC for Windows}} |
|||
<syntaxhighlight lang="bbcbasic"> DIM node{pPrev%, pNext%, iData%} |
|||
DIM a{} = node{}, b{} = node{}, c{} = node{} |
|||
a.pNext% = b{} |
|||
a.iData% = 123 |
|||
b.pPrev% = a{} |
|||
b.iData% = 789 |
|||
c.iData% = 456 |
|||
PROCinsert(a{}, c{}) |
|||
PRINT "Traverse forwards:" |
|||
pnode% = a{} |
|||
REPEAT |
|||
!(^node{}+4) = pnode% |
|||
PRINT node.iData% |
|||
pnode% = node.pNext% |
|||
UNTIL pnode% = 0 |
|||
PRINT "Traverse backwards:" |
|||
pnode% = b{} |
|||
REPEAT |
|||
!(^node{}+4) = pnode% |
|||
PRINT node.iData% |
|||
pnode% = node.pPrev% |
|||
UNTIL pnode% = 0 |
|||
END |
|||
DEF PROCinsert(here{}, new{}) |
|||
LOCAL temp{} : DIM temp{} = node{} |
|||
new.pNext% = here.pNext% |
|||
new.pPrev% = here{} |
|||
!(^temp{}+4) = new.pNext% |
|||
temp.pPrev% = new{} |
|||
here.pNext% = new{} |
|||
ENDPROC |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre>Traverse forwards: |
|||
123 |
|||
456 |
|||
789 |
|||
Traverse backwards: |
|||
789 |
|||
456 |
|||
123</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">// A doubly linked list of strings; |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 9: | Line 778: | ||
typedef struct sListEntry { |
typedef struct sListEntry { |
||
char *value; |
const char *value; |
||
struct sListEntry *next; |
struct sListEntry *next; |
||
struct sListEntry *prev; |
struct sListEntry *prev; |
||
Line 20: | Line 789: | ||
LinkedList NewList() { |
LinkedList NewList() { |
||
ListEntry le = |
ListEntry le = malloc(sizeof(struct sListEntry)); |
||
if (le) { |
if (le) { |
||
le->value = NULL; |
le->value = NULL; |
||
Line 28: | Line 797: | ||
} |
} |
||
int LL_Append(LinkedList ll, char *newVal) |
int LL_Append(LinkedList ll, const char *newVal) |
||
{ |
{ |
||
ListEntry le = |
ListEntry le = malloc(sizeof(struct sListEntry)); |
||
if (le) { |
if (le) { |
||
le->value = strdup(newVal); |
le->value = strdup(newVal); |
||
Line 44: | Line 813: | ||
} |
} |
||
int LI_Insert(LIterator iter, char *newVal) |
int LI_Insert(LIterator iter, const char *newVal) |
||
{ |
{ |
||
ListEntry crnt = iter->link; |
ListEntry crnt = iter->link; |
||
ListEntry le = |
ListEntry le = malloc(sizeof(struct sListEntry)); |
||
if (le) { |
if (le) { |
||
le->value = strdup(newVal); |
le->value = strdup(newVal); |
||
Line 77: | Line 846: | ||
LIterator LL_GetIterator(LinkedList ll ) |
LIterator LL_GetIterator(LinkedList ll ) |
||
{ |
{ |
||
LIterator liter = |
LIterator liter = malloc(sizeof(struct sListIterator)); |
||
liter->head = ll; |
liter->head = ll; |
||
liter->link = ll; |
liter->link = ll; |
||
Line 91: | Line 860: | ||
return iter->link == NULL; |
return iter->link == NULL; |
||
} |
} |
||
char *LLI_Value(LIterator iter) |
const char *LLI_Value(LIterator iter) |
||
{ |
{ |
||
return (iter->link)? iter->link->value: NULL; |
return (iter->link)? iter->link->value: NULL; |
||
Line 106: | Line 875: | ||
} |
} |
||
int main( |
int main() |
||
{ |
{ |
||
static char *contents[] = {"Read", "Orage", "Yeller", |
static const char *contents[] = {"Read", "Orage", "Yeller", |
||
"Glean", "Blew", "Burple"}; |
"Glean", "Blew", "Burple"}; |
||
int ix; |
int ix; |
||
LinkedList ll = NewList(); //new linked list |
LinkedList ll = NewList(); //new linked list |
||
Line 130: | Line 899: | ||
//uhhh-- delete list?? |
//uhhh-- delete list?? |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Collections.Generic; |
|||
namespace RosettaCode.DoublyLinkedList |
|||
{ |
|||
internal static class Program |
|||
{ |
|||
private static void Main() |
|||
{ |
|||
var list = new LinkedList<char>("hello"); |
|||
var current = list.First; |
|||
do |
|||
{ |
|||
Console.WriteLine(current.Value); |
|||
} while ((current = current.Next) != null); |
|||
Console.WriteLine(); |
|||
current = list.Last; |
|||
do |
|||
{ |
|||
Console.WriteLine(current.Value); |
|||
} while ((current = current.Previous) != null); |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
h |
|||
e |
|||
l |
|||
l |
|||
o |
|||
o |
|||
l |
|||
l |
|||
e |
|||
h</pre> |
|||
=={{header|C++}}== |
|||
{{works with|C++11}} |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <list> |
|||
int main () |
|||
{ |
|||
std::list<int> numbers {1, 5, 7, 0, 3, 2}; |
|||
for(const auto& i: numbers) |
|||
std::cout << i << ' '; |
|||
std::cout << '\n'; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
1 5 7 0 3 2 |
|||
</pre> |
|||
=={{header|Clojure}}== |
|||
Given the definition in [[../Definition#Clojure]], |
|||
<syntaxhighlight 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...>})</syntaxhighlight> |
|||
=={{header|D}}== |
|||
===Standard Doubly-linked List=== |
|||
<syntaxhighlight lang="d">void main() { |
|||
import std.stdio, std.container, std.range; |
|||
auto dll = DList!dchar("DCBA"d.dup); |
|||
dll[].writeln; |
|||
dll[].retro.writeln; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>ABCD |
|||
DCBA </pre> |
|||
===User-defined Doubly-linked list=== |
|||
Same output. |
|||
<syntaxhighlight lang="d">struct Node(T) { |
|||
T data; |
|||
typeof(this)* prev, next; |
|||
} |
|||
void prepend(T)(ref Node!T* head, in T item) pure nothrow { |
|||
auto newNode = new Node!T(item, null, head); |
|||
if (head) |
|||
head.prev = newNode; |
|||
head = newNode; |
|||
} |
|||
void main() { |
|||
import std.stdio; |
|||
Node!char* head; |
|||
foreach (char c; "DCBA") |
|||
head.prepend(c); |
|||
auto last = head; |
|||
for (auto p = head; p; p = p.next) { |
|||
p.data.write; |
|||
last = p; |
|||
} |
|||
writeln; |
|||
for (auto p = last; p; p = p.prev) |
|||
p.data.write; |
|||
writeln; |
|||
}</syntaxhighlight> |
|||
=={{header|Delphi}}== |
|||
<syntaxhighlight lang="delphi">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;</syntaxhighlight> |
|||
=={{header|E}}== |
|||
{{incorrect|E|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 [[../Definition#E]], |
|||
<syntaxhighlight 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 |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="e">? def list := makeDLList() |
|||
# value: <> |
|||
? list.push(1) |
|||
? list.push(2) |
|||
? list.push(3) |
|||
? traverse(list) |
|||
1 |
|||
2 |
|||
3 |
|||
3 |
|||
2 |
|||
1</syntaxhighlight> |
|||
=={{header|Erlang}}== |
|||
The task in [[Doubly-linked_list/Element_insertion]] uses traversal as proof that the insertion worked. |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
open System.Collections.Generic |
|||
let first (l: LinkedList<char>) = l.First |
|||
let last (l: LinkedList<char>) = l.Last |
|||
let next (l: LinkedListNode<char>) = l.Next |
|||
let prev (l: LinkedListNode<char>) = l.Previous |
|||
let traverse g f (ls: LinkedList<char>) = |
|||
let rec traverse (l: LinkedListNode<char>) = |
|||
match l with |
|||
| null -> () |
|||
| _ -> |
|||
printf "%A" l.Value |
|||
traverse (f l) |
|||
traverse (g ls) |
|||
let traverseForward = traverse first next |
|||
let traverseBackward = traverse last prev |
|||
let cs = LinkedList(['a'..'z']) |
|||
traverseForward cs |
|||
printfn "" |
|||
traverseBackward cs |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
'a''b''c''d''e''f''g''h''i''j''k''l''m''n''o''p''q''r''s''t''u''v''w''x''y''z' |
|||
'z''y''x''w''v''u''t''s''r''q''p''o''n''m''l''k''j''i''h''g''f''e''d''c''b''a' |
|||
</pre> |
|||
=={{header|Fortran}}== |
|||
see [[Doubly-linked list/Definition#Fortran]] |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">Dim As Integer i, MiLista() |
|||
For i = 0 To Int(Rnd * 100)+25 |
|||
Redim Preserve MiLista(i) |
|||
MiLista(i) = Rnd * 314 |
|||
Next |
|||
'Tour from the beginning |
|||
For i = Lbound(MiLista) To Ubound(MiLista) |
|||
Print MiLista(i) |
|||
Next i |
|||
Print |
|||
'Travel from the end |
|||
For i = Ubound(MiLista) To Lbound(MiLista) Step -1 |
|||
Print MiLista(i) |
|||
Next i |
|||
Sleep</syntaxhighlight> |
|||
=={{header|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. |
|||
Also note that there is a doubly linked list in the Go standard library in package container/list. |
|||
<syntaxhighlight 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("") |
|||
}</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
<nil> |
|||
[A B] |
|||
[A C B] |
|||
From tail: B C A |
|||
</pre> |
|||
=={{header|Groovy}}== |
|||
<syntaxhighlight lang="groovy">class DoubleLinkedListTraversing { |
|||
static void main(args) { |
|||
def linkedList = (1..9).collect() as LinkedList |
|||
linkedList.each { |
|||
print it |
|||
} |
|||
println() |
|||
linkedList.reverseEach { |
|||
print it |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>123456789 |
|||
987654321</pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">main = print . traverse True $ create [10,20,30,40] |
|||
data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) } |
|||
create = go Leaf |
|||
where go _ [] = Leaf |
|||
go prev (x:xs) = current |
|||
where current = Node prev x next |
|||
next = go current xs |
|||
isLeaf Leaf = True |
|||
isLeaf _ = False |
|||
lastNode Leaf = Leaf |
|||
lastNode dl = until (isLeaf.next) next dl |
|||
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)</syntaxhighlight> |
|||
==Icon and {{header|Unicon}}== |
|||
Uses Unicon classes. |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
Traverse from beginning to end |
|||
1 |
|||
3 |
|||
2 |
|||
Traverse from end to beginning |
|||
2 |
|||
3 |
|||
1 |
|||
</pre> |
|||
=={{header|J}}== |
|||
<syntaxhighlight 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 |
|||
)</syntaxhighlight> |
|||
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. |
|||
=={{header|Java}}== |
|||
{{works with|Java|8 or higher}} |
|||
<syntaxhighlight lang="java"> |
|||
package com.rosettacode; |
|||
import java.util.LinkedList; |
|||
import java.util.stream.Collectors; |
|||
import java.util.stream.IntStream; |
|||
public class DoubleLinkedListTraversing { |
|||
public static void main(String[] args) { |
|||
final LinkedList<String> doubleLinkedList = |
|||
IntStream.range(1, 10) |
|||
.mapToObj(String::valueOf) |
|||
.collect(Collectors.toCollection(LinkedList::new)); |
|||
doubleLinkedList.iterator().forEachRemaining(System.out::print); |
|||
System.out.println(); |
|||
doubleLinkedList.descendingIterator().forEachRemaining(System.out::print); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>123456789 |
|||
987654321</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
See [[Doubly-Linked List (element)#JavaScript]]. The <code>traverse()</code> and <code>print()</code> functions have been inherited from [[Singly-Linked List (traversal)#JavaScript]]. |
See [[Doubly-Linked List (element)#JavaScript]]. The <code>traverse()</code> and <code>print()</code> functions have been inherited from [[Singly-Linked List (traversal)#JavaScript]]. |
||
< |
<syntaxhighlight lang="javascript">DoublyLinkedList.prototype.getTail = function() { |
||
var tail; |
var tail; |
||
this.traverse(function(node){tail = node;}); |
this.traverse(function(node){tail = node;}); |
||
Line 150: | Line 1,394: | ||
var head = createDoublyLinkedListFromArray([10,20,30,40]); |
var head = createDoublyLinkedListFromArray([10,20,30,40]); |
||
head.print(); |
head.print(); |
||
head.getTail().printBackward();</ |
head.getTail().printBackward();</syntaxhighlight> |
||
outputs: |
outputs: |
||
Line 161: | Line 1,405: | ||
20 |
20 |
||
10</pre> |
10</pre> |
||
Uses the <code>print()</code> function from [[Rhino]] or [[SpiderMonkey]]. |
Uses the <code>print()</code> function from [[Rhino]] or [[SpiderMonkey]]. |
||
=={{header| |
=={{header|Julia}}== |
||
<syntaxhighlight lang="julia">mutable struct DLNode{T} |
|||
<lang haskell> |
|||
value::T |
|||
main = print . traverse True $ create [10,20,30,40] |
|||
pred::Union{DLNode{T}, Nothing} |
|||
succ::Union{DLNode{T}, Nothing} |
|||
DLNode(v) = new{typeof(v)}(v, nothing, nothing) |
|||
end |
|||
function insertpost(prevnode, node) |
|||
data DList a = Leaf | Node (DList a) a (DList a) |
|||
succ = prevnode.succ |
|||
prevnode.succ = node |
|||
node.pred = prevnode |
|||
node.succ = succ |
|||
if succ != nothing |
|||
succ.pred = node |
|||
end |
|||
node |
|||
end |
|||
first(nd) = (while nd.pred != nothing nd = nd.prev end; nd) |
|||
create = worker Leaf |
|||
last(nd) = (while nd.succ != nothing nd = nd.succ end; nd) |
|||
where worker _ [] = Leaf |
|||
worker prev (x:xs) = current |
|||
where current = Node prev x next |
|||
next = worker current xs |
|||
function printconnected(nd; fromtail = false) |
|||
traverse _ Leaf = [] |
|||
if fromtail |
|||
traverse True (Node l v Leaf) = v : v : traverse False l |
|||
nd = last(nd) |
|||
traverse dir (Node l v r) = v : traverse dir (if dir then r else l) |
|||
print(nd.value) |
|||
</lang> |
|||
while nd.pred != nothing |
|||
nd = nd.pred |
|||
print(" -> $(nd.value)") |
|||
end |
|||
else |
|||
nd = first(nd) |
|||
print(nd.value) |
|||
while nd.succ != nothing |
|||
nd = nd.succ |
|||
print(" -> $(nd.value)") |
|||
end |
|||
end |
|||
println() |
|||
end |
|||
node1 = DLNode(1) |
|||
node2 = DLNode(2) |
|||
node3 = DLNode(3) |
|||
insertpost(node1, node2) |
|||
insertpost(node2, node3) |
|||
print("From beginning to end: "); printconnected(node1) |
|||
print("From end to beginning: "); printconnected(node1, fromtail = true) |
|||
</syntaxhighlight> {{output}} <pre> |
|||
From beginning to end: 1 -> 2 -> 3 |
|||
From end to beginning: 3 -> 2 -> 1 |
|||
</pre> |
|||
=={{header|Kotlin}}== |
|||
To complete this task, we just need to add a couple of traversal functions to the class we defined in the [[Doubly-linked list/Definition]] task: |
|||
<syntaxhighlight lang="scala">// version 1.1.2 |
|||
class LinkedList<E> { |
|||
class Node<E>(var data: E, var prev: Node<E>? = null, var next: Node<E>? = null) { |
|||
override fun toString(): String { |
|||
val sb = StringBuilder(this.data.toString()) |
|||
var node = this.next |
|||
while (node != null) { |
|||
sb.append(" -> ", node.data.toString()) |
|||
node = node.next |
|||
} |
|||
return sb.toString() |
|||
} |
|||
} |
|||
var first: Node<E>? = null |
|||
var last: Node<E>? = null |
|||
fun addFirst(value: E) { |
|||
if (first == null) { |
|||
first = Node(value) |
|||
last = first |
|||
} |
|||
else { |
|||
val node = first!! |
|||
first = Node(value, null, node) |
|||
node.prev = first |
|||
} |
|||
} |
|||
fun addLast(value: E) { |
|||
if (last == null) { |
|||
last = Node(value) |
|||
first = last |
|||
} |
|||
else { |
|||
val node = last!! |
|||
last = Node(value, node, null) |
|||
node.next = last |
|||
} |
|||
} |
|||
fun insert(after: Node<E>?, value: E) { |
|||
if (after == null) |
|||
addFirst(value) |
|||
else if (after == last) |
|||
addLast(value) |
|||
else { |
|||
val next = after.next |
|||
val new = Node(value, after, next) |
|||
after.next = new |
|||
if (next != null) next.prev = new |
|||
} |
|||
} |
|||
override fun toString() = first.toString() |
|||
fun firstToLast() = first?.toString() ?: "" |
|||
fun lastToFirst(): String { |
|||
if (last == null) return "" |
|||
val sb = StringBuilder(last.toString()) |
|||
var node = last!!.prev |
|||
while (node != null) { |
|||
sb.append(" -> ", node.data.toString()) |
|||
node = node.prev |
|||
} |
|||
return sb.toString() |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val ll = LinkedList<Int>() |
|||
ll.addFirst(1) |
|||
ll.addLast(4) |
|||
ll.insert(ll.first, 2) |
|||
ll.insert(ll.last!!.prev, 3) |
|||
println("First to last : ${ll.firstToLast()}") |
|||
println("Last to first : ${ll.lastToFirst()}") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
First to last : 1 -> 2 -> 3 -> 4 |
|||
Last to first : 4 -> 3 -> 2 -> 1 |
|||
</pre> |
|||
=={{header|Lua}}== |
|||
Begin with this: [[Doubly-linked_list/Definition#Lua]], then extend with this: |
|||
<syntaxhighlight lang="lua">-------------- |
|||
-- TRAVERSAL: |
|||
-------------- |
|||
List.iterateForward = function(self) |
|||
local function iter(self, node) |
|||
if node then return node.next else return self.head end |
|||
end |
|||
return iter, self, nil |
|||
end |
|||
List.iterateReverse = function(self) |
|||
local function iter(self, node) |
|||
if node then return node.prev else return self.tail end |
|||
end |
|||
return iter, self, nil |
|||
end |
|||
--------- |
|||
-- TEST: |
|||
--------- |
|||
local list = List() |
|||
for i = 1, 5 do list:insertTail(i) end |
|||
io.write("Forward: ") for node in list:iterateForward() do io.write(node.data..",") end print() |
|||
io.write("Reverse: ") for node in list:iterateReverse() do io.write(node.data..",") end print()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Forward: 1,2,3,4,5, |
|||
Reverse: 5,4,3,2,1,</pre> |
|||
=={{header|Liberty BASIC}}== |
|||
<syntaxhighlight lang="lb"> |
|||
struct block,nxt as ulong,prev as ulong,nm as char[20],age as long'Our structure of the blocks in our list. |
|||
global hHeap |
|||
global hFirst |
|||
global hLast |
|||
global blockCount |
|||
global blockSize |
|||
blockSize=len(block.struct) |
|||
call Init |
|||
if hHeap=0 then |
|||
print "Error occured! Could not create heap, exiting..." |
|||
end |
|||
end if |
|||
FirstUser=New("David",20) |
|||
notImportant=New("Jessica",35) |
|||
notImportant=New("Joey",38) |
|||
MiddleUser=New("Jack",56) |
|||
notImportant=New("Amy",17) |
|||
notImportant=New("Bob",28) |
|||
LastUser=New("Kenny",56) |
|||
print "-Traversing the list forwards" |
|||
hCurrent=hFirst |
|||
while hCurrent<>0 |
|||
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent) |
|||
hCurrent=Block.next(hCurrent) |
|||
wend |
|||
print |
|||
print "-Deleting first, middle, and last person." |
|||
call Delete FirstUser'1 |
|||
call Delete MiddleUser'2 |
|||
call Delete LastUser'3 |
|||
print |
|||
print "-Traversing the list backwards" |
|||
hCurrent=hLast |
|||
while hCurrent<>0 |
|||
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent) |
|||
hCurrent=Block.prev(hCurrent) |
|||
wend |
|||
call Uninit |
|||
end |
|||
function Block.next(hBlock) |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
Block.next=block.nxt.struct |
|||
end function |
|||
function Block.prev(hBlock) |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
Block.prev=block.prev.struct |
|||
end function |
|||
function Block.age(hBlock) |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
Block.age=block.age.struct |
|||
end function |
|||
function Block.name$(hBlock) |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
Block.name$=block.nm.struct |
|||
end function |
|||
sub Block.age hBlock,age |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
block.age.struct=age |
|||
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void |
|||
end sub |
|||
sub Block.name hBlock,name$ |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
block.nm.struct=name$ |
|||
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void |
|||
end sub |
|||
sub Block.next hBlock,nxt |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
block.nxt.struct=nxt |
|||
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void |
|||
end sub |
|||
sub Block.prev hBlock,prev |
|||
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void |
|||
block.prev.struct=prev |
|||
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void |
|||
end sub |
|||
function New(name$,age) |
|||
calldll #kernel32,"HeapAlloc",hHeap as ulong,_HEAP_ZERO_MEMORY as ulong,blockSize as long,New as ulong |
|||
if New<>0 then |
|||
blockCount=blockCount+1 |
|||
if hFirst=0 then |
|||
hFirst=New |
|||
hLast=New |
|||
else |
|||
call Block.next hLast,New |
|||
call Block.prev New,hLast |
|||
hLast=New |
|||
end if |
|||
call Block.name New,name$ |
|||
call Block.age New,age |
|||
end if |
|||
end function |
|||
sub Delete hBlock |
|||
if hBlock<>0 then |
|||
blockCount=blockCount-1 |
|||
if blockCount=0 then |
|||
hFirst=0 |
|||
hLast=0 |
|||
else |
|||
if hBlock=hFirst then |
|||
hFirst=Block.next(hBlock) |
|||
call Block.prev hFirst,0 |
|||
else |
|||
if hBlock=hLast then |
|||
hLast=Block.prev(hBlock) |
|||
call Block.next hLast,0 |
|||
else |
|||
call Block.next Block.prev(hBlock),Block.next(hBlock) |
|||
call Block.prev Block.next(hBlock),Block.prev(hBlock) |
|||
end if |
|||
end if |
|||
end if |
|||
calldll #kernel32,"HeapFree",hHeap as ulong,0 as long,hBlock as ulong,ret as void |
|||
end if |
|||
end sub |
|||
sub Init |
|||
calldll #kernel32,"HeapCreate",0 as long,10000 as long,0 as long,hHeap as ulong |
|||
end sub |
|||
sub Uninit |
|||
calldll #kernel32,"HeapDestroy",hHeap as ulong,ret as void |
|||
end sub |
|||
</syntaxhighlight> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">type |
|||
List[T] = object |
|||
head, tail: Node[T] |
|||
Node[T] = ref TNode[T] |
|||
TNode[T] = object |
|||
next, prev: Node[T] |
|||
data: T |
|||
proc initList[T](): List[T] = discard |
|||
proc newNode[T](data: T): Node[T] = |
|||
new(result) |
|||
result.data = data |
|||
proc prepend[T](l: var List[T], n: Node[T]) = |
|||
n.next = l.head |
|||
if l.head != nil: l.head.prev = n |
|||
l.head = n |
|||
if l.tail == nil: l.tail = n |
|||
proc append[T](l: var List[T], n: Node[T]) = |
|||
n.next = nil |
|||
n.prev = l.tail |
|||
if l.tail != nil: |
|||
l.tail.next = n |
|||
l.tail = n |
|||
if l.head == nil: |
|||
l.head = n |
|||
proc insertAfter[T](l: var List[T], r, n: Node[T]) = |
|||
n.prev = r |
|||
n.next = r.next |
|||
n.next.prev = n |
|||
r.next = n |
|||
if r == l.tail: l.tail = n |
|||
proc remove[T](l: var List[T], n: Node[T]) = |
|||
if n == l.tail: l.tail = n.prev |
|||
if n == l.head: l.head = n.next |
|||
if n.next != nil: n.next.prev = n.prev |
|||
if n.prev != nil: n.prev.next = n.next |
|||
proc `$`[T](l: var List[T]): string = |
|||
result = "" |
|||
var n = l.head |
|||
while n != nil: |
|||
if result.len > 0: result.add(" -> ") |
|||
result.add($n.data) |
|||
n = n.next |
|||
iterator traverseForward[T](l: List[T]): T = |
|||
var n = l.head |
|||
while n != nil: |
|||
yield n.data |
|||
n = n.next |
|||
iterator traverseBackward[T](l: List[T]): T = |
|||
var n = l.tail |
|||
while n != nil: |
|||
yield n.data |
|||
n = n.prev |
|||
var l = initList[int]() |
|||
var n = newNode(12) |
|||
var m = newNode(13) |
|||
var i = newNode(14) |
|||
var j = newNode(15) |
|||
l.append(n) |
|||
l.prepend(m) |
|||
l.insertAfter(m, i) |
|||
l.prepend(j) |
|||
l.remove(m) |
|||
for i in l.traverseForward(): |
|||
echo "> ", i |
|||
for i in l.traverseBackward(): |
|||
echo "< ", i</syntaxhighlight> |
|||
=={{header|Oberon-2}}== |
|||
<syntaxhighlight lang="oberon2"> |
|||
MODULE Collections; |
|||
IMPORT Box; |
|||
TYPE |
|||
Action = PROCEDURE (o: Box.Object); |
|||
PROCEDURE (dll: DLList) GoForth*(do: Action); |
|||
VAR |
|||
iter: Node; |
|||
BEGIN |
|||
iter := dll.first; |
|||
WHILE iter # NIL DO |
|||
do(iter.value); |
|||
iter := iter.next |
|||
END |
|||
END GoForth; |
|||
PROCEDURE (dll: DLList) GoBack*(do: Action); |
|||
VAR |
|||
iter: Node; |
|||
BEGIN |
|||
ASSERT(dll.last # NIL); |
|||
iter := dll.last; |
|||
WHILE iter # NIL DO |
|||
do(iter.value); |
|||
iter := iter.prev |
|||
END |
|||
END GoBack; |
|||
END Collections. |
|||
</syntaxhighlight> |
|||
=={{header|Objeck}}== |
|||
<syntaxhighlight lang="objeck"> |
|||
class Traverse { |
|||
function : Main(args : String[]) ~ Nil { |
|||
list := Collection.IntList->New(); |
|||
list->Insert(100); |
|||
list->Insert(50); |
|||
list->Insert(25); |
|||
list->Insert(10); |
|||
list->Insert(5); |
|||
"-- forward --"->PrintLine(); |
|||
list->Rewind(); |
|||
while(list->More()) { |
|||
list->Get()->PrintLine(); |
|||
list->Next(); |
|||
}; |
|||
"-- backward --"->PrintLine(); |
|||
list->Forward(); |
|||
while(list->More()) { |
|||
list->Get()->PrintLine(); |
|||
list->Previous(); |
|||
}; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
<pre> |
|||
-- forward -- |
|||
100 |
|||
5 |
|||
10 |
|||
25 |
|||
50 |
|||
-- backward -- |
|||
50 |
|||
25 |
|||
10 |
|||
5 |
|||
100 |
|||
</pre> |
|||
=={{header|Oforth}}== |
|||
Complete definition is here : [[../Definition#Oforth]] |
|||
Defining #forEachNext and #forEachPrev allow to traverse this double linked list using #forEach: and #revEach: syntax |
|||
<syntaxhighlight lang="oforth">DList method: forEachNext |
|||
dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ] |
|||
next dup ifNull: [ drop false ] else: [ dup true ] ; |
|||
DList method: forEachPrev |
|||
dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ] |
|||
prev dup ifNull: [ drop false ] else: [ dup true ] ; |
|||
: test |
|||
| dl n | |
|||
DList new ->dl |
|||
dl insertFront("A") |
|||
dl insertBack("B") |
|||
dl head insertAfter(DNode new("C", null , null)) |
|||
"Traversal (beginning to end) : " println |
|||
dl forEach: n [ n . ] |
|||
"\nTraversal (end to beginning) : " println |
|||
dl revEach: n [ n . ] ;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
>test |
|||
Traversal (beginning to end) : |
|||
A C B |
|||
Traversal (end to beginning) : |
|||
B C A ok |
|||
</pre> |
|||
=={{header|Oz}}== |
|||
Warning: Highly unidiomatic code. (Use built-in lists instead.) |
|||
<syntaxhighlight 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}</syntaxhighlight> |
|||
=={{header|Pascal}}== |
|||
See [[Doubly-linked_list/Traversal#Delphi | Delphi]] |
|||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">enum</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DATA</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">empty_dll</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}}</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">empty_dll</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">prv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">dll</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">prv</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">prv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ONE"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TWO"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">insert_after</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"THREE"</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">DATA</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dll</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"=="</span> |
|||
<span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">)</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}} |
|||
"ONE" |
|||
"TWO" |
|||
"THREE" |
|||
"==" |
|||
"THREE" |
|||
"TWO" |
|||
"ONE" |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight 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) )</syntaxhighlight> |
|||
Output for the example data produced in |
|||
[[Doubly-linked list/Definition#PicoLisp]] and |
|||
[[Doubly-linked list/Element definition#PicoLisp]]: |
|||
<pre>: (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</pre> |
|||
Output for the example data produced in |
|||
[[Doubly-linked list/Element insertion#PicoLisp]]: |
|||
<pre>: (2print *DL) # Print the list |
|||
A C B |
|||
: (2printReversed *DL) # Print it in reversed order |
|||
B C A</pre> |
|||
=={{header|PL/I}}== |
|||
<syntaxhighlight 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 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;</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
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</pre> |
|||
=={{header|PureBasic}}== |
|||
<syntaxhighlight 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())</syntaxhighlight> |
|||
=={{header|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. |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
This produces the desired output. However, I expect most python programmers would do the following instead: |
|||
<syntaxhighlight 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)</syntaxhighlight> |
|||
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. |
|||
=={{header|Racket}}== |
|||
See [[Doubly-Linked List]] for the structure definitions. |
|||
These functions traverse the list in the two directions. |
|||
They create a native (singly-linked) list by adding to the front, so they traverse in the reverse order from the desired result order. |
|||
<syntaxhighlight lang="racket">(define (dlist-elements dlist) |
|||
(let loop ([elements '()] [dlink (dlist-tail dlist)]) |
|||
(if dlink |
|||
(loop (cons (dlink-content dlink) elements) (dlink-prev dlink)) |
|||
elements))) |
|||
(define (dlist-elements/reverse dlist) |
|||
(let loop ([elements '()] [dlink (dlist-head dlist)]) |
|||
(if dlink |
|||
(loop (cons (dlink-content dlink) elements) (dlink-next dlink)) |
|||
elements)))</syntaxhighlight> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
Since the list routines are supplied by the generic roles defined in [[Doubly-linked_list/Definition#Raku]], it suffices to say: |
|||
<syntaxhighlight lang="raku" line>say $dll.list; |
|||
say $dll.reverse;</syntaxhighlight> |
|||
These automatically return just the payloads, hiding the elements containing the forward and backward pointers. |
|||
=={{header|REXX}}== |
|||
REXX doesn't have linked lists, as there are no pointers (or handles). |
|||
However, linked lists can be simulated with lists in REXX. |
|||
<syntaxhighlight 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 /*stick a fork in it, we're done.*/ |
|||
/*──────────────────────────────────subroutines─────────────────────────*/ |
|||
p: return word(arg(1),1) |
|||
sy: say; say left('',30) "───" arg(1) '───'; return |
|||
@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 /*j*/ |
|||
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</syntaxhighlight> |
|||
'''output''' |
|||
<pre style="height:30ex;overflow:scroll"> |
|||
─── 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 |
|||
</pre> |
|||
=={{header|Ring}}== |
|||
<syntaxhighlight lang="ring"> |
|||
# Project : Doubly-linked list/Traversal |
|||
trav = [123, 789, 456] |
|||
travfor = sort(trav) |
|||
see "Traverse forwards:" + nl |
|||
see travfor |
|||
see nl |
|||
travback = reverse(travfor) |
|||
see "Traverse backwards:" + nl |
|||
see travback |
|||
see nl |
|||
</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
Traverse forwards: |
|||
123 |
|||
456 |
|||
789 |
|||
Traverse backwards: |
|||
789 |
|||
456 |
|||
123 |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">class DListNode |
||
def get_tail |
def get_tail |
||
# parent class (ListNode) includes Enumerable, so the find method is available to us |
# parent class (ListNode) includes Enumerable, so the find method is available to us |
||
Line 196: | Line 2,387: | ||
head = DListNode.from_array([:a, :b, :c]) |
head = DListNode.from_array([:a, :b, :c]) |
||
head.each {|node| p node.value} |
head.each {|node| p node.value} |
||
head.get_tail.each_previous {|node| p node.value}</ |
head.get_tail.each_previous {|node| p node.value}</syntaxhighlight> |
||
=={{header|Salmon}}== |
|||
Without explicit type information: |
|||
<syntaxhighlight lang="salmon">class item(init_data) |
|||
{ |
|||
variable next, |
|||
previous, |
|||
data := init_data; |
|||
}; |
|||
function prepend(tail, new_data) |
|||
{ |
|||
immutable result := item(new_data); |
|||
result.next := tail; |
|||
result.previous := null; |
|||
if (tail != null) |
|||
tail.previous := result;; |
|||
return result; |
|||
}; |
|||
variable my_list := null; |
|||
my_list := prepend(my_list, "R"); |
|||
my_list := prepend(my_list, "o"); |
|||
my_list := prepend(my_list, "s"); |
|||
my_list := prepend(my_list, "e"); |
|||
my_list := prepend(my_list, "t"); |
|||
my_list := prepend(my_list, "t"); |
|||
my_list := prepend(my_list, "a"); |
|||
"Items in the list going forward:"! |
|||
variable follow := my_list; |
|||
while (true) |
|||
{ |
|||
follow.data! |
|||
if (follow.next == null) |
|||
break;; |
|||
} |
|||
step |
|||
follow := follow.next;; |
|||
"Items in the list going backward:"! |
|||
while (follow != null) |
|||
follow.data! |
|||
step |
|||
follow := follow.previous;;</syntaxhighlight> |
|||
With explicit type information: |
|||
<syntaxhighlight lang="salmon">class item(init_data : string) |
|||
{ |
|||
variable next: item | {null}, |
|||
previous : item | {null}, |
|||
data : string := init_data; |
|||
}; |
|||
function prepend(tail : item | {null}, new_data : string) returns item |
|||
{ |
|||
immutable result := item(new_data); |
|||
result.next := tail; |
|||
result.previous := null; |
|||
if (tail != null) |
|||
tail.previous := result;; |
|||
return result; |
|||
}; |
|||
variable my_list : item | {null} := null; |
|||
my_list := prepend(my_list, "R"); |
|||
my_list := prepend(my_list, "o"); |
|||
my_list := prepend(my_list, "s"); |
|||
my_list := prepend(my_list, "e"); |
|||
my_list := prepend(my_list, "t"); |
|||
my_list := prepend(my_list, "t"); |
|||
my_list := prepend(my_list, "a"); |
|||
"Items in the list going forward:"! |
|||
variable follow : item | {null} := my_list; |
|||
while (true) |
|||
{ |
|||
follow.data! |
|||
if (follow.next == null) |
|||
break;; |
|||
} |
|||
step |
|||
follow := follow.next;; |
|||
"Items in the list going backward:"! |
|||
while (follow != null) |
|||
follow.data! |
|||
step |
|||
follow := follow.previous;;</syntaxhighlight> |
|||
Both of these produce the following output: |
|||
<pre> |
|||
Items in the list going forward: |
|||
a |
|||
t |
|||
t |
|||
e |
|||
s |
|||
o |
|||
R |
|||
Items in the list going backward: |
|||
R |
|||
o |
|||
s |
|||
e |
|||
t |
|||
t |
|||
a |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
<syntaxhighlight lang="scala">import java.util |
|||
object DoublyLinkedListTraversal extends App { |
|||
private val ll = new util.LinkedList[String] |
|||
private def traverse(iter: util.Iterator[String]) = |
|||
while (iter.hasNext) iter.next |
|||
traverse(ll.iterator) |
|||
traverse(ll.descendingIterator) |
|||
}</syntaxhighlight> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Assuming that the <code>List</code> class from [[Doubly-Linked List (element)#Tcl|this other task]] is already present... |
Assuming that the <code>List</code> class from [[Doubly-Linked List (element)#Tcl|this other task]] is already present... |
||
< |
<syntaxhighlight lang="tcl"># Modify the List class to add the iterator methods |
||
oo::define List { |
oo::define List { |
||
method foreach {varName script} { |
method foreach {varName script} { |
||
Line 223: | Line 2,537: | ||
$first foreach char { puts $char } |
$first foreach char { puts $char } |
||
puts "Backward..." |
puts "Backward..." |
||
$last revforeach char { puts $char }</ |
$last revforeach char { puts $char }</syntaxhighlight> |
||
Which produces this output: |
Which produces this output: |
||
<pre>Forward... |
<pre>Forward... |
||
Line 236: | Line 2,550: | ||
a</pre> |
a</pre> |
||
=={{header| |
=={{header|Wren}}== |
||
{{libheader|Wren-llist}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./llist" for DLinkedList |
|||
import "./fmt" for Fmt |
|||
// create a new doubly-linked list and add the first 50 positive integers to it |
|||
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. |
|||
var dll = DLinkedList.new(1..50) |
|||
<lang python>class List: |
|||
def __init__(self, data, next=None, prev=None): |
|||
self.data = data |
|||
self.next = next |
|||
self.prev = prev |
|||
// traverse the doubly-linked list from head to tail |
|||
def append(self, data): |
|||
for (i in dll) { |
|||
if self.next == None: |
|||
Fmt.write("$4d ", i) |
|||
if (i % 10 == 0) System.print() |
|||
} |
|||
else: |
|||
System.print() |
|||
return self.next.append(data) |
|||
// traverse the doubly-linked list from tail to head |
|||
for (i in dll.reversed) { |
|||
Fmt.write("$4d ", i) |
|||
if (i % 10 == 1) System.print() |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
# Build the list |
|||
<pre> |
|||
tail = head = List(10) |
|||
1 2 3 4 5 6 7 8 9 10 |
|||
for i in [ 20, 30, 40 ]: |
|||
11 12 13 14 15 16 17 18 19 20 |
|||
tail = tail.append(i) |
|||
21 22 23 24 25 26 27 28 29 30 |
|||
31 32 33 34 35 36 37 38 39 40 |
|||
41 42 43 44 45 46 47 48 49 50 |
|||
50 49 48 47 46 45 44 43 42 41 |
|||
# Traverse forwards |
|||
40 39 38 37 36 35 34 33 32 31 |
|||
node = head |
|||
30 29 28 27 26 25 24 23 22 21 |
|||
while node != None: |
|||
20 19 18 17 16 15 14 13 12 11 |
|||
print(node.data) |
|||
10 9 8 7 6 5 4 3 2 1 |
|||
node = node.next |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
# Traverse Backwards |
|||
<syntaxhighlight lang "XPL0">def \Node\ Prev, Data, Next; \Element (Node) definition |
|||
node = tail |
|||
def SizeofInt = 4; |
|||
while node != None: |
|||
print(node.data) |
|||
node = node.prev</lang> |
|||
proc Insert(NewNode, Node); \Insert NewNode after Node |
|||
This produces the desired output. However, I expect most python programmers would do the following instead: |
|||
int NewNode, Node, NextNode; |
|||
[NextNode:= Node(Next); |
|||
NextNode(Prev):= NewNode; |
|||
NewNode(Next):= NextNode; |
|||
NewNode(Prev):= Node; |
|||
Node(Next):= NewNode; |
|||
]; |
|||
int Head(3), Tail(3); \Doubly linked list definition |
|||
<lang python>l = [ 10, 20, 30, 40 ] |
|||
int N, NewNode, Node; |
|||
for i in l: |
|||
[\Further define (initialize) the doubly linked list |
|||
print(i) |
|||
Head(Next):= Tail; |
|||
for i in reversed(l): # reversed produces an iterator, so only O(1) memory is used |
|||
Tail(Prev):= Head; |
|||
print(i)</lang> |
|||
\Insert some Nodes containing square data |
|||
for N:= 1 to 10 do |
|||
[NewNode:= Reserve(3*SizeofInt); |
|||
NewNode(Data):= N*N; |
|||
Insert(NewNode, Head); |
|||
]; |
|||
\Traverse list from Head to Tail |
|||
Node:= Head(Next); |
|||
while Node # Tail do |
|||
[IntOut(0, Node(Data)); ChOut(0, ^ ); |
|||
Node:= Node(Next); |
|||
]; |
|||
CrLf(0); |
|||
\Traverse list from Tail to Head |
|||
Node:= Tail(Prev); |
|||
while Node # Head do |
|||
[IntOut(0, Node(Data)); ChOut(0, ^ ); |
|||
Node:= Node(Prev); |
|||
]; |
|||
CrLf(0); |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
100 81 64 49 36 25 16 9 4 1 |
|||
1 4 9 16 25 36 49 64 81 100 |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
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. |
|||
<syntaxhighlight lang="zkl">class Node{ |
|||
fcn init(_value,_prev=Void,_next=Void) |
|||
{ var value=_value, prev=_prev, next=_next; } |
|||
fcn toString{ value.toString() } |
|||
fcn append(value){ |
|||
b,c := Node(value,self,next),next; |
|||
next=b; |
|||
if(c) c.prev=b; |
|||
b |
|||
} |
|||
}</syntaxhighlight> |
|||
<syntaxhighlight lang="zkl">a,c := Node("a"), a.append("b").append("c"); |
|||
n:=a; while(n){ print(n," "); n=n.next } |
|||
println(); |
|||
n:=c; while(n){ print(n," "); n=n.prev } |
|||
println();</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
a b c |
|||
c b a |
|||
</pre> |
|||
{{omit from|ACL2}} |
|||
{{omit from|GUISS}} |
Latest revision as of 12:06, 28 November 2023
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.
- 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
Action!
The user must type in the monitor the following command after compilation and before running the program!
SET EndProg=*
CARD EndProg ;required for ALLOCATE.ACT
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
DEFINE PTR="CARD"
DEFINE NODE_SIZE="6"
TYPE ListNode=[INT data PTR prv,nxt]
ListNode POINTER listBegin,listEnd
PROC Append(INT v)
ListNode POINTER n
n=Alloc(NODE_SIZE)
n.data=v
n.prv=listEnd
n.nxt=0
IF listEnd THEN
listEnd.nxt=n
ELSE
listBegin=n
FI
listEnd=n
RETURN
PROC Clear()
ListNode POINTER n,next
n=listBegin
WHILE n
DO
next=n.nxt
Free(n,NODE_SIZE)
n=next
OD
listBegin=0
listEnd=0
RETURN
PROC ForwardTraverse()
ListNode POINTER n
n=listBegin
PrintE("Forward traverse:")
Print("(")
WHILE n
DO
PrintI(n.data)
IF n.nxt THEN
Print(", ")
FI
n=n.nxt
OD
PrintE(")")
RETURN
PROC BackwardTraverse()
ListNode POINTER n
n=listEnd
PrintE("Backward traverse")
Print("(")
WHILE n
DO
PrintI(n.data)
IF n.prv THEN
Print(", ")
FI
n=n.prv
OD
PrintE(")")
RETURN
PROC Main()
INT i
Put(125) PutE() ;clear screen
AllocInit(0)
listBegin=0
listEnd=0
FOR i=0 TO 50
DO
Append(i*i)
OD
ForwardTraverse()
PutE()
BackwardTraverse()
Clear()
RETURN
- Output:
Screenshot from Atari 8-bit computer
Forward traverse: (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500) Backward traverse (2500, 2401, 2304, 2209, 2116, 2025, 1936, 1849, 1764, 1681, 1600, 1521, 1444, 1369, 1296, 1225, 1156, 1089, 1024, 961, 900, 841, 784, 729, 676, 625, 576, 529, 484, 441, 400, 361, 324, 289, 256, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1, 0)
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;
ALGOL 68
LinkedList.alg:
# Node struct - contains next and prev NODE pointers and DATA #
MODE NODE = STRUCT(
DATA data,
REF NODE prev,
REF NODE next
);
# List structure - contains head and tail NODE pointers #
MODE LIST = STRUCT(
REF NODE head,
REF NODE tail
);
# --- PREPEND - Adds a node to the beginning of the list ---#
PRIO PREPEND = 1;
OP PREPEND = (REF LIST list, DATA data) VOID:
(
HEAP NODE n := (data, NIL, NIL);
IF head OF list IS REF NODE(NIL) THEN
head OF list := tail OF list := n
ELSE
next OF n := head OF list;
prev OF head OF list := head OF list := n
FI
);
#--- APPEND - Adds a node to the end of the list ---#
PRIO APPEND = 1;
OP APPEND = (REF LIST list, DATA data) VOID:
(
HEAP NODE n := (data, NIL, NIL);
IF head OF list IS REF NODE(NIL) THEN
head OF list := tail OF list := n
ELSE
prev OF n := tail OF list;
next OF tail OF list := tail OF list := n
FI
);
#--- REMOVE_FIRST - removes & returns node at end of the list ---#
PRIO REMOVE_FIRST = 1;
OP REMOVE_FIRST = (REF LIST list) DATA:
(
IF head OF list ISNT REF NODE(NIL) THEN
DATA d := data OF head OF list;
prev OF next OF head OF list := NIL;
head OF list := next OF head OF list;
d # return d #
FI
);
#--- REMOVE_LAST: removes & returns node at front of list --- #
PRIO REMOVE_LAST = 1;
OP REMOVE_LAST = (REF LIST list) DATA:
(
IF head OF list ISNT REF NODE(NIL) THEN
DATA d := data OF tail OF list;
next OF prev OF tail OF list := NIL;
tail OF list := prev OF tail OF list;
d # return d #
FI
);
#--- PURGE - removes all elements from the list ---#
PRIO PURGE = 2;
OP PURGE = (REF LIST list) VOID:
(
head OF list := tail OF list := NIL
);
#--- returns the data at the end of the list ---#
PRIO LAST_IN = 2;
OP LAST_IN = (REF LIST list) DATA: (
IF head OF list ISNT REF NODE(NIL) THEN
data OF tail OF list
FI
);
#--- returns the data at the front of the list ---#
PRIO FIRST_IN = 2;
OP FIRST_IN = (REF LIST list) DATA: (
IF head OF list ISNT REF NODE(NIL) THEN
data OF head OF list
FI
);
#--- Traverses through the list forwards ---#
PROC forward traversal = (LIST list) VOID:
(
REF NODE travel := head OF list;
WHILE travel ISNT REF NODE(NIL) DO
list visit(data OF travel);
travel := next OF travel
OD
);
#--- Traverses through the list backwards ---#
PROC backward traversal = (LIST list) VOID:
(
REF NODE travel := tail OF list;
WHILE travel ISNT REF NODE(NIL) DO
list visit(data OF travel);
travel := prev OF travel
OD
)
main.alg:
PR READ "LinkedList.alg" PR;
MODE EMPLOYEE = STRUCT(STRING name, INT salary, INT years);
MODE DATA = EMPLOYEE; #Sets the data type that is in the list#
# Function that traversals call for each node in list #
PROC list visit = (REF DATA data) VOID:
(
print((
"EMPLOYEE NAME : ", name OF data , newline,
" SALARY: " , salary OF data, newline,
" YEARS : " , years OF data, newline
))
);
#***************************************************************#
main:
(
EMPLOYEE empl;
name OF empl := "one";
salary OF empl := 100;
years OF empl := 10;
LIST list := (NIL, NIL);
list PREPEND empl;
name OF empl := "two";
salary OF empl := 200;
years OF empl := 20;
list APPEND empl;
name OF empl := "three";
salary OF empl := 300;
years OF empl := 30;
list APPEND empl;
salary OF empl := 400;
years OF empl := 40;
name OF empl := "four";
list APPEND empl;
forward traversal(list);
PURGE list;
forward traversal(list)
)
- Output:
EMPLOYEE NAME : one SALARY: +100 YEARS : +10 EMPLOYEE NAME : two SALARY: +200 YEARS : +20 EMPLOYEE NAME : three SALARY: +300 YEARS : +30 EMPLOYEE NAME : four SALARY: +400 YEARS : +40
ALGOL W
Using the element type and insertion routine from the Doubly Linked List/Eleemnt Insertion task.
begin
% record type to hold an element of a doubly linked list of integers %
record DListIElement ( reference(DListIElement) prev
; integer iValue
; reference(DListIElement) next
);
% additional record types would be required for other element types %
% inserts a new element into the list, before e %
reference(DListIElement) procedure insertIntoDListIBefore( reference(DListIElement) value e
; integer value v
);
begin
reference(DListIElement) newElement;
newElement := DListIElement( null, v, e );
if e not = null then begin
% the element we are inserting before is not null %
reference(DListIElement) ePrev;
ePrev := prev(e);
prev(newElement) := ePrev;
prev(e) := newElement;
if ePrev not = null then next(ePrev) := newElement
end if_e_ne_null ;
newElement
end insertIntoDListiAfter ;
begin
reference(DListIElement) head, e, last;
head := null;
head := insertIntoDListIBefore( head, 1701 );
head := insertIntoDListIBefore( head, 9000 );
e := insertIntoDListIBefore( next(head), 90210 );
e := insertIntoDListIBefore( next(e), 4077 );
e := head;
last := null;
write( "Forward:" );
while e not = null do begin
write( i_w := 1, s_w := 0, " ", iValue(e) );
last := e;
e := next(e)
end while_e_ne_null ;
write( "Backward:" );
e := last;
while e not = null do begin
write( i_w := 1, s_w := 0, " ", iValue(e) );
last := e;
e := prev(e)
end while_e_ne_null
end
end.
- Output:
Forward: 9000 90210 4077 1701 Backward: 1701 4077 90210 9000
Applesoft BASIC
100 REM BUILD THE LIST
110 FOR I = 20 TO 40 STEP 10
120 LET S$ = STR$ (I): GOSUB 260"APPEND"
130 NEXT I
140 REM TRAVERSE FORWARDS
150 LET N = HEAD
160 FOR Q = 1 TO 1
170 IF N < > NIL THEN PRINT S$(N)" ";:N = N(N):Q = 0
180 NEXT Q
190 PRINT
200 REM TRAVERSE BACKWARDS
210 LET N = TAIL
220 FOR Q = 1 TO 1
230 IF N < > NIL THEN PRINT S$(N)" ";:N = P(N):Q = 0
240 NEXT Q
250 END
260 REM APPEND S$
270 LET NIL = - 1
280 LET P(L) = NIL
290 LET N(L) = NIL
300 REM TRAVERSE UNTIL LAST NODE FOUND
310 FOR Q = 1 TO 1
320 IF N(N) < > NIL THEN N = N(N):Q = 0
330 NEXT Q
340 REM NEW NODE
350 LET S$(L) = S$
360 LET N(L) = NIL
370 IF N < > L THEN P(L) = N
380 REM POINT THE LAST NODE AT THE NEW NODE
390 IF N < > L THEN N(N) = L
400 LET TAIL = L
410 LET N = TAIL
420 LET L = L + 1
430 RETURN
ARM Assembly
/* ARM assembly Raspberry PI */
/* program transDblList.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly
for the routine affichageMess conversion10S
see at end of this program the instruction include */
/* Constantes */
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ READ, 3
.equ WRITE, 4
/*******************************************/
/* Structures */
/********************************************/
/* structure Doublylinkedlist*/
.struct 0
dllist_head: @ head node
.struct dllist_head + 4
dllist_tail: @ tail node
.struct dllist_tail + 4
dllist_fin:
/* structure Node Doublylinked List*/
.struct 0
NDlist_next: @ next element
.struct NDlist_next + 4
NDlist_prev: @ previous element
.struct NDlist_prev + 4
NDlist_value: @ element value or key
.struct NDlist_value + 4
NDlist_fin:
/* Initialized data */
.data
szMessInitListe: .asciz "List initialized.\n"
szMessListInv: .asciz "Display list inverse :\n"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "Error detected.\n"
/* datas message display */
szMessResult: .ascii "Result value :"
sValue: .space 12,' '
.asciz "\n"
/* UnInitialized data */
.bss
dllist1: .skip dllist_fin @ list memory place
/* code section */
.text
.global main
main:
ldr r0,iAdrdllist1
bl newDList @ create new list
ldr r0,iAdrszMessInitListe
bl affichageMess
ldr r0,iAdrdllist1 @ list address
mov r1,#10 @ value
bl insertHead @ insertion at head
cmp r0,#-1
beq 99f
ldr r0,iAdrdllist1
mov r1,#20
bl insertTail @ insertion at tail
cmp r0,#-1
beq 99f
ldr r0,iAdrdllist1 @ list address
mov r1,#10 @ value to after insered
mov r2,#15 @ new value
bl insertAfter
cmp r0,#-1
beq 99f
ldr r0,iAdrdllist1 @ list address
mov r1,#20 @ value to after insered
mov r2,#25 @ new value
bl insertAfter
cmp r0,#-1
beq 99f
ldr r0,iAdrdllist1
bl transHeadTail @ display value head to tail
ldr r0,iAdrszMessListInv
bl affichageMess
ldr r0,iAdrdllist1
bl transTailHead @ display value tail to head
b 100f
99:
ldr r0,iAdrszMessErreur
bl affichageMess
100: @ standard end of the program
mov r7, #EXIT @ request to exit program
svc 0 @ perform system call
iAdrszMessInitListe: .int szMessInitListe
iAdrszMessErreur: .int szMessErreur
iAdrszMessListInv: .int szMessListInv
iAdrszCarriageReturn: .int szCarriageReturn
iAdrdllist1: .int dllist1
/******************************************************************/
/* create new list */
/******************************************************************/
/* r0 contains the address of the list structure */
newDList:
push {r1,lr} @ save registers
mov r1,#0
str r1,[r0,#dllist_tail]
str r1,[r0,#dllist_head]
pop {r1,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* list is empty ? */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r0 return 0 if empty else return 1 */
isEmpty:
//push {r1,lr} @ save registers
ldr r0,[r0,#dllist_head]
cmp r0,#0
movne r0,#1
//pop {r1,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* insert value at list head */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value */
insertHead:
push {r1-r4,lr} @ save registers
mov r4,r0 @ save address
mov r0,r1 @ value
bl createNode
cmp r0,#-1 @ allocation error ?
beq 100f
ldr r2,[r4,#dllist_head] @ load address first node
str r2,[r0,#NDlist_next] @ store in next pointer on new node
mov r1,#0
str r1,[r0,#NDlist_prev] @ store zero in previous pointer on new node
str r0,[r4,#dllist_head] @ store address new node in address head list
cmp r2,#0 @ address first node is null ?
strne r0,[r2,#NDlist_prev] @ no store adresse new node in previous pointer
streq r0,[r4,#dllist_tail] @ else store new node in tail address
100:
pop {r1-r4,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* insert value at list tail */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value */
insertTail:
push {r1-r4,lr} @ save registers
mov r4,r0 @ save list address
mov r0,r1 @ value
bl createNode @ new node
cmp r0,#-1
beq 100f @ allocation error
ldr r2,[r4,#dllist_tail] @ load address last node
str r2,[r0,#NDlist_prev] @ store in previous pointer on new node
mov r1,#0 @ store null un next pointer
str r1,[r0,#NDlist_next]
str r0,[r4,#dllist_tail] @ store address new node on list tail
cmp r2,#0 @ address last node is null ?
strne r0,[r2,#NDlist_next] @ no store address new node in next pointer
streq r0,[r4,#dllist_head] @ else store in head list
100:
pop {r1-r4,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* insert value after other element */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains value to search*/
/* r2 contains value to insert */
insertAfter:
push {r1-r5,lr} @ save registers
mov r4,r0
bl searchValue @ search node with this value in r1
cmp r0,#-1
beq 100f @ not found -> error
mov r5,r0 @ save address of node find
mov r0,r2 @ new value
bl createNode @ create new node
cmp r0,#-1
beq 100f @ allocation error
ldr r2,[r5,#NDlist_next] @ load pointer next of find node
str r0,[r5,#NDlist_next] @ store new node in pointer next
str r5,[r0,#NDlist_prev] @ store address find node in previous pointer on new node
str r2,[r0,#NDlist_next] @ store pointer next of find node on pointer next on new node
cmp r2,#0 @ next pointer is null ?
strne r0,[r2,#NDlist_prev] @ no store address new node in previous pointer
streq r0,[r4,#dllist_tail] @ else store in list tail
100:
pop {r1-r5,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* search value */
/******************************************************************/
/* r0 contains the address of the list structure */
/* r1 contains the value to search */
/* r0 return address of node or -1 if not found */
searchValue:
push {r2,lr} @ save registers
ldr r0,[r0,#dllist_head] @ load first node
1:
cmp r0,#0 @ null -> end search not found
moveq r0,#-1
beq 100f
ldr r2,[r0,#NDlist_value] @ load node value
cmp r2,r1 @ equal ?
beq 100f
ldr r0,[r0,#NDlist_next] @ load addresse next node
b 1b @ and loop
100:
pop {r2,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* transversal for head to tail */
/******************************************************************/
/* r0 contains the address of the list structure */
transHeadTail:
push {r2,lr} @ save registers
ldr r2,[r0,#dllist_head] @ load first node
1:
ldr r0,[r2,#NDlist_value]
ldr r1,iAdrsValue
bl conversion10S
ldr r0,iAdrszMessResult
bl affichageMess
ldr r2,[r2,#NDlist_next]
cmp r2,#0
bne 1b
100:
pop {r2,lr} @ restaur registers
bx lr @ return
iAdrszMessResult: .int szMessResult
iAdrsValue: .int sValue
/******************************************************************/
/* transversal for tail to head */
/******************************************************************/
/* r0 contains the address of the list structure */
transTailHead:
push {r2,lr} @ save registers
ldr r2,[r0,#dllist_tail] @ load last node
1:
ldr r0,[r2,#NDlist_value]
ldr r1,iAdrsValue
bl conversion10S
ldr r0,iAdrszMessResult
bl affichageMess
ldr r2,[r2,#NDlist_prev]
cmp r2,#0
bne 1b
100:
pop {r2,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* Create new node */
/******************************************************************/
/* r0 contains the value */
/* r0 return node address or -1 if allocation error*/
createNode:
push {r1-r7,lr} @ save registers
mov r4,r0 @ save value
@ allocation place on the heap
mov r0,#0 @ allocation place heap
mov r7,#0x2D @ call system 'brk'
svc #0
mov r5,r0 @ save address heap for output string
add r0,#NDlist_fin @ reservation place one element
mov r7,#0x2D @ call system 'brk'
svc #0
cmp r0,#-1 @ allocation error
beq 100f
mov r0,r5
str r4,[r0,#NDlist_value] @ store value
mov r2,#0
str r2,[r0,#NDlist_next] @ store zero to pointer next
str r2,[r0,#NDlist_prev] @ store zero to pointer previous
100:
pop {r1-r7,lr} @ restaur registers
bx lr @ return
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
.include "../affichage.inc"
AutoHotkey
see Doubly-linked list/AutoHotkey
Axe
LINK(L₁,1)→A
LINK(L₁+10,2)→B
LINK(L₁+50,3)→C
INSERT(A,B)
INSERT(A,C)
A→I
While I≠0
Disp VALUE(I)▶Dec,i
NEXT(I)→I
End
Disp "-----",i
B→I
While I≠0
Disp VALUE(I)▶Dec,i
PREV(I)→I
End
BBC BASIC
DIM node{pPrev%, pNext%, iData%}
DIM a{} = node{}, b{} = node{}, c{} = node{}
a.pNext% = b{}
a.iData% = 123
b.pPrev% = a{}
b.iData% = 789
c.iData% = 456
PROCinsert(a{}, c{})
PRINT "Traverse forwards:"
pnode% = a{}
REPEAT
!(^node{}+4) = pnode%
PRINT node.iData%
pnode% = node.pNext%
UNTIL pnode% = 0
PRINT "Traverse backwards:"
pnode% = b{}
REPEAT
!(^node{}+4) = pnode%
PRINT node.iData%
pnode% = node.pPrev%
UNTIL pnode% = 0
END
DEF PROCinsert(here{}, new{})
LOCAL temp{} : DIM temp{} = node{}
new.pNext% = here.pNext%
new.pPrev% = here{}
!(^temp{}+4) = new.pNext%
temp.pPrev% = new{}
here.pNext% = new{}
ENDPROC
Output:
Traverse forwards: 123 456 789 Traverse backwards: 789 456 123
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;
}
C#
using System;
using System.Collections.Generic;
namespace RosettaCode.DoublyLinkedList
{
internal static class Program
{
private static void Main()
{
var list = new LinkedList<char>("hello");
var current = list.First;
do
{
Console.WriteLine(current.Value);
} while ((current = current.Next) != null);
Console.WriteLine();
current = list.Last;
do
{
Console.WriteLine(current.Value);
} while ((current = current.Previous) != null);
}
}
}
Output:
h e l l o o l l e h
C++
#include <iostream>
#include <list>
int main ()
{
std::list<int> numbers {1, 5, 7, 0, 3, 2};
for(const auto& i: numbers)
std::cout << i << ' ';
std::cout << '\n';
}
- Output:
1 5 7 0 3 2
Clojure
Given the definition in Doubly-linked list/Definition#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...>})
D
Standard Doubly-linked List
void main() {
import std.stdio, std.container, std.range;
auto dll = DList!dchar("DCBA"d.dup);
dll[].writeln;
dll[].retro.writeln;
}
- Output:
ABCD DCBA
User-defined Doubly-linked list
Same output.
struct Node(T) {
T data;
typeof(this)* prev, next;
}
void prepend(T)(ref Node!T* head, in T item) pure nothrow {
auto newNode = new Node!T(item, null, head);
if (head)
head.prev = newNode;
head = newNode;
}
void main() {
import std.stdio;
Node!char* head;
foreach (char c; "DCBA")
head.prepend(c);
auto last = head;
for (auto p = head; p; p = p.next) {
p.data.write;
last = p;
}
writeln;
for (auto p = last; p; p = p.prev)
p.data.write;
writeln;
}
Delphi
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;
E
Given the definition in Doubly-linked list/Definition#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
}
}
}
? def list := makeDLList()
# value: <>
? list.push(1)
? list.push(2)
? list.push(3)
? traverse(list)
1
2
3
3
2
1
Erlang
The task in Doubly-linked_list/Element_insertion uses traversal as proof that the insertion worked.
F#
open System.Collections.Generic
let first (l: LinkedList<char>) = l.First
let last (l: LinkedList<char>) = l.Last
let next (l: LinkedListNode<char>) = l.Next
let prev (l: LinkedListNode<char>) = l.Previous
let traverse g f (ls: LinkedList<char>) =
let rec traverse (l: LinkedListNode<char>) =
match l with
| null -> ()
| _ ->
printf "%A" l.Value
traverse (f l)
traverse (g ls)
let traverseForward = traverse first next
let traverseBackward = traverse last prev
let cs = LinkedList(['a'..'z'])
traverseForward cs
printfn ""
traverseBackward cs
- Output:
'a''b''c''d''e''f''g''h''i''j''k''l''m''n''o''p''q''r''s''t''u''v''w''x''y''z' 'z''y''x''w''v''u''t''s''r''q''p''o''n''m''l''k''j''i''h''g''f''e''d''c''b''a'
Fortran
see Doubly-linked list/Definition#Fortran
FreeBASIC
Dim As Integer i, MiLista()
For i = 0 To Int(Rnd * 100)+25
Redim Preserve MiLista(i)
MiLista(i) = Rnd * 314
Next
'Tour from the beginning
For i = Lbound(MiLista) To Ubound(MiLista)
Print MiLista(i)
Next i
Print
'Travel from the end
For i = Ubound(MiLista) To Lbound(MiLista) Step -1
Print MiLista(i)
Next i
Sleep
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.
Also note that there is a doubly linked list in the Go standard library in package container/list.
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("")
}
Output:
<nil> [A B] [A C B] From tail: B C A
Groovy
class DoubleLinkedListTraversing {
static void main(args) {
def linkedList = (1..9).collect() as LinkedList
linkedList.each {
print it
}
println()
linkedList.reverseEach {
print it
}
}
}
- Output:
123456789 987654321
Haskell
main = print . traverse True $ create [10,20,30,40]
data DList a = Leaf | Node { prev::(DList a), elt::a, next::(DList a) }
create = go Leaf
where go _ [] = Leaf
go prev (x:xs) = current
where current = Node prev x next
next = go current xs
isLeaf Leaf = True
isLeaf _ = False
lastNode Leaf = Leaf
lastNode dl = until (isLeaf.next) next dl
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)
Icon and Unicon
Uses Unicon classes.
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
Output:
Traverse from beginning to end 1 3 2 Traverse from end to beginning 2 3 1
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
)
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
package com.rosettacode;
import java.util.LinkedList;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class DoubleLinkedListTraversing {
public static void main(String[] args) {
final LinkedList<String> doubleLinkedList =
IntStream.range(1, 10)
.mapToObj(String::valueOf)
.collect(Collectors.toCollection(LinkedList::new));
doubleLinkedList.iterator().forEachRemaining(System.out::print);
System.out.println();
doubleLinkedList.descendingIterator().forEachRemaining(System.out::print);
}
}
- Output:
123456789 987654321
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.
Julia
mutable struct DLNode{T}
value::T
pred::Union{DLNode{T}, Nothing}
succ::Union{DLNode{T}, Nothing}
DLNode(v) = new{typeof(v)}(v, nothing, nothing)
end
function insertpost(prevnode, node)
succ = prevnode.succ
prevnode.succ = node
node.pred = prevnode
node.succ = succ
if succ != nothing
succ.pred = node
end
node
end
first(nd) = (while nd.pred != nothing nd = nd.prev end; nd)
last(nd) = (while nd.succ != nothing nd = nd.succ end; nd)
function printconnected(nd; fromtail = false)
if fromtail
nd = last(nd)
print(nd.value)
while nd.pred != nothing
nd = nd.pred
print(" -> $(nd.value)")
end
else
nd = first(nd)
print(nd.value)
while nd.succ != nothing
nd = nd.succ
print(" -> $(nd.value)")
end
end
println()
end
node1 = DLNode(1)
node2 = DLNode(2)
node3 = DLNode(3)
insertpost(node1, node2)
insertpost(node2, node3)
print("From beginning to end: "); printconnected(node1)
print("From end to beginning: "); printconnected(node1, fromtail = true)
- Output:
From beginning to end: 1 -> 2 -> 3 From end to beginning: 3 -> 2 -> 1
Kotlin
To complete this task, we just need to add a couple of traversal functions to the class we defined in the Doubly-linked list/Definition task:
// version 1.1.2
class LinkedList<E> {
class Node<E>(var data: E, var prev: Node<E>? = null, var next: Node<E>? = null) {
override fun toString(): String {
val sb = StringBuilder(this.data.toString())
var node = this.next
while (node != null) {
sb.append(" -> ", node.data.toString())
node = node.next
}
return sb.toString()
}
}
var first: Node<E>? = null
var last: Node<E>? = null
fun addFirst(value: E) {
if (first == null) {
first = Node(value)
last = first
}
else {
val node = first!!
first = Node(value, null, node)
node.prev = first
}
}
fun addLast(value: E) {
if (last == null) {
last = Node(value)
first = last
}
else {
val node = last!!
last = Node(value, node, null)
node.next = last
}
}
fun insert(after: Node<E>?, value: E) {
if (after == null)
addFirst(value)
else if (after == last)
addLast(value)
else {
val next = after.next
val new = Node(value, after, next)
after.next = new
if (next != null) next.prev = new
}
}
override fun toString() = first.toString()
fun firstToLast() = first?.toString() ?: ""
fun lastToFirst(): String {
if (last == null) return ""
val sb = StringBuilder(last.toString())
var node = last!!.prev
while (node != null) {
sb.append(" -> ", node.data.toString())
node = node.prev
}
return sb.toString()
}
}
fun main(args: Array<String>) {
val ll = LinkedList<Int>()
ll.addFirst(1)
ll.addLast(4)
ll.insert(ll.first, 2)
ll.insert(ll.last!!.prev, 3)
println("First to last : ${ll.firstToLast()}")
println("Last to first : ${ll.lastToFirst()}")
}
- Output:
First to last : 1 -> 2 -> 3 -> 4 Last to first : 4 -> 3 -> 2 -> 1
Lua
Begin with this: Doubly-linked_list/Definition#Lua, then extend with this:
--------------
-- TRAVERSAL:
--------------
List.iterateForward = function(self)
local function iter(self, node)
if node then return node.next else return self.head end
end
return iter, self, nil
end
List.iterateReverse = function(self)
local function iter(self, node)
if node then return node.prev else return self.tail end
end
return iter, self, nil
end
---------
-- TEST:
---------
local list = List()
for i = 1, 5 do list:insertTail(i) end
io.write("Forward: ") for node in list:iterateForward() do io.write(node.data..",") end print()
io.write("Reverse: ") for node in list:iterateReverse() do io.write(node.data..",") end print()
- Output:
Forward: 1,2,3,4,5, Reverse: 5,4,3,2,1,
Liberty BASIC
struct block,nxt as ulong,prev as ulong,nm as char[20],age as long'Our structure of the blocks in our list.
global hHeap
global hFirst
global hLast
global blockCount
global blockSize
blockSize=len(block.struct)
call Init
if hHeap=0 then
print "Error occured! Could not create heap, exiting..."
end
end if
FirstUser=New("David",20)
notImportant=New("Jessica",35)
notImportant=New("Joey",38)
MiddleUser=New("Jack",56)
notImportant=New("Amy",17)
notImportant=New("Bob",28)
LastUser=New("Kenny",56)
print "-Traversing the list forwards"
hCurrent=hFirst
while hCurrent<>0
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent)
hCurrent=Block.next(hCurrent)
wend
print
print "-Deleting first, middle, and last person."
call Delete FirstUser'1
call Delete MiddleUser'2
call Delete LastUser'3
print
print "-Traversing the list backwards"
hCurrent=hLast
while hCurrent<>0
print tab(2);dechex$(hCurrent);" ";Block.name$(hCurrent);" ";Block.age(hCurrent)
hCurrent=Block.prev(hCurrent)
wend
call Uninit
end
function Block.next(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.next=block.nxt.struct
end function
function Block.prev(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.prev=block.prev.struct
end function
function Block.age(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.age=block.age.struct
end function
function Block.name$(hBlock)
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
Block.name$=block.nm.struct
end function
sub Block.age hBlock,age
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.age.struct=age
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
sub Block.name hBlock,name$
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.nm.struct=name$
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
sub Block.next hBlock,nxt
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.nxt.struct=nxt
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
sub Block.prev hBlock,prev
calldll #kernel32,"RtlMoveMemory",block as struct,hBlock as ulong,blockSize as long,ret as void
block.prev.struct=prev
calldll #kernel32,"RtlMoveMemory",hBlock as ulong,block as struct,blockSize as long,ret as void
end sub
function New(name$,age)
calldll #kernel32,"HeapAlloc",hHeap as ulong,_HEAP_ZERO_MEMORY as ulong,blockSize as long,New as ulong
if New<>0 then
blockCount=blockCount+1
if hFirst=0 then
hFirst=New
hLast=New
else
call Block.next hLast,New
call Block.prev New,hLast
hLast=New
end if
call Block.name New,name$
call Block.age New,age
end if
end function
sub Delete hBlock
if hBlock<>0 then
blockCount=blockCount-1
if blockCount=0 then
hFirst=0
hLast=0
else
if hBlock=hFirst then
hFirst=Block.next(hBlock)
call Block.prev hFirst,0
else
if hBlock=hLast then
hLast=Block.prev(hBlock)
call Block.next hLast,0
else
call Block.next Block.prev(hBlock),Block.next(hBlock)
call Block.prev Block.next(hBlock),Block.prev(hBlock)
end if
end if
end if
calldll #kernel32,"HeapFree",hHeap as ulong,0 as long,hBlock as ulong,ret as void
end if
end sub
sub Init
calldll #kernel32,"HeapCreate",0 as long,10000 as long,0 as long,hHeap as ulong
end sub
sub Uninit
calldll #kernel32,"HeapDestroy",hHeap as ulong,ret as void
end sub
Nim
type
List[T] = object
head, tail: Node[T]
Node[T] = ref TNode[T]
TNode[T] = object
next, prev: Node[T]
data: T
proc initList[T](): List[T] = discard
proc newNode[T](data: T): Node[T] =
new(result)
result.data = data
proc prepend[T](l: var List[T], n: Node[T]) =
n.next = l.head
if l.head != nil: l.head.prev = n
l.head = n
if l.tail == nil: l.tail = n
proc append[T](l: var List[T], n: Node[T]) =
n.next = nil
n.prev = l.tail
if l.tail != nil:
l.tail.next = n
l.tail = n
if l.head == nil:
l.head = n
proc insertAfter[T](l: var List[T], r, n: Node[T]) =
n.prev = r
n.next = r.next
n.next.prev = n
r.next = n
if r == l.tail: l.tail = n
proc remove[T](l: var List[T], n: Node[T]) =
if n == l.tail: l.tail = n.prev
if n == l.head: l.head = n.next
if n.next != nil: n.next.prev = n.prev
if n.prev != nil: n.prev.next = n.next
proc `$`[T](l: var List[T]): string =
result = ""
var n = l.head
while n != nil:
if result.len > 0: result.add(" -> ")
result.add($n.data)
n = n.next
iterator traverseForward[T](l: List[T]): T =
var n = l.head
while n != nil:
yield n.data
n = n.next
iterator traverseBackward[T](l: List[T]): T =
var n = l.tail
while n != nil:
yield n.data
n = n.prev
var l = initList[int]()
var n = newNode(12)
var m = newNode(13)
var i = newNode(14)
var j = newNode(15)
l.append(n)
l.prepend(m)
l.insertAfter(m, i)
l.prepend(j)
l.remove(m)
for i in l.traverseForward():
echo "> ", i
for i in l.traverseBackward():
echo "< ", i
Oberon-2
MODULE Collections;
IMPORT Box;
TYPE
Action = PROCEDURE (o: Box.Object);
PROCEDURE (dll: DLList) GoForth*(do: Action);
VAR
iter: Node;
BEGIN
iter := dll.first;
WHILE iter # NIL DO
do(iter.value);
iter := iter.next
END
END GoForth;
PROCEDURE (dll: DLList) GoBack*(do: Action);
VAR
iter: Node;
BEGIN
ASSERT(dll.last # NIL);
iter := dll.last;
WHILE iter # NIL DO
do(iter.value);
iter := iter.prev
END
END GoBack;
END Collections.
Objeck
class Traverse {
function : Main(args : String[]) ~ Nil {
list := Collection.IntList->New();
list->Insert(100);
list->Insert(50);
list->Insert(25);
list->Insert(10);
list->Insert(5);
"-- forward --"->PrintLine();
list->Rewind();
while(list->More()) {
list->Get()->PrintLine();
list->Next();
};
"-- backward --"->PrintLine();
list->Forward();
while(list->More()) {
list->Get()->PrintLine();
list->Previous();
};
}
}
-- forward -- 100 5 10 25 50 -- backward -- 50 25 10 5 100
Oforth
Complete definition is here : Doubly-linked list/Definition#Oforth
Defining #forEachNext and #forEachPrev allow to traverse this double linked list using #forEach: and #revEach: syntax
DList method: forEachNext
dup ifNull: [ drop @head ifNull: [ false ] else: [ @head @head true] return ]
next dup ifNull: [ drop false ] else: [ dup true ] ;
DList method: forEachPrev
dup ifNull: [ drop @tail ifNull: [ false ] else: [ @tail @tail true] return ]
prev dup ifNull: [ drop false ] else: [ dup true ] ;
: test
| dl n |
DList new ->dl
dl insertFront("A")
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
"Traversal (beginning to end) : " println
dl forEach: n [ n . ]
"\nTraversal (end to beginning) : " println
dl revEach: n [ n . ] ;
- Output:
>test Traversal (beginning to end) : A C B Traversal (end to beginning) : B C A ok
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}
Pascal
See Delphi
Phix
enum NEXT,PREV,DATA constant empty_dll = {{1,1}} sequence dll = deep_copy(empty_dll) procedure insert_after(object data, integer pos=1) integer prv = dll[pos][PREV] dll = append(dll,{pos,prv,data}) if prv!=0 then dll[prv][NEXT] = length(dll) end if dll[pos][PREV] = length(dll) end procedure insert_after("ONE") insert_after("TWO") insert_after("THREE") ?dll procedure show(integer d) integer idx = dll[1][d] while idx!=1 do ?dll[idx][DATA] idx = dll[idx][d] end while end procedure show(NEXT) ?"==" show(PREV)
- Output:
{{2,4},{3,1,"ONE"},{4,2,"TWO"},{1,3,"THREE"}} "ONE" "TWO" "THREE" "==" "THREE" "TWO" "ONE"
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) )
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
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 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;
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
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())
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.
Racket
See Doubly-Linked List for the structure definitions.
These functions traverse the list in the two directions. They create a native (singly-linked) list by adding to the front, so they traverse in the reverse order from the desired result order.
(define (dlist-elements dlist)
(let loop ([elements '()] [dlink (dlist-tail dlist)])
(if dlink
(loop (cons (dlink-content dlink) elements) (dlink-prev dlink))
elements)))
(define (dlist-elements/reverse dlist)
(let loop ([elements '()] [dlink (dlist-head dlist)])
(if dlink
(loop (cons (dlink-content dlink) elements) (dlink-next dlink))
elements)))
Raku
(formerly Perl 6)
Since the list routines are supplied by the generic roles defined in Doubly-linked_list/Definition#Raku, it suffices to say:
say $dll.list;
say $dll.reverse;
These automatically return just the payloads, hiding the elements containing the forward and backward pointers.
REXX
REXX doesn't have linked lists, as there are no pointers (or handles). However, linked lists can be simulated with lists in 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 /*stick a fork in it, we're done.*/
/*──────────────────────────────────subroutines─────────────────────────*/
p: return word(arg(1),1)
sy: say; say left('',30) "───" arg(1) '───'; return
@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 /*j*/
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
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
Ring
# Project : Doubly-linked list/Traversal
trav = [123, 789, 456]
travfor = sort(trav)
see "Traverse forwards:" + nl
see travfor
see nl
travback = reverse(travfor)
see "Traverse backwards:" + nl
see travback
see nl
Output:
Traverse forwards: 123 456 789 Traverse backwards: 789 456 123
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}
Salmon
Without explicit type information:
class item(init_data)
{
variable next,
previous,
data := init_data;
};
function prepend(tail, new_data)
{
immutable result := item(new_data);
result.next := tail;
result.previous := null;
if (tail != null)
tail.previous := result;;
return result;
};
variable my_list := null;
my_list := prepend(my_list, "R");
my_list := prepend(my_list, "o");
my_list := prepend(my_list, "s");
my_list := prepend(my_list, "e");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "a");
"Items in the list going forward:"!
variable follow := my_list;
while (true)
{
follow.data!
if (follow.next == null)
break;;
}
step
follow := follow.next;;
"Items in the list going backward:"!
while (follow != null)
follow.data!
step
follow := follow.previous;;
With explicit type information:
class item(init_data : string)
{
variable next: item | {null},
previous : item | {null},
data : string := init_data;
};
function prepend(tail : item | {null}, new_data : string) returns item
{
immutable result := item(new_data);
result.next := tail;
result.previous := null;
if (tail != null)
tail.previous := result;;
return result;
};
variable my_list : item | {null} := null;
my_list := prepend(my_list, "R");
my_list := prepend(my_list, "o");
my_list := prepend(my_list, "s");
my_list := prepend(my_list, "e");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "t");
my_list := prepend(my_list, "a");
"Items in the list going forward:"!
variable follow : item | {null} := my_list;
while (true)
{
follow.data!
if (follow.next == null)
break;;
}
step
follow := follow.next;;
"Items in the list going backward:"!
while (follow != null)
follow.data!
step
follow := follow.previous;;
Both of these produce the following output:
Items in the list going forward: a t t e s o R Items in the list going backward: R o s e t t a
Scala
import java.util
object DoublyLinkedListTraversal extends App {
private val ll = new util.LinkedList[String]
private def traverse(iter: util.Iterator[String]) =
while (iter.hasNext) iter.next
traverse(ll.iterator)
traverse(ll.descendingIterator)
}
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
Wren
import "./llist" for DLinkedList
import "./fmt" for Fmt
// create a new doubly-linked list and add the first 50 positive integers to it
var dll = DLinkedList.new(1..50)
// traverse the doubly-linked list from head to tail
for (i in dll) {
Fmt.write("$4d ", i)
if (i % 10 == 0) System.print()
}
System.print()
// traverse the doubly-linked list from tail to head
for (i in dll.reversed) {
Fmt.write("$4d ", i)
if (i % 10 == 1) System.print()
}
- Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
XPL0
def \Node\ Prev, Data, Next; \Element (Node) definition
def SizeofInt = 4;
proc Insert(NewNode, Node); \Insert NewNode after Node
int NewNode, Node, NextNode;
[NextNode:= Node(Next);
NextNode(Prev):= NewNode;
NewNode(Next):= NextNode;
NewNode(Prev):= Node;
Node(Next):= NewNode;
];
int Head(3), Tail(3); \Doubly linked list definition
int N, NewNode, Node;
[\Further define (initialize) the doubly linked list
Head(Next):= Tail;
Tail(Prev):= Head;
\Insert some Nodes containing square data
for N:= 1 to 10 do
[NewNode:= Reserve(3*SizeofInt);
NewNode(Data):= N*N;
Insert(NewNode, Head);
];
\Traverse list from Head to Tail
Node:= Head(Next);
while Node # Tail do
[IntOut(0, Node(Data)); ChOut(0, ^ );
Node:= Node(Next);
];
CrLf(0);
\Traverse list from Tail to Head
Node:= Tail(Prev);
while Node # Head do
[IntOut(0, Node(Data)); ChOut(0, ^ );
Node:= Node(Prev);
];
CrLf(0);
]
- Output:
100 81 64 49 36 25 16 9 4 1 1 4 9 16 25 36 49 64 81 100
zkl
class Node{
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
fcn toString{ value.toString() }
fcn append(value){
b,c := Node(value,self,next),next;
next=b;
if(c) c.prev=b;
b
}
}
a,c := Node("a"), a.append("b").append("c");
n:=a; while(n){ print(n," "); n=n.next }
println();
n:=c; while(n){ print(n," "); n=n.prev }
println();
- Output:
a b c c b a
- Programming Tasks
- Data Structures
- Iteration
- Action!
- Action! Tool Kit
- Ada
- ALGOL 68
- ALGOL W
- Applesoft BASIC
- ARM Assembly
- AutoHotkey
- Axe
- BBC BASIC
- C
- C sharp
- C++
- Clojure
- D
- Delphi
- E
- E examples needing attention
- Examples needing attention
- Erlang
- F Sharp
- Fortran
- FreeBASIC
- Go
- Groovy
- Haskell
- Unicon
- J
- Java
- JavaScript
- Julia
- Kotlin
- Lua
- Liberty BASIC
- Nim
- Oberon-2
- Objeck
- Oforth
- Oz
- Pascal
- Phix
- PicoLisp
- PL/I
- PureBasic
- Python
- Racket
- Raku
- REXX
- Ring
- Ruby
- Salmon
- Scala
- Tcl
- Wren
- Wren-llist
- Wren-fmt
- XPL0
- Zkl
- ACL2/Omit
- GUISS/Omit