Doubly-linked list/Definition: Difference between revisions

==Icon and {{header|Unicon}}==

Uses Unicon's classes.

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]]

<lang Unicon>

class DoubleList (item)

method head ()

node := item

every (node := node.traverse_backwards ()) # move to start of list

return node

end

method tail ()

node := item

every (node := node.traverse_forwards ()) # move to end of list

return node

end

method insert_at_head (value)

head().insert_before (DoubleLink(value))

end

method insert_at_tail (value)

tail().insert_after (DoubleLink (value))

end

# insert a node for new_value after that for target_value,

# i.e. in the middle of the list

method insert_after (target_value, new_value)

node := head ()

every node := head().traverse_forwards () do

if (node.value = target_value)

then {

node.insert_after (DoubleLink (new_value))

break

}

end

# constructor initiates a list making a node from given value

initially (value)

self.item := DoubleLink (value)

end

</lang>

An <code>insert_before</code> method was added to the DoubleLink class:

<lang Unicon>

# insert given node before this one, losing its existing connections

method insert_before (node)

if (\prev_link) then prev_link.next_link := node

node.prev_link := prev_link

node.next_link := self

self.prev_link := node

end

</lang>

To test the double-linked list:

<lang Unicon>

procedure main ()

dlist := DoubleList (5)

every i := 4 to 1 by -1 do

dlist.insert_at_head (i)

every i := 6 to 10 do

dlist.insert_at_tail (i)

dlist.insert_after (3, 11)

every node := dlist.head().traverse_forwards () do

write (node.value)

end

</lang>

Output:

<pre>

1

2

3

11

4

5

6

7

8

9

10

</pre>