Doubly-linked list/Traversal: Difference between revisions
Content added Content deleted
(Nimrod -> Nim) |
m (Sort languages in alphabetical order) |
||
| Line 397: | Line 397: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
see [[Doubly-linked list/Definition#Fortran]] |
see [[Doubly-linked list/Definition#Fortran]] |
||
=={{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. |
|||
<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("") |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
<nil> |
|||
[A B] |
|||
[A C B] |
|||
From tail: B C A |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
<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)</lang> |
|||
==Icon and {{header|Unicon}}== |
==Icon and {{header|Unicon}}== |
||
| Line 518: | Line 613: | ||
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|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. |
|||
<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("") |
|||
}</lang> |
|||
Output: |
|||
<pre> |
|||
<nil> |
|||
[A B] |
|||
[A C B] |
|||
From tail: B C A |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
<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)</lang> |
|||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||