Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Ring}}: Remove vanity tags) |
No edit summary |
||
Line 1,495: | Line 1,495: | ||
1 -> 2 -> 3 -> 4 |
1 -> 2 -> 3 -> 4 |
||
</pre> |
</pre> |
||
=={{header|M2000 Interpreter}}== |
|||
<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=.RemoveJead() |
|||
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 m 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 |
|||
</lang> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |