Doubly-linked list/Definition: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (48 intermediate revisions by 24 users not shown) | |||
Line 8:
{{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="5"
TYPE ListNode=[BYTE data PTR prv,nxt]
ListNode POINTER listBegin,listEnd
PROC AddBegin(BYTE v)
ListNode POINTER n
n=Alloc(NODE_SIZE)
n.data=v
n.prv=0
n.nxt=listBegin
IF listBegin THEN
listBegin.prv=n
ELSE
listEnd=n
FI
listBegin=n
RETURN
PROC AddEnd(BYTE 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 AddBefore(BYTE v ListNode POINTER node)
ListNode POINTER n,tmp
IF node=0 THEN
PrintE("The node is null!") Break()
ELSEIF node=listBegin THEN
AddBegin(v)
ELSE
n=Alloc(NODE_SIZE)
n.data=v
n.prv=node.prv
n.nxt=node
tmp=node.prv
tmp.nxt=n
node.prv=n
FI
RETURN
PROC AddAfter(BYTE v ListNode POINTER node)
ListNode POINTER n,tmp
IF node=0 THEN
PrintE("The node is null!") Break()
ELSEIF node=listEnd THEN
AddEnd(v)
ELSE
n=Alloc(NODE_SIZE)
n.data=v
n.nxt=node.nxt
n.prv=node
tmp=node.nxt
tmp.prv=n
node.nxt=n
FI
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 PrintList()
ListNode POINTER n
n=listBegin
Print("(")
WHILE n
DO
PrintB(n.data)
IF n.nxt THEN
Print(", ")
FI
n=n.nxt
OD
PrintE(")")
RETURN
PROC TestAddBegin(BYTE v)
AddBegin(v)
PrintF("Add %B at the begin:%E",v)
PrintList()
RETURN
PROC TestAddEnd(BYTE v)
AddEnd(v)
PrintF("Add %B at the end:%E",v)
PrintList()
RETURN
PROC TestAddBefore(BYTE v ListNode POINTER node)
AddBefore(v,node)
PrintF("Add %B before %B:%E",v,node.data)
PrintList()
RETURN
PROC TestAddAfter(BYTE v ListNode POINTER node)
AddAfter(v,node)
PrintF("Add %B after %B:%E",v,node.data)
PrintList()
RETURN
PROC TestClear()
Clear()
PrintE("Clear the list:")
PrintList()
RETURN
PROC Main()
Put(125) PutE() ;clear screen
AllocInit(0)
listBegin=0
listEnd=0
PrintList()
TestAddBegin(1)
TestAddBegin(2)
TestAddEnd(3)
TestAddBefore(4,listBegin.nxt)
TestAddBefore(5,listBegin)
TestAddAfter(6,listEnd.prv)
TestAddAfter(7,listEnd)
TestClear()
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Doubly-linked_list_definition.png Screenshot from Atari 8-bit computer]
<pre>
()
Add 1 at the begin:
(1)
Add 2 at the begin:
(2, 1)
Add 3 at the end:
(2, 1, 3)
Add 4 before 1:
(2, 4, 1, 3)
Add 5 before 2:
(5, 2, 4, 1, 3)
Add 6 after 1:
(5, 2, 4, 1, 6, 3)
Add 7 after 3:
(5, 2, 4, 1, 6, 3, 7)
Clear the list:
()
</pre>
=={{header|Ada}}==
Line 20 ⟶ 198:
{{works with|ALGOL 68|Revision 1 - one extension to language used - PRAGMA READ - a non standard feature similar to C's #include directive.}}{{works with|ALGOL 68G|Any - tested with release algol68g-2.7}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
'''File: prelude/Doubly-linked_list_Link.a68'''<
COMMENT REQUIRES:
MODE VALUE = ~;
Line 34 ⟶ 212:
MODE LINK = REF LINKNEW;
SKIP</
MODE LISTNEW = LINKNEW;
MODE LIST = REF LISTNEW;
Line 81 ⟶ 259:
link ISNT LINK(self);
SKIP</
# -*- coding: utf-8 -*- #
MODE VALUE = STRING; # user defined data type #
Line 125 ⟶ 303:
OD;
print(new line)
)</
{{out}}
<pre>
Line 132 ⟶ 310:
Empty from tail: saw I cat a it Was
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program defDblList.s */
/* 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"
szCarriageReturn: .asciz "\n"
szMessErreur: .asciz "Error detected.\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
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
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 @ create 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 @ save list address
bl searchValue @ search 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
/******************************************************************/
/* 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
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registers
mov r2,#0 @ counter length */
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call system
pop {r0,r1,r2,r7,lr} @ restaur registers
bx lr @ return
</syntaxhighlight>
=={{header|ATS}}==
{{trans|Scheme}}
The example is broken into an interface ("static") file ''dllist.sats'', an implementation ("dynamic") file ''dllist.dats'', and a demonstration program ''dllist-demo.dats''. I broke up the example this way because the abstraction thus introduced is important; the implementation is a linear type, whereas the user sees it as a nonlinear type. The interface file completely hides the linear typing.
The reason for this complication is that, in ATS, a linear object can be treated as "mutable", without resorting to embedded C code. One cost of this is that an object of a linear type has to be freed explicitly. However, if it is cast to an "ordinary" (nonlinear) type, a garbage collector to handle freeing the object. Such casting is what I have done.
In the following, the doubly linked list and its nodes are not distinct types. The nodes form a circle, but they do not form a circular list, because one of the nodes is a "root" node that holds no value, cannot be deleted, and is marked as special.
Here is ''dllist.sats''.
<syntaxhighlight lang="ats">(********************************************************************)
(* The public interface *)
abstype dllist_t (t : t@ype+, is_root : bool) (* An abstract type. *)
typedef dllist_t (t : t@ype+) = [b : bool] dllist_t (t, b)
(* Make a new dllist_t, consisting of a root node. *)
fun {t : t@ype}
dllist_t_make () : dllist_t (t, true)
(* Is this the root node, with no element stored? *)
fun {t : t@ype}
dllist_t_is_root
{is_root : bool}
(dl : dllist_t (t, is_root)) :
[b : bool | b == is_root]
bool b
(* Is this a non-root node, with an element stored? *)
fun {t : t@ype}
dllist_t_isnot_root
{is_root : bool}
(dl : dllist_t (t, is_root)) :
[b : bool | b == ~is_root]
bool b
(* Return the root node of the list. *)
fun {t : t@ype}
dllist_t_root (dl : dllist_t t) : dllist_t (t, true)
(* Return the previous node. *)
fun {t : t@ype}
dllist_t_previous (dl : dllist_t t) : dllist_t t
(* Return the next node. *)
fun {t : t@ype}
dllist_t_next (dl : dllist_t t) : dllist_t t
(* Insert an element before the given node. *)
fun {t : t@ype}
dllist_t_insert_before (dl : dllist_t t, elem : t) : void
(* Insert an element after the given node. *)
fun {t : t@ype}
dllist_t_insert_after (dl : dllist_t t, elem : t) : void
(* Remove the given node. It is an error to call this on the root
node. *)
fun {t : t@ype}
dllist_t_remove (dl : dllist_t t) : void
(* Return a copy of the stored element. It is an error to call this on
the root node. *)
fun {t : t@ype}
dllist_t_element (dl: dllist_t t) : t
fun {t : t@ype}
dllist_t_make_generator (dl: dllist_t t, direction : int) :
() -<cloref1> Option t
fun {t : t@ype}
dllist_t_to_list
(dl : dllist_t t) : [n : nat] list (t, n)
fun {t : t@ype}
list_to_dllist_t
{n : int}
(dl : list (t, n)) : dllist_t t
(********************************************************************)</syntaxhighlight>
Here is ''dllist.dats''.
<syntaxhighlight lang="ats">#define ATS_DYNLOADFLAG 0
#include "share/atspre_staload.hats"
staload "dllist.sats"
staload UN = "prelude/SATS/unsafe.sats"
(********************************************************************)
(* The implementation in terms of linear types. *)
absprop NODEPTR (t : t@ype+, is_root : bool, p : addr)
vtypedef nodeptr_vt (t : t@ype+, is_root : bool, p : addr) =
@(NODEPTR (t, is_root, p) | ptr p)
vtypedef nodeptr_vt (t : t@ype+, p : addr) =
[is_root : bool] nodeptr_vt (t, is_root, p)
vtypedef nodeptr_vt (t : t@ype+, is_root : bool) =
[p : addr] nodeptr_vt (t, is_root, p)
vtypedef nodeptr_vt (t : t@ype+) =
[is_root : bool] [p : addr] nodeptr_vt (t, is_root, p)
datavtype node_vt (t : t@ype+, is_root : bool) =
| node_vt_object (t, is_root) of
(bool is_root, (* Is it the root node? *)
nodeptr_vt t, (* previous*)
nodeptr_vt t, (* next *)
t) (* element *)
vtypedef node_vt (t : t@ype+) =
[is_root : bool] node_vt (t, is_root)
extern castfn
node2nodeptr_consuming :
{t : t@ype}
{is_root : bool}
node_vt (t, is_root) -<> nodeptr_vt (t, is_root)
extern castfn
nodeptr2node_consuming :
{t : t@ype}
{is_root : bool}
nodeptr_vt (t, is_root) -<> node_vt (t, is_root)
extern castfn
node2nodeptr_preserving :
{t : t@ype}
{is_root : bool}
(!node_vt (t, is_root) >> _) -<> nodeptr_vt (t, is_root)
extern castfn
nodeptr2node_preserving :
{t : t@ype}
{is_root : bool}
(!nodeptr_vt (t, is_root) >> _) -<> node_vt (t, is_root)
fn {t : t@ype}
node_refcopy {is_root : bool}
(node : !node_vt (t, is_root)) :
node_vt (t, is_root) =
nodeptr2node_preserving (node2nodeptr_preserving node)
fn {t : t@ype}
make_root () : node_vt (t, true) =
(* Create a node that is marked as a root, points to itself, and has
no actual element stored in it. *)
let
var fake_elem : t?
prval _ = $UN.castview2void_at{t} (view@ fake_elem)
val node = node_vt_object (true,
$UN.castvwtp0 the_null_ptr,
$UN.castvwtp0 the_null_ptr,
fake_elem)
val prev_val = node2nodeptr_preserving node
val next_val = node2nodeptr_preserving node
val+ @ node_vt_object (_, prev, next, _) = node
val _ = prev := prev_val
val _ = next := next_val
prval _ = fold@ node
in
node
end
fn {t : t@ype}
is_root {is_root : bool}
(node : !node_vt (t, is_root)) :
[b : bool | b == is_root] bool b =
case+ node of
| node_vt_object (is_root, _, _, _) => is_root
fn {t : t@ype}
isnot_root {is_root : bool}
(node : !node_vt (t, is_root)) :
[b : bool | b == ~is_root] bool b =
~is_root<t> node
fn {t : t@ype}
find_root (node : !node_vt t) : node_vt (t, true) =
let
fun
loop (node : !node_vt t) : node_vt (t, true) =
case+ node of
| node_vt_object (true, _, _, _) => node_refcopy node
| node_vt_object (false, prev, _, _) =>
let
val prev_node = nodeptr2node_preserving prev
val retval = loop prev_node
val _ = $UN.castvwtp0{void} prev_node
in
retval
end
in
loop node
end
fn {t : t@ype}
get_prev (node : !node_vt t) : node_vt t =
let
val+ @ node_vt_object (_, prev, _, _) = node
val prev_node = nodeptr2node_preserving prev
prval _ = fold@ node
in
prev_node
end
fn {t : t@ype}
get_next (node : !node_vt t) : node_vt t =
let
val+ @ node_vt_object (_, _, next, _) = node
val next_node = nodeptr2node_preserving next
prval _ = fold@ node
in
next_node
end
fn {t : t@ype}
set_prev (node : !node_vt t, prev_val : !node_vt t) : void =
{
val+ @ node_vt_object (_, prev, _, _) = node
val _ = prev := node2nodeptr_preserving prev_val
prval _ = fold@ node
}
fn {t : t@ype}
set_next (node : !node_vt t, next_val : !node_vt t) : void =
{
val+ @ node_vt_object (_, _, next, _) = node
val _ = next := node2nodeptr_preserving next_val
prval _ = fold@ node
}
fn {t : t@ype}
insert_before (node : !node_vt t, elem : t) : void =
{
val prev_node = get_prev<t> node
val new_node =
node_vt_object (false, node2nodeptr_preserving prev_node,
node2nodeptr_preserving node, elem)
val _ = set_next<t> (prev_node, new_node)
val _ = set_prev<t> (node, new_node)
val _ = $UN.castvwtp0{void} prev_node
val _ = $UN.castvwtp0{void} new_node
}
fn {t : t@ype}
insert_after (node : !node_vt t, elem : t) : void =
{
val next_node = get_next<t> node
val new_node =
node_vt_object (false, node2nodeptr_preserving node,
node2nodeptr_preserving next_node, elem)
val _ = set_next<t> (node, new_node)
val _ = set_prev<t> (next_node, new_node)
val _ = $UN.castvwtp0{void} next_node
val _ = $UN.castvwtp0{void} new_node
}
fn {t : t@ype}
remove (node : !node_vt t) : void =
{
val _ = assertloc (isnot_root<t> node)
val prev_node = get_prev<t> node
val next_node = get_next<t> node
val _ = set_next<t> (prev_node, next_node)
val _ = set_prev<t> (next_node, prev_node)
val _ = $UN.castvwtp0{void} prev_node
val _ = $UN.castvwtp0{void} next_node
}
fn {t : t@ype}
get_element (node : !node_vt t) : t =
case+ node of
| node_vt_object (is_root, _, _, elem) =>
begin
assertloc (~is_root);
elem
end
(********************************************************************)
(* Implementation of the public interface. *)
(* The public interface is "nonlinear"; that is, its types are
"ordinary", and will have to be managed by a garbage collector, if
you do not want them to leak freely. The need to free the linear
types is bypassed by these interface template functions.
A garbage collector, of course, is necessary for a great many
programming languages, and with more of them all the time. So it is
nothing extraordinary.
The usual garbage collector to use with ATS2 (Postiats) is Boehm
GC. *)
assume dllist_t (t, is_root) = ptr
implement {t}
dllist_t_make () =
$UN.castvwtp0 (make_root<t> ())
implement {t}
dllist_t_is_root {is_root} dl =
let
val node = $UN.castvwtp0{node_vt (t, is_root)} dl
val retval = is_root<t> node
val _ = $UN.castvwtp0{void} node
in
retval
end
implement {t}
dllist_t_isnot_root {is_root} dl =
let
val node = $UN.castvwtp0{node_vt (t, is_root)} dl
val retval = isnot_root<t> node
val _ = $UN.castvwtp0{void} node
in
retval
end
implement {t}
dllist_t_root dl =
let
val node = $UN.castvwtp0{node_vt t} dl
val root = find_root<t> node
val _ = $UN.castvwtp0{void} node
in
$UN.castvwtp0 root
end
implement {t}
dllist_t_previous dl =
let
val node = $UN.castvwtp0{node_vt t} dl
val prev = get_prev<t> node
val _ = $UN.castvwtp0{void} node
in
$UN.castvwtp0 prev
end
implement {t}
dllist_t_next dl =
let
val node = $UN.castvwtp0{node_vt t} dl
val next = get_next<t> node
val _ = $UN.castvwtp0{void} node
in
$UN.castvwtp0 next
end
implement {t}
dllist_t_insert_before (dl, elem) =
let
val node = $UN.castvwtp0{node_vt t} dl
val next = insert_before<t> (node, elem)
val _ = $UN.castvwtp0{void} node
in
end
implement {t}
dllist_t_insert_after (dl, elem) =
let
val node = $UN.castvwtp0{node_vt t} dl
val next = insert_after<t> (node, elem)
val _ = $UN.castvwtp0{void} node
in
end
implement {t}
dllist_t_remove dl =
let
val node = $UN.castvwtp0{node_vt t} dl
val next = remove<t> node
val _ = $UN.castvwtp0{void} node
in
end
implement {t}
dllist_t_element dl =
let
val node = $UN.castvwtp0{node_vt t} dl
val elem = get_element<t> node
val _ = $UN.castvwtp0{void} node
in
elem
end
implement {t}
dllist_t_make_generator (dl, direction) =
if isltz direction then
let
val node_ref = ref (dllist_t_previous<t> (dllist_t_root<t> dl))
val p_node = $UN.castvwtp0{ptr} node_ref
in
lam () =>
let
val node_ref = $UN.castvwtp0{ref (dllist_t t)} p_node
val node = !node_ref
in
if dllist_t_is_root<t> node then
None ()
else
let
val elem = dllist_t_element<t> node
in
!node_ref := dllist_t_previous<t> node;
Some elem
end
end
end
else
let
val node_ref = ref (dllist_t_next<t> (dllist_t_root<t> dl))
val p_node = $UN.castvwtp0{ptr} node_ref
in
lam () =>
let
val node_ref = $UN.castvwtp0{ref (dllist_t t)} p_node
val node = !node_ref
in
if dllist_t_is_root<t> node then
None ()
else
let
val elem = dllist_t_element<t> node
in
!node_ref := dllist_t_next<t> node;
Some elem
end
end
end
implement {t}
dllist_t_to_list dl =
let
var lst : List0 t = list_nil ()
var xopt : Option t
val gen = dllist_t_make_generator<t> (dl, ~1)
in
for (xopt := gen (); option_is_some xopt; xopt := gen ())
case+ xopt of
| Some x => lst := list_cons (x, lst);
lst
end
implement {t}
list_to_dllist_t lst =
let
val root = dllist_t_make<t> ()
var dl : dllist_t t = root
var p : List t
in
for (p := lst; isneqz p; p := list_tail p)
begin
dllist_t_insert_after<t> (dl, list_head p);
dl := dllist_t_next<t> dl
end;
root
end
(********************************************************************)</syntaxhighlight>
And here is ''dllist-demo.dats''.
<syntaxhighlight lang="ats">#include "share/atspre_staload.hats"
staload "dllist.sats"
staload _ = "dllist.dats"
(* Using macdefs as follows, rather than implementing compiled
functions in terms of the templates, means the templates will be
expanded each time you call the macro. You may or may not wish
this. You *might* get big code that optimizes well. *)
typedef dl_t = dllist_t int
macdef dlmake = dllist_t_make<int>
macdef insert_before = dllist_t_insert_before<int>
macdef insert_after = dllist_t_insert_after<int>
macdef remove = dllist_t_remove<int>
macdef get_root = dllist_t_root<int>
macdef get_prev = dllist_t_previous<int>
macdef get_next = dllist_t_next<int>
macdef is_root = dllist_t_is_root<int>
macdef isnot_root = dllist_t_isnot_root<int>
macdef get_element = dllist_t_element<int>
macdef make_generator = dllist_t_make_generator<int>
macdef dl2list = dllist_t_to_list<int>
macdef list2dl = list_to_dllist_t<int>
fn
print_forwards (dl : dl_t) =
let
val gen = make_generator (dl, 1)
var xopt : Option int
var separator : string = ""
in
for (xopt := gen (); option_is_some xopt; xopt := gen ())
case+ xopt of
| Some x =>
begin
print! separator;
print! x;
separator := " "
end
end
fn
print_backwards (dl : dl_t) =
let
val gen = make_generator (dl, ~1)
var xopt : Option int
var separator : string = ""
in
for (xopt := gen (); option_is_some xopt; xopt := gen ())
case+ xopt of
| Some x =>
begin
print! separator;
print! x;
separator := " "
end
end
implement
main0 () =
{
val dl = list2dl ($list{int} (10, 20, 30, 40, 50))
val _ = print! ("doubly linked list: ")
val _ = print_forwards dl
val _ = println! ()
val _ = print! ("conversion to a regular list: ")
val _ = println! (dl2list dl)
val _ = print! ("traversal backwards: ")
val _ = print_backwards dl
val _ = println! ()
val _ = print! ("traversal forwards, given a non-root node: ")
val _ = print_forwards (get_prev (get_prev dl))
val _ = println! ()
val _ = print! ("traversal backwards, given a non-root node: ")
val _ = print_backwards (get_prev (get_prev dl))
val _ = println! ()
val _ = print! ("insertion after the root: ")
val _ = insert_after (dl, 5)
val _ = print_forwards dl
val _ = println! ()
val _ = print! ("insertion before the root: ")
val _ = insert_before (dl, 55)
val _ = print_forwards dl
val _ = println! ()
val _ = print! ("insertion after the second element: ")
val _ = insert_after (get_next (get_next dl), 15)
val _ = print_forwards dl
val _ = println! ()
val _ = print! ("insertion before the second from last element: ")
val _ = insert_before (get_prev (get_prev dl), 45)
val _ = print_forwards dl
val _ = println! ()
val _ = print! ("removal of the element 30: ")
val _ =
let
var p : dl_t
in
for (p := get_next dl; get_element p <> 30; p := get_next p)
();
remove p
end
val _ = print_forwards dl
val _ = println! ()
}</syntaxhighlight>
{{out}}
<pre>$ patscc -O2 -DATS_MEMALLOC_GCBDW dllist-demo.dats dllist.dats dllist.sats -lgc && ./a.out
doubly linked list: 10 20 30 40 50
conversion to a regular list: 10, 20, 30, 40, 50
traversal backwards: 50 40 30 20 10
traversal forwards, given a non-root node: 10 20 30 40 50
traversal backwards, given a non-root node: 50 40 30 20 10
insertion after the root: 5 10 20 30 40 50
insertion before the root: 5 10 20 30 40 50 55
insertion after the second element: 5 10 15 20 30 40 50 55
insertion before the second from last element: 5 10 15 20 30 40 45 50 55
removal of the element 30: 5 10 15 20 40 45 50 55</pre>
''Aside: This is a form of doubly linked list I first implemented in Fortran 2018 for a mark-and-sweep garbage collector. I used the list to store the mutator roots.''
=={{header|AutoHotkey}}==
Line 138 ⟶ 1,165:
=={{header|C}}==
<
#include <stdio.h>
#include <stdlib.h>
Line 294 ⟶ 1,321:
n->succ->pred = n->pred;
return n;
}</
Simple test:
<
struct IntNode {
Line 332 ⟶ 1,359:
free(lista);
}
}</
=={{header|C sharp|C#}}==
The .NET framework provides the <code>LinkedListNode<T></code> class, which represents an individual node of a linked list, and the <code>LinkedList<T></code> class, which provides abstractions to read and modify a list as if it were a single object. The <code>LinkedListNode<T>.Next</code> and <code>LinkedListNode<T>.Previous</code> properties is read-only, ensuring that all lists must be created using <code>LinkedList<T></code> and that each list can only be mutated using the methods of its <code>LinkedList<T></code> instance (the appropriate .NET accessibility modifiers are used to hide these implementation details).
One node instance is forbidden to be in multiple lists; this is enforced using the <code>LinkedListNode<T>.List</code> property, which is set accordingly when a node is added to a <code>LinkedList<T></code> and set to <code>null</code> when it is removed. This also has the effect of preventing cycles.
Though mutating the ''structure'' of a list can only be done through the <code>LinkedList<T></code> class, mutating the values contained by the nodes of a list is done through its individual <code>LinkedListNode<T></code> instances, as the <code>LinkedListNode<T>.Next</code>.Value property is settable.
<syntaxhighlight lang="c sharp">using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
LinkedList<string> list = new LinkedList<string>();
list.AddFirst(".AddFirst() adds at the head.");
list.AddLast(".AddLast() adds at the tail.");
LinkedListNode<string> head = list.Find(".AddFirst() adds at the head.");
list.AddAfter(head, ".AddAfter() adds after a specified node.");
LinkedListNode<string> tail = list.Find(".AddLast() adds at the tail.");
list.AddBefore(tail, "Betcha can't guess what .AddBefore() does.");
System.Console.WriteLine("Forward:");
foreach (string nodeValue in list) { System.Console.WriteLine(nodeValue); }
System.Console.WriteLine("\nBackward:");
LinkedListNode<string> current = tail;
while (current != null)
{
System.Console.WriteLine(current.Value);
current = current.Previous;
}
}
}</syntaxhighlight>
{{out}}
<pre>Forward:
.AddFirst() adds at the head.
.AddAfter() adds after a specified node.
Betcha can't guess what .AddBefore() does.
.AddLast() adds at the tail.
Backward:
.AddLast() adds at the tail.
Betcha can't guess what .AddBefore() does.
.AddAfter() adds after a specified node.
.AddFirst() adds at the head.</pre>
=={{header|C++}}==
{{works with|C++11}}
<
#include <list>
Line 349 ⟶ 1,424:
std::cout << i << ' ';
std::cout << '\n';
}</
{{out}}
<pre>
9 1 5 7 6 0 3 2 4
</pre>
=={{header|Clojure}}==
<
(defprotocol PDoubleList
Line 512 ⟶ 1,541:
(defmethod print-method Node [n w]
(print-method (symbol "#:double_list.Node") w)
(print-method (into {} (dissoc n :m)) w))</
Usage:
<
;=> nil
(def dl (double-list (range 10)))
Line 535 ⟶ 1,564:
;=> #:double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}
(get-prev *1)
;=> #:double_list.Node{:prev #<Object ...>, :next #<Object ...>, :data 1, :key #<Object ...>}</
=={{header|Common Lisp}}==
<
(defstruct dlink content prev next)
Line 586 ⟶ 1,615:
acc
(extract-values (dlink-next dlink) (cons (dlink-content dlink) acc)))))
(reverse (extract-values (dlist-head dlist) nil))))</
The following produces <code>(1 2 3 4)</code>.
<
(insert-head dlist 1)
(insert-tail dlist 4)
Line 597 ⟶ 1,626:
(bad-link (insert-before dlist next-to-last 42)))
(remove-link dlist bad-link))
(print (dlist-elements dlist)))</
=={{header|D}}==
<syntaxhighlight lang="d">import std.stdio;
class LinkedList(T)
{
Node!(T) head, tail;
/** Iterate in the forward direction. */
int opApply (int delegate(uint, Node!(T)) dg)
Line 619 ⟶ 1,650:
return result;
}
static LinkedList!(T) fromArray (T[] array)
{
Line 641 ⟶ 1,672:
LinkedList!(T) parent;
T value;
this (Node!(T) next, Node!(T) previous, T value, LinkedList!(T) parent)
in
Line 657 ⟶ 1,688:
this.value = value;
this.parent = parent;
if (parent.head == next)
parent.head = this;
Line 663 ⟶ 1,694:
parent.tail = this;
}
/** Insert an element after this one. */
void insertAfter (T value)
{
new Node!(T)(
}
/** Insert an element before this one. */
void insertBefore (T value)
{
new Node!(T)(
}
/** Remove the current node from the list. */
void remove ()
Line 692 ⟶ 1,723:
void main ()
{
auto list = LinkedList!
for (auto elem = list.head; elem; elem = elem.next)
{
Line 705 ⟶ 1,736:
}
writeln;
}</
{{out}}
<pre>
Line 712 ⟶ 1,743:
Empty from tail: saw I cat a really it Was
</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| boost.LinkedList}}[[https://github.com/MaiconSoft/DelphiBoostLib]]
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Doubly_linked;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
boost.LinkedList;
var
List: TLinkedList<string>;
Head, Tail,Current: TLinkedListNode<string>;
Value:string;
begin
List := TLinkedList<string>.Create;
List.AddFirst('.AddFirst() adds at the head.');
List.AddLast('.AddLast() adds at the tail.');
Head := List.Find('.AddFirst() adds at the head.');
List.AddAfter(Head, '.AddAfter() adds after a specified node.');
Tail := List.Find('.AddLast() adds at the tail.');
List.AddBefore(Tail, 'Betcha can''t guess what .AddBefore() does.');
Writeln('Forward:');
for value in List do
Writeln(value);
Writeln(#10'Backward:');
Current:= Tail;
while Assigned(Current) do
begin
Writeln(Current.Value);
Current:= Current.Prev;
end;
List.Free;
Readln;
end.</syntaxhighlight>
=={{header|E}}==
<
def firstINode
def lastINode
Line 820 ⟶ 1,895:
}
return dlList
}</
<
# value: <>
Line 852 ⟶ 1,927:
? for x in 11..20 { list.push(x) }
? list
# value: <0, 1, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20></
=={{header|Erlang}}==
As with [[Singly-linked_list/Element_insertion]] a process is used to get mutability in Erlang's single assignment world.
<syntaxhighlight lang="erlang">
-module( doubly_linked_list ).
Line 924 ⟶ 1,999:
loop_foreach_previous( _Fun, noprevious ) -> ok;
loop_foreach_previous( Fun, Next ) -> Next ! {foreach_previous, Fun}.
</syntaxhighlight>
=={{header|F Sharp|F#}}==
<
type DList<'T> = {mutable front: DListAux<'T> option; mutable back: DListAux<'T> option} //'
Line 954 ⟶ 2,029:
if link.next = dlist.back then addBack dlist elt else
let e = Some {prev=Some link; data=elt; next=link.next}
link.next <- e</
=={{header|Fortran}}==
Tested with g95 and gfortran v. 4.6.
<
module dlist
implicit none
Line 1,167 ⟶ 2,241:
call tidy(mydll)
end program dl
</syntaxhighlight>
{{out}}
Line 1,174 ⟶ 2,248:
Doubly-linked list has 5 element - bwd = 7, 5, 4, 3, 1
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">Sub InsertaElto(lista() As String, posic As Integer = 1)
For i As Integer = Lbound(lista) To Ubound(lista)
If i = posic Then Swap lista(i), lista(Ubound(lista))
Next i
End Sub
Sub mostrarLista(lista() As String, titulo As String)
'display all elements from list of strings
Print !"\n"; titulo;
For i As Integer = Lbound(lista) To Ubound(lista)
Print lista(i); " ";
Next i
Print ""
End Sub
Dim As String arr() 'create a new list of strings
Dim As String elto 'items to add to the list
Dim As Integer j, c = 0
Restore datos
Do
Read elto : c += 1
If elto <> "EndOfData" Then Redim Preserve arr(c) : arr(c) = elto
Loop Until elto = "EndOfData"
Dim As Integer lb = Lbound(arr), ub = Ubound(arr)
Dim As String arrTMP(ub)
For j = lb To ub : arrTMP(ub-j) = arr(j)
Next j
For j = lb To ub : Swap arr(j), arrTMP(j)
Next j
mostrarLista(arr(),"Insertion at Head: ")
Erase arr
Restore datos
c = 0
Do
Read elto : c += 1
If elto <> "EndOfData" Then Redim Preserve arr(c) : arr(c) = elto
Loop Until elto = "EndOfData"
mostrarLista(arr(),"Insertion at Tail:")
Erase arr
Restore datos
c = 0
Do
Read elto : c += 1
If elto <> "EndOfData" Then Redim Preserve arr(c) : arr(c) = elto
Loop Until elto = "EndOfData"
InsertaElto(arr(), 3)
mostrarLista(arr(),"Insertion in Middle:")
Sleep
'the list of datos that will be added to the list
datos:
Data "One", "Two", "Three", "Four", "Five", "Six", "EndOfData"</syntaxhighlight>
{{out}}
<pre>Insertion at Head: Six Five Four Three Two One
Insertion at Tail: One Two Three Four Five Six
Insertion in Middle: One Two Six Four Five Three</pre>
=={{header|Go}}==
Go has nothing like an enforced invariant. Responsibility for preventing circular loops must be shared by all code that modifies the list. Given that, the following declaration ''enables'' code to do that efficiently.
<
int
next, prev *dlNode
Line 1,189 ⟶ 2,326:
members map[*dlNode]int
head, tail **dlNode
}</
Or, just use the [http://golang.org/pkg/container/list/#Element container/list] package:
<
import "fmt"
Line 1,208 ⟶ 2,345:
fmt.Println(e.Value)
}
}</
=={{header|Haskell}}==
For an efficient implementation, see the <code>Data.FDList</code> module provided by [http://hackage.haskell.org/package/liboleg liboleg]. But before using doubly linked lists at all, see [http://stackoverflow.com/questions/1844195/doubly-linked-list-in-a-purely-functional-programming-language this discussion on Stack Overflow].
<
type NodeID = Maybe Rational
Line 1,267 ⟶ 2,404:
fromList = foldr fcons empty
toList = map vNode . M.elems</
An example of use:
<
where l = mcons 'M' n1 n2 x
x = rcons 'Z' $ fcons 'a' $ fcons 'q' $ singleton 'w'
n1 = firstNode x
Just n2 = nextNode x n1</
==Icon and {{header|Unicon}}==
Line 1,283 ⟶ 2,420:
The DoubleList is made from elements of DoubleLink. [[Doubly-Linked List (element)#Icon_and_Unicon]], [[Doubly-Linked List (element insertion)#Icon_and_Unicon]] and [[Doubly-Linked List (traversal)#Icon_and_Unicon]]
<syntaxhighlight lang="unicon">
class DoubleList (item)
Line 1,322 ⟶ 2,459:
self.item := DoubleLink (value)
end
</syntaxhighlight>
An <code>insert_before</code> method was added to the DoubleLink class:
<syntaxhighlight lang="unicon">
# insert given node before this one, losing its existing connections
method insert_before (node)
Line 1,334 ⟶ 2,471:
self.prev_link := node
end
</syntaxhighlight>
To test the double-linked list:
<syntaxhighlight lang="unicon">
procedure main ()
dlist := DoubleList (5)
Line 1,351 ⟶ 2,488:
write (node.value)
end
</syntaxhighlight>
{{out}}
Line 1,416 ⟶ 2,553:
That said, note also that while the native J lists do not support cycles or loops, this high-cost substitute is general enough to support them.
=={{header|Java}}==
The <code>LinkedList<T></code> class is the Doubly-linked list implementation in Java. There are a large number of methods supporting the list. An example is shown below.
<syntaxhighlight lang="java">
import java.util.LinkedList;
public class DoublyLinkedList {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
list.addFirst("Add First");
list.addLast("Add Last 1");
list.addLast("Add Last 2");
list.addLast("Add Last 1");
traverseList(list);
list.removeFirstOccurrence("Add Last 1");
traverseList(list);
}
private static void traverseList(LinkedList<String> list) {
System.out.println("Traverse List:");
for ( int i = 0 ; i < list.size() ; i++ ) {
System.out.printf("Element number %d - Element value = '%s'%n", i, list.get(i));
}
System.out.println();
}
}
</syntaxhighlight>
{{out}}
<pre>
Traverse List:
Element number 0 - Element value = 'Add First'
Element number 1 - Element value = 'Add Last 1'
Element number 2 - Element value = 'Add Last 2'
Element number 3 - Element value = 'Add Last 1'
Traverse List:
Element number 0 - Element value = 'Add First'
Element number 1 - Element value = 'Add Last 2'
Element number 2 - Element value = 'Add Last 1'
</pre>
=={{header|JavaScript}}==
See [[Doubly-Linked List (element)#JavaScript]], [[Doubly-Linked List (element insertion)#JavaScript]] and [[Doubly-Linked List (traversal)#JavaScript]]
=={{header|Julia}}==
Regarding the avoidance or circular loops part of this task, a call to <syntaxhighlight lang="julia">show(DLNode)</syntaxhighlight> reveals that Julia considers all of the nodes of doubly linked lists of this kind to contain circular references to their adjacent nodes.
<syntaxhighlight lang="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
function insertpre(postnode, node)
pred = postnode.pred
postnode.pred = node
node.succ = postnode
node.pred = pred
if pred != nothing
pred.succ = node
end
node
end
function delete(nd)
if nd != nothing
pred = nd.pred
succ = nd.succ
if pred != nothing pred.succ = succ end
if succ != nothing succ.pred = pred end
end
nothing
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)
node4 = DLNode(4)
insertpost(node1, node2)
insertpre(node2, node4)
insertpost(node2, node3)
println("First value is ", first(node1).value, " and last value is ", last(node1).value)
print("From beginning to end: "); printconnected(node1)
delete(node4)
print("From end to beginning post deletion: "); printconnected(node1, fromtail = true)
</syntaxhighlight> {{output}} <pre>
First value is 1 and last value is 3
From beginning to end: 1 -> 4 -> 2 -> 3
From end to beginning post deletion: 3 -> 2 -> 1
</pre>
=={{header|Kotlin}}==
Rather than use the java.util.LinkedList<E> class, we will write our own simple LinkedList<E> class for this 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 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(ll)
}</syntaxhighlight>
{{out}}
<pre>
1 -> 2 -> 3 -> 4
</pre>
=={{header|Lua}}==
<syntaxhighlight lang="lua">-- Doubly Linked List in Lua 6/15/2020 db
-------------------
-- IMPLEMENTATION:
-------------------
local function Node(data)
return { data=data } --implied: return { data=data, prev=nil, next=nil }
end
local List = {
head = nil,
tail = nil,
insertHead = function(self, data)
local node = Node(data)
if (self.head) then
self.head.prev = node
node.next = self.head
self.head = node
else
self.head = node
self.tail = node
end
return node
end,
insertTail = function(self, data)
local node = Node(data)
if self.tail then
self.tail.next = node
node.prev = self.tail
self.tail = node
else
self.head = node
self.tail = node
end
return node
end,
insertBefore = function(self,mark,data)
if (mark) then
local node = Node(data)
if (mark == self.head) then
self.head.next = node
node.next = self.head
self.head = node
else
mark.prev.next = node
node.prev = mark.prev
mark.prev = node
node.next = mark
end
return node
else
-- if no mark given, then insertBefore()==insertHead()
return self:insertHead(data)
end
end,
insertAfter = function(self,mark,data)
if (mark) then
local node = Node(data)
if (mark == self.tail) then
self.tail.next = node
node.prev = self.tail
self.tail = node
else
mark.next.prev = node
node.next = mark.next
mark.next = node
node.prev = mark
end
return node
else
-- if no mark given, then insertAfter()==insertTail()
return self:insertTail(data)
end
end,
values = function(self)
local result, node = {}, self.head
while (node) do result[#result+1], node = node.data, node.next end
return result
end,
}
List.__index = List
setmetatable(List, {__call=function(self) return setmetatable({},self) end })
---------
-- TEST:
---------
local function validate(list, expected)
local values = list:values()
local actual = table.concat(values, ",")
print(actual==expected, actual)
end
local list = List() validate(list, "")
local n1 = list:insertTail(1) validate(list, "1")
local n2 = list:insertTail(2) validate(list, "1,2")
local n3 = list:insertTail(3) validate(list, "1,2,3")
local n4 = list:insertTail(4) validate(list, "1,2,3,4")
local n33 = list:insertAfter(n3, 33) validate(list, "1,2,3,33,4")
local n22 = list:insertAfter(n2, 22) validate(list, "1,2,22,3,33,4")
local n11 = list:insertAfter(n1, 11) validate(list, "1,11,2,22,3,33,4")
local n44 = list:insertAfter(n4, 44) validate(list, "1,11,2,22,3,33,4,44")
local n5 = list:insertTail(5) validate(list, "1,11,2,22,3,33,4,44,5")
local n444 = list:insertBefore(n5, 444) validate(list, "1,11,2,22,3,33,4,44,444,5")
local n55 = list:insertAfter(nil, 55) validate(list, "1,11,2,22,3,33,4,44,444,5,55")
local n0 = list:insertHead(0) validate(list, "0,1,11,2,22,3,33,4,44,444,5,55")
local nm1 = list:insertBefore(nil, -1) validate(list, "-1,0,1,11,2,22,3,33,4,44,444,5,55")
local n111 = list:insertBefore(n2, 111) validate(list, "-1,0,1,11,111,2,22,3,33,4,44,444,5,55")
local n222 = list:insertAfter(n22, 222) validate(list, "-1,0,1,11,111,2,22,222,3,33,4,44,444,5,55")
local n333 = list:insertBefore(n4, 333) validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55")
local n555 = list:insertAfter(n55, 555) validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55,555")</syntaxhighlight>
{{out}}
<pre>true
true 1
true 1,2
true 1,2,3
true 1,2,3,4
true 1,2,3,33,4
true 1,2,22,3,33,4
true 1,11,2,22,3,33,4
true 1,11,2,22,3,33,4,44
true 1,11,2,22,3,33,4,44,5
true 1,11,2,22,3,33,4,44,444,5
true 1,11,2,22,3,33,4,44,444,5,55
true 0,1,11,2,22,3,33,4,44,444,5,55
true -1,0,1,11,2,22,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55,555</pre>
=={{header|M2000 Interpreter}}==
M2000 from 9th version has pointers for groups. Also there is IS operator to check if two pointers are the same. There is no Null pointer except ->0 for groups which decrement object reference counter. So here we use a Null class to define an empty group and then we make a global pointer Null to hold that and compare it with Is operator later.
To check that all works we have to use deconstructor ( Remove {}) which call with Clear statement if only one reference exist. So when we remove from list nodes we check it if destroyed, visually.
We can use ? as print.
There is no garbage collector for pointers for groups, except the reference counter. We can use groups without pointers and we place them in containers, and use indexes or keys for those containers as pointers. Using groups with no pointers make each group unique, so there is no circular dependency between two groups. Containers have garbage collector.
Using pointers inside groups make harder to program.
Groups are two kinds in M2000. The named group (or static in a way) and the float group (unnamed). Pointers for groups are also two types, internal, but we handle it as one type. If we get a pointer to a named group, actually we get a weak reference. If this named grouped erased then weak pointer can't work, we get error. If we get a pointer from an expression we get a real pointer (with counting reference). To get a real pointer from a named group is not possible. We can use A->(namedGroup) to get a pointer of a copy of namedGroup. Then we can use namedGroup=Group(A) to merge a copy of A to namedGroup (same members get new values, new members added, unique members of namedGroup stay as is).
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Form 80, 50
Class Null {}
Global Null->Null()
Class Node {
group pred, succ
dat=0
Remove {
Print "destroyed", .dat
}
class:
module Node {
.pred->Null
.succ->Null
if match("N") Then Read .dat
}
}
Class LList {
Group Head, Tail
Module PushTail(k as pointer) {
if .Tail is Null then {
.Head<=k
.Tail<=k
} else {
n=.Tail
.Tail<=k
k=>pred=n=>pred
n=>pred=k
k=>succ=n
}
}
Function RemoveTail {
n=.Tail
if n is .Head then {
.Head->Null
.Tail->Null
} Else {
.Tail<=n=>succ
.Tail=>pred=n=>pred
n=>pred->Null
}
for n {
.succ->Null
.pred->Null
}
=n
}
Module PushHead(k as pointer) {
if .head is Null then {
.Head<=k
.Tail<=k
} else {
n=.head
.head<=k
k=>succ=n=>succ
n=>succ=k
k=>pred=n
}
}
Function RemoveHead {
n=.Head
if n is .Tail then {
.Head->Null
.Tail->Null
} Else {
.Head<=n=>pred
.Head=>succ=n=>succ
n=>succ->Null
}
for n {
.succ->Null
.pred->Null
}
=n
}
Module RemoveNode(k as pointer) {
pred=k=>pred
succ=k=>succ
if pred is succ then {
if .head is k else Error "Can't remove this node"
k=.RemoveHead()
clear k
} else {
pred=>succ=succ
succ=>pred=pred
}
}
Module InsertAfter(k as pointer, n as pointer) {
pred=k=>pred
n=>pred=pred
n=>succ=k
pred=>succ=n
k=>pred=n
}
Function IsEmpty {
= .Head is null or .tail is null
}
class:
Module LList {
.Head->Null
.Tail->Null
}
}
m->Node(100)
L=LList()
L.PushTail m
If not L.Head is Null then Print L.Head=>dat=100
for i=101 to 103 {
m->Node(i)
L.PushTail m
Print "ok....", i
}
for i=104 to 106 {
m->Node(i)
L.PushHead m
Print "ok....", i
}
Print "Use Head to display from last to first"
m=L.Head
do {
Print m=>dat
m=m=>pred
} Until m is null
Print "ok, now find 3rd and remove it"
m1=L.Head
i=1
Index=3
While i<Index {
if m1 is null then exit
m1=m1=>pred
i++
}
If i<>Index then {
Print "List has less than "; Index;" Items"
} Else {
Print "First add one new node"
newNode->Node(1000)
L.InsertAfter m1, newNode
L.RemoveNode m1
clear m1 ' last time m1 used here
newNode=Null
Print "ok.............."
}
Print "Use Tail to display from first to last"
m=L.Tail
do {
Print m=>dat
m=m=>succ
} Until m is null
useother=True
While not L.IsEmpty(){
For This {
\\ we have to use a temporary variable name, here A
A=If(useother->L.RemoveTail(),L.RemoveHead())
? A=>dat
useother~
\\ now we can try to perform removing
clear A
}
}
Print "list is empty:"; L.IsEmpty()
}
Checkit
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ds = CreateDataStructure["DoublyLinkedList"];
ds["Append", #] & /@ {1, 5, 7, 0, 3, 2};
ds["Prepend", 9];
ds["Append", 4];
(* This is adding at the end and then swap to insert in to the middle: *)
ds["Append", 14]; ds["SwapPart", Round[ds["Length"]/2], ds["Length"]];
ds["Elements"]</syntaxhighlight>
{{out}}
<pre>{9, 1, 5, 14, 0, 3, 2, 4, 7}</pre>
=={{header|Nim}}==
Nim has a doubly linked list already in the lists module of the standard library.
<
List[T] = object
head, tail: Node[T]
Line 1,489 ⟶ 3,150:
l2.prepend newNode("hello")
l2.append newNode("world")
echo l2</
{{out}}
<pre>15 -> 14 -> 12
hello -> world</pre>
=={{header|Oberon-2}}==
<syntaxhighlight lang="oberon2">
IMPORT Basic;
TYPE
Node* = POINTER TO NodeDesc;
NodeDesc* = (* ABSTRACT *) RECORD
prev-,next-: Node;
END;
DLList* = POINTER TO DLListDesc;
DLListDesc* = RECORD
first-,last-: Node;
size-: INTEGER;
END;
</syntaxhighlight>
=={{header|Objeck}}==
<
use Collection;
Line 1,512 ⟶ 3,189:
while(list->Get() <> Nil);
}
}</
=={{header|Oforth}}==
<
DNode method: initialize := next := prev := value ;
Line 1,565 ⟶ 3,242:
dl insertBack("B")
dl head insertAfter(DNode new("C", null , null))
dl ;</
{{out}}
Line 1,573 ⟶ 3,250:
</pre>
=={{header|
See [[Doubly-linked_list/Traversal#Phix|Doubly-linked_list/Traversal]] for a complete example.
=={{header|PicoLisp}}==
Line 1,650 ⟶ 3,264:
| | | ---+---> end
+-----+-----+
<
(de 2list @
(let Prev NIL
Line 1,659 ⟶ 3,273:
(cons L Prev) ) ) )
(setq *DLst (2list 'was 'it 'a 'cat 'I 'saw))</
For output of the example data, see [[Doubly-linked list/Traversal#PicoLisp]].
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
define structure
1 Node,
Line 1,669 ⟶ 3,283:
2 back_pointer handle(Node),
2 fwd_pointer handle(Node);
</syntaxhighlight>
=={{header|PowerShell}}==
Create and populate the list:
<syntaxhighlight lang="powershell">
$list = New-Object -TypeName 'Collections.Generic.LinkedList[PSCustomObject]'
Line 1,682 ⟶ 3,296:
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 1,698 ⟶ 3,312:
</pre>
Insert a value at the head:
<syntaxhighlight lang="powershell">
$list.AddFirst([PSCustomObject]@{ID=123; X=123;Y=123}) | Out-Null
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 1,719 ⟶ 3,333:
</pre>
Insert a value in the middle:
<syntaxhighlight lang="powershell">
$current = $list.First
Line 1,734 ⟶ 3,348:
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 1,752 ⟶ 3,366:
</pre>
Insert a value at the end:
<syntaxhighlight lang="powershell">
$list.AddLast([PSCustomObject]@{ID=789; X=789;Y=789}) | Out-Null
$list
</syntaxhighlight>
{{Out}}
<pre>
Line 1,776 ⟶ 3,390:
=={{header|PureBasic}}==
<
;the list of words that will be added to the list
words:
Line 1,843 ⟶ 3,457:
displayList(a(),"Insertion in Middle: ")
Repeat: Until Inkey() <> ""</
{{out}}
<pre>
Line 1,852 ⟶ 3,466:
=={{header|Python}}==
In the high level language Python, its <code>list</code> native datatype
===collections.deque===
If, as you would expect from a doubly-linked list, you need to efficiently
append items to the start of an ordered collection, use Python’s built-in
[https://docs.python.org/3/library/collections.html#collections.deque collections.deque]
datatype. See [https://wiki.python.org/moin/TimeComplexity TimeComplexity].
<syntaxhighlight lang="python">
from collections import deque
some_list = deque(["a", "b", "c"])
print(some_list)
some_list.appendleft("Z")
print(some_list)
for value in reversed(some_list):
print(value)
</syntaxhighlight>
{{out}}
<pre>
$ python deque_example.py
deque(['a', 'b', 'c'])
deque(['Z', 'a', 'b', 'c'])
c
b
a
Z
</pre>
===Alternative===
Although a <code>deque</code> is preferable in most cases, this implementation gives you the
option to access nodes and slice "views" from a <code>DoublyLinkedList</code>. Things that
<code>collections.deque</code> does not do.
Retrieving an item by it’s index returns the node’s value. Similarly, iterating
a <code>DoublyLinkedList</code> yields a sequence of values, not a sequence of nodes. The
return value of a slice is a <code>DoublyLinkedListView</code>, which shares common nodes with
the original list.
Note that, without a concrete use case, the decision as to which of the special
methods should return a node’s value or a <code>DoublyLinkedListView</code> is somewhat
arbitrary. One might also choose to do away with <code>DoublyLinkedListView</code> and return
a new <code>DoublyLinkedList</code>, accepting that update operations on a derived list could
break links between nodes in other lists.
<syntaxhighlight lang="python">
"""A doubly-linked list. Requires Python >=3.7"""
from __future__ import annotations
import math
from abc import ABC
from collections.abc import MutableSequence
from collections.abc import Sequence
from dataclasses import dataclass
from dataclasses import field
from typing import Any
from typing import Iterable
from typing import Iterator
from typing import Optional
from typing import Union
@dataclass
class Node:
value: Any
prev: Optional[Node] = field(default=None)
next: Optional[Node] = field(default=None)
class BaseDoublyLinkedList(ABC):
def __len__(self):
return self.size
def __iter__(self) -> Iterator[Any]:
node = self.head
cnt = 1
while node is not None and cnt <= self.size:
yield node.value
node = node.next
cnt += 1
def __reversed__(self) -> Iterator[Any]:
node = self.tail
while node is not None:
yield node.value
node = node.prev
def __getitem__(self, key: Union[int, slice]) -> Optional[Any]:
if isinstance(key, int):
node = self._find_node(key)
return node.value
if key.step not in (None, 1):
raise IndexError("can't step more than 1")
start = key.start or 0
node = self._find_node(start)
return DoublyLinkedListView(node, key.stop - start - 1)
def _find_node(self, index) -> Node:
if index > self.size - 1 or index < -self.size:
raise IndexError("list index out of range")
if index >= 0:
node = self.head
for _ in range(index):
node = node.next
else:
node = self.tail
for _ in range(self.size - 1, self.size - abs(index), -1):
node = node.prev
return node
class DoublyLinkedListView(BaseDoublyLinkedList, Sequence):
def __init__(self, node, stop=math.inf):
self.head = node
# Find the tail
cnt = 1
while node is not None and cnt <= stop:
node = node.next
cnt += 1
self.tail = node
self.size = cnt
def __repr__(self):
return f"DoublyLinkedListView([{', '.join(repr(v) for v in self)}])"
def __str__(self):
return repr(self)
class DoublyLinkedList(BaseDoublyLinkedList, MutableSequence):
def __init__(self, iterable: Iterable):
it = iter(iterable)
# Possibly empty iterable
try:
self.head = Node(value=next(it))
self.tail = self.head
self.size = 1
except StopIteration:
self.head = None
self.tail = None
self.size = 0
node = self.head
for val in it:
self.tail = Node(value=val, prev=node)
node.next = self.tail
node = self.tail
self.size += 1
def __repr__(self):
return f"DoublyLinkedList([{', '.join(repr(v) for v in self)}])"
def __str__(self):
return repr(self)
def __setitem__(self, key, value):
node = self._find_node(key)
node.value = value
def __delitem__(self, key) -> None:
node = self._find_node(key)
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
def insert(self, index: int, value: Any) -> None:
node = self._find_node(index)
new_node = Node(value=value, prev=node.prev, next=node)
node.prev.next = new_node
node.prev = node
self.size += 1
def append(self, value: Any) -> None:
tail = self.tail
node = Node(value=value, prev=tail)
tail.next = node
self.tail = node
self.size += 1
def appendleft(self, value: Any) -> None:
head = self.head
node = Node(value=value, next=head)
head.prev = node
self.head = node
self.size += 1
def pop(self) -> Any:
value = self.tail.value
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
return value
def popleft(self) -> Any:
value = self.head.value
self.head = self.head.next
self.head.prev = None
self.size -= 1
return value
</syntaxhighlight>
=={{header|Racket}}==
The following is a port of the Common Lisp solution. The ouput is '(1 2 3 4).
<
#lang racket
(define-struct dlist (head tail) #:mutable #:transparent)
Line 1,917 ⟶ 3,748:
(remove-link dlist bad-link))
(dlist-elements dlist))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
This shows a complete example. (Other entries in the section focus on aspects of this solution.)
<syntaxhighlight lang="raku" line>role DLElem[::T] {
has DLElem[T] $.prev is rw;
has DLElem[T] $.next is rw;
has T $.payload = T;
method pre-insert(T $payload) {
die "Can't insert before beginning" unless $!prev;
my $elem = ::?CLASS.new(:$payload);
$!prev.next = $elem;
$elem.prev = $!prev;
$elem.next = self;
$!prev = $elem;
$elem;
}
method post-insert(T $payload) {
die "Can't insert after end" unless $!next;
my $elem = ::?CLASS.new(:$payload);
$!next.prev = $elem;
$elem.next = $!next;
$elem.prev = self;
$!next = $elem;
$elem;
}
method delete {
die "Can't delete a sentinel" unless $!prev and $!next;
$!next.prev = $!prev;
$!prev.next = $!next; # conveniently returns next element
}
}
role DLList[::DLE] {
has DLE $.first;
has DLE $.last;
submethod BUILD {
$!first = DLE.new;
$!last = DLE.new;
$!first.next = $!last;
$!last.prev = $!first;
}
method list { ($!first.next, *.next ...^ !*.next).map: *.payload }
method reverse { ($!last.prev, *.prev ...^ !*.prev).map: *.payload }
}
class DLElem_Int does DLElem[Int] {}
class DLList_Int does DLList[DLElem_Int] {}
my $dll = DLList_Int.new;
$dll.first.post-insert(1).post-insert(2).post-insert(3);
$dll.first.post-insert(0);
$dll.last.pre-insert(41).pre-insert(40).prev.delete; # (deletes 3)
$dll.last.pre-insert(42);
say $dll.list; # 0 1 2 40 41 42
say $dll.reverse; # 42 41 40 2 1 0</syntaxhighlight>
{{out}}
<pre>0 1 2 40 41 42
42 41 40 2 1 0</pre>
=={{header|REXX}}==
Line 1,946 ⟶ 3,843:
REXX doesn't have linked lists, as there are no pointers (or handles).
<br>However, linked lists can be simulated with lists in REXX.
<
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"
Line 1,989 ⟶ 3,886:
/*──────────────────────────────────────────────────────────────────────────────────────*/
@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</
'''output'''
<pre style="height:30ex;overflow:scroll">
Line 2,025 ⟶ 3,922:
─── showing list ───
Oy! Was it a black cat I saw there, in the shadows, stalking its prey (and next meal).
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Doubly-linked list/Definition
test = [1, 5, 7, 0, 3, 2]
insert(test, 0, 9)
insert(test, len(test), 4)
item = len(test)/2
insert(test, item, 6)
showarray(test)
func showarray(vect)
svect = ""
for n = 1 to len(vect)
svect = svect + vect[n] + " "
next
svect = left(svect, len(svect) - 1)
see svect
</syntaxhighlight>
Output:
<pre>
9 1 5 7 6 0 3 2 4
</pre>
=={{header|Ruby}}==
See [[Doubly-Linked List (element)#Ruby]], [[Doubly-Linked List (element insertion)#Ruby]] and [[Doubly-Linked List (traversal)#Ruby]]
=={{header|Scheme}}==
{{works with|R7RS}}
See also [[#ATS|ATS]].
<syntaxhighlight lang="scheme">(cond-expand
(r7rs)
(chicken (import r7rs)))
(import (scheme base))
(import (scheme write))
(import (scheme case-lambda))
(import (scheme process-context))
;; A doubly-linked list will be represented by a reference to any of
;; its nodes. This is possible because the "root node" is marked as
;; such.
(define-record-type <dllist>
(%dllist root? prev next element)
dllist?
(root? dllist-root?)
(prev dllist-prev %dllist-set-prev!)
(next dllist-next %dllist-set-next!)
(element %dllist-element))
(define (dllist-element node)
;; Get the element in a node. It is an error if the node is the
;; root.
(when (dllist-root? node)
(display "dllist-element of a root node\n" (current-error-port))
(exit 1))
(%dllist-element node))
(define (dllist . elements)
;; Make a doubly-linked list from the given elements.
(list->dllist elements))
(define (make-dllist)
;; Return a node marked as being a root, and which points to itself.
(let ((root (%dllist #t #f #f #f)))
(%dllist-set-prev! root root)
(%dllist-set-next! root root)
root))
(define (dllist-root node)
;; Given a reference to any node of a <dllist>, return a reference
;; to the list's root node.
(if (dllist-root? node)
node
(dllist-root (dllist-prev node))))
(define (dllist-insert-after! node element)
;; Insert an element after the given node, which may be either the
;; root or some other node.
(let* ((next-node (dllist-next node))
(new-node (%dllist #f node next-node element)))
(%dllist-set-next! node new-node)
(%dllist-set-prev! next-node new-node)))
(define (dllist-insert-before! node element)
;; Insert an element before the given node, which may be either the
;; root or some other node.
(let* ((prev-node (dllist-prev node))
(new-node (%dllist #f prev-node node element)))
(%dllist-set-next! prev-node new-node)
(%dllist-set-prev! node new-node)))
(define (dllist-remove! node)
;; Remove a node from a <dllist>. It is an error if the node is the
;; root.
(when (dllist-root? node)
(display "dllist-remove! of a root node\n" (current-error-port))
(exit 1))
(let ((prev (dllist-prev node))
(next (dllist-next node)))
(%dllist-set-next! prev next)
(%dllist-set-prev! next prev)))
(define dllist-make-generator
;; Make a thunk that returns the elements of the list, starting at
;; the root and going in either direction.
(case-lambda
((node) (dllist-make-generator node 1))
((node direction)
(if (negative? direction)
(let ((p (dllist-prev (dllist-root node))))
(lambda ()
(and (not (dllist-root? p))
(let ((element (dllist-element p)))
(set! p (dllist-prev p))
element))))
(let ((p (dllist-next (dllist-root node))))
(lambda ()
(and (not (dllist-root? p))
(let ((element (dllist-element p)))
(set! p (dllist-next p))
element))))))))
(define (list->dllist lst)
;; Make a doubly-linked list from the elements of an ordinary list.
(let loop ((node (make-dllist))
(lst lst))
(if (null? lst)
(dllist-next node)
(begin
(dllist-insert-after! node (car lst))
(loop (dllist-next node) (cdr lst))))))
(define (dllist->list node)
;; Make an ordinary list from the elements of a doubly-linked list.
(let loop ((lst '())
(node (dllist-prev (dllist-root node))))
(if (dllist-root? node)
lst
(loop (cons (dllist-element node) lst) (dllist-prev node)))))
;;;
;;; Some demonstration.
;;;
(define (print-it node)
(let ((gen (dllist-make-generator node)))
(do ((x (gen) (gen)))
((not x))
(display " ")
(write x))
(newline)))
(define dl (dllist 10 20 30 40 50))
(let ((gen (dllist-make-generator dl)))
(display "forwards generator: ")
(do ((x (gen) (gen)))
((not x))
(display " ")
(write x))
(newline))
(let ((gen (dllist-make-generator dl -1)))
(display "backwards generator:")
(do ((x (gen) (gen)))
((not x))
(display " ")
(write x))
(newline))
(display "insertion after the root: ")
(dllist-insert-after! dl 5)
(print-it dl)
(display "insertion before the root:")
(dllist-insert-before! dl 55)
(print-it dl)
(display "insertion after the second element:")
(dllist-insert-after! (dllist-next (dllist-next dl)) 15)
(print-it dl)
(display "insertion before the second from last element:")
(dllist-insert-before! (dllist-prev (dllist-prev dl)) 45)
(print-it dl)
(display "removal of the element 30:")
(let ((node (let loop ((node (dllist-next dl)))
(if (= (dllist-element node) 30)
node
(loop (dllist-next node))))))
(dllist-remove! node))
(print-it dl)
(display "any node can be used for the generator:")
(print-it (dllist-next (dllist-next (dllist-next dl))))
(display "conversion to a list: ")
(display (dllist->list dl))
(newline)
(display "conversion from a list:")
(print-it (list->dllist (list "a" "b" "c")))</syntaxhighlight>
{{out}}
<pre>$ chibi dllist.scm
forwards generator: 10 20 30 40 50
backwards generator: 50 40 30 20 10
insertion after the root: 5 10 20 30 40 50
insertion before the root: 5 10 20 30 40 50 55
insertion after the second element: 5 10 15 20 30 40 50 55
insertion before the second from last element: 5 10 15 20 30 40 45 50 55
removal of the element 30: 5 10 15 20 40 45 50 55
any node can be used for the generator: 5 10 15 20 40 45 50 55
conversion to a list: (5 10 15 20 40 45 50 55)
conversion from a list: "a" "b" "c"</pre>
=={{header|Swift}}==
<syntaxhighlight lang="Swift">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
class Node<T> {
var value: T
fileprivate var prev: NodePtr<T>?
fileprivate var next: NodePtr<T>?
init(value: T, prev: NodePtr<T>? = nil, next: NodePtr<T>? = nil) {
self.value = value
self.prev = prev
self.next = next
}
}
struct DoublyLinkedList<T> {
fileprivate var head: NodePtr<T>?
fileprivate var tail: NodePtr<T>?
@discardableResult
mutating func insert(_ val: T, at: InsertLoc<T> = .last) -> Node<T> {
let node = NodePtr<T>.allocate(capacity: 1)
node.initialize(to: Node(value: val))
if head == nil && tail == nil {
head = node
tail = node
return node.pointee
}
switch at {
case .first:
node.pointee.next = head
head?.pointee.prev = node
head = node
case .last:
node.pointee.prev = tail
tail?.pointee.next = node
tail = node
case let .after(insertNode):
var n = head
while n != nil {
if n!.pointee !== insertNode {
n = n?.pointee.next
continue
}
node.pointee.prev = n
node.pointee.next = n!.pointee.next
n!.pointee.next = node
if n == tail {
tail = node
}
break
}
}
return node.pointee
}
@discardableResult
mutating func remove(_ node: Node<T>) -> T? {
var n = head
while n != nil {
if n!.pointee !== node {
n = n?.pointee.next
continue
}
if n == head {
n?.pointee.next?.pointee.prev = nil
head = n?.pointee.next
} else if n == tail {
n?.pointee.prev?.pointee.next = nil
tail = n?.pointee.prev
} else {
n?.pointee.prev?.pointee.next = n?.pointee.next
n?.pointee.next?.pointee.prev = n?.pointee.prev
}
break
}
if n == nil {
return nil
}
defer {
n?.deinitialize(count: 1)
n?.deallocate()
}
return n?.pointee.value
}
enum InsertLoc<T> {
case first
case last
case after(Node<T>)
}
}
extension DoublyLinkedList: CustomStringConvertible {
var description: String {
var res = "["
var node = head
while node != nil {
res += "\(node!.pointee.value), "
node = node?.pointee.next
}
return (res.count > 1 ? String(res.dropLast(2)) : res) + "]"
}
}
var list = DoublyLinkedList<Int>()
var node: Node<Int>!
for i in 0..<10 {
let insertedNode = list.insert(i)
if i == 5 {
node = insertedNode
}
}
print(list)
list.insert(100, at: .after(node!))
print(list)
list.remove(node!)
print(list)</syntaxhighlight>
{{out}}
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 100, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 100, 6, 7, 8, 9]</pre>
{{works with|Swift|5.8}}
This version uses classes instead of structs and unsafe pointers. It thus obviates the need for explicit memory management and i, I think, a little cleaner.
Loops are avoided by handling the management of all links within the class itself.
<syntaxhighlight lang="Swift">public class DoublyLinkedList<Element>
{
public class Entry
{
// Each entry owns the next entry
public fileprivate(set) weak var prev: Entry?
public fileprivate(set) var next: Entry?
public let item: Element
init(prev: Entry? = nil, next: Entry? = nil, item: Element)
{
self.prev = prev
self.next = next
self.item = item
}
}
public init(){}
public private(set) var headEntry: Entry? = nil
public private(set) var tailEntry: Entry? = nil
public var head: Element? { headEntry?.item }
public var tail: Element? { tailEntry?.item }
public func append(item: Element)
{
let newEntry = Entry(prev: tailEntry, item: item)
if let tailEntry
{
tailEntry.next = newEntry
}
else
{
headEntry = newEntry
}
tailEntry = newEntry
}
public func prepend(item: Element)
{
let newEntry = Entry(next: headEntry, item: item)
if let headEntry
{
headEntry.prev = newEntry
}
else
{
tailEntry = newEntry
}
headEntry = newEntry
}
public func insert(item: Element, before: Entry)
{
let newEntry = Entry(next: before, item: item)
if let previous = before.prev
{
newEntry.prev = previous
previous.next = newEntry
}
else
{
headEntry = newEntry
}
newEntry.next = before
}
public func insert(item: Element, after: Entry)
{
let newEntry = Entry(prev: after, item: item)
if let next = after.next
{
newEntry.next = next
next.prev = newEntry
}
else
{
tailEntry = newEntry
}
after.next = newEntry
}
@discardableResult public func remove(entry: Entry) -> Element
{
if let prevEntry = entry.prev
{
prevEntry.next = entry.next
}
else
{
headEntry = entry.next
}
if let nextEntry = entry.next
{
nextEntry.prev = entry.prev
}
else
{
tailEntry = entry.prev
}
entry.prev = nil
entry.next = nil
return entry.item
}
}
extension DoublyLinkedList: CustomStringConvertible where Element: CustomStringConvertible
{
public var description: String
{
var array: [Element] = []
var currentEntry = headEntry
while let thisEntry = currentEntry
{
array.append(thisEntry.item)
currentEntry = thisEntry.next
}
return "[" + array.map({ $0.description }).joined(separator: ", ") + "]"
}
}
let list = DoublyLinkedList<Int>()
for i in 0 ... 5
{
list.append(item: i)
}
for i in 10 ... 15
{
list.prepend(item: i)
}
if let insertPoint = list.headEntry?.next?.next
{
list.insert(item: 99, after: insertPoint)
}
print("\(list)")
if let removePoint = list.headEntry?.next?.next?.next
{
let item = list.remove(entry: removePoint)
}
print("\(list)")
</syntaxhighlight>
{{out}}
<pre>
[15, 14, 13, 99, 12, 11, 10, 0, 1, 2, 3, 4, 5]
[15, 14, 13, 12, 11, 10, 0, 1, 2, 3, 4, 5]
</pre>
=={{header|Tcl}}==
Line 2,045 ⟶ 4,472:
See also [[Doubly-Linked List (element)]] for a TclOO-based version.
<
proc dl {_name cmd {where error} {value ""}} {
upvar 1 $_name N
Line 2,115 ⟶ 4,542:
}
}
}</
<
set testcases [split {
dl D insert head foo
Line 2,141 ⟶ 4,568:
if {[lsearch $argv -p] >= 0} {parray D}
}
}</
=={{header|Visual Basic .NET}}==
<
Private m_Head As Node(Of T)
Private m_Tail As Node(Of T)
Line 2,272 ⟶ 4,699:
End Sub
End Class</
=={{header|Wren}}==
{{libheader|Wren-llist}}
The DLinkedList class in the above module is a generic doubly-linked list and is implemented in such a way that circular loops are not possible. We therefore use it here.
<syntaxhighlight lang="wren">import "./llist" for DLinkedList
var dll = DLinkedList.new()
for (i in 1..3) dll.add(i)
System.print(dll)
for (i in 1..3) dll.remove(i)
System.print(dll)</syntaxhighlight>
{{out}}
<pre>
[1 <-> 2 <-> 3]
[]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">
def \Node\ Prev, Data, Next; \Element (Node) definition
int Head(3), Tail(3); \Doubly linked list definition
[Head(Next):= Tail;
Tail(Prev):= Head;
]</syntaxhighlight>
=={{header|zkl}}==
<
fcn init(_value,_prev=Void,_next=Void)
{ var value=_value, prev=_prev, next=_next; }
Line 2,300 ⟶ 4,752:
}.fp(Ref(self),dir))
}
}</
<
a.append("c").append("d");
a.last().append("e");
a.last().first().append("b");
foreach n in (a){ print(n," ") } println();
foreach n in (a.last().walker(False)){ print(n," ") } println();</
{{out}}
<pre>
| |||