class List[E]
special IndexedCollection[E]
# Access
- redef meth [](index) do return get_node(index).item
+ redef fun [](index) do return get_node(index).item
- redef meth []=(index, item) do get_node(index).item = item
+ redef fun []=(index, item) do get_node(index).item = item
# O(1)
- redef meth first do return _head.item
+ redef fun first do return _head.item
# O(1)
- redef meth first=(e) do _head.item = e
+ redef fun first=(e) do _head.item = e
# O(1)
- redef meth last do return _tail.item
+ redef fun last do return _tail.item
# O(1)
- redef meth last=(e) do _tail.item = e
+ redef fun last=(e) do _tail.item = e
# Queries
# O(1)
- redef meth is_empty do return _head == null
+ redef fun is_empty do return _head == null
# O(n)
- redef meth length
+ redef fun length
do
var l = 0
var t = _head
end
# O(n)
- redef meth has(e) do return search_node_after(e, _head) != null
+ redef fun has(e) do return search_node_after(e, _head) != null
- redef meth has_only(e)
+ redef fun has_only(e)
do
var node = _head
while node != null do
return true
end
- redef meth count(e)
+ redef fun count(e)
do
var nb = 0
var node = _head
return nb
end
- redef meth has_key(index) do return get_node(index) != null
+ redef fun has_key(index) do return get_node(index) != null
# Add elements
# O(1)
- redef meth push(e)
+ redef fun push(e)
do
var node = new ListNode[E](e)
if _tail == null then
end
# O(1)
- redef meth unshift(e)
+ redef fun unshift(e)
do
var node = new ListNode[E](e)
if _head == null then
# Append `l' to `self' but clear `l'.
##
# O(1)
- meth link(l: List[E])
+ fun link(l: List[E])
do
if _tail == null then
_head = l._head
# Remove elements
# O(1)
- redef meth pop
+ redef fun pop
do
var node = _tail
_tail = node.prev
end
# O(1)
- redef meth shift
+ redef fun shift
do
var node = _head
_head = node.next
return node.item
end
- redef meth remove(e)
+ redef fun remove(e)
do
var node = search_node_after(e, _head)
if node != null then remove_node(node)
end
- redef meth remove_at(i)
+ redef fun remove_at(i)
do
var node = get_node(i)
if node != null then remove_node(node)
end
- redef meth clear
+ redef fun clear
do
_head = null
_tail = null
end
- redef meth iterator: ListIterator[E] do return new ListIterator[E](_head)
+ redef fun iterator: ListIterator[E] do return new ListIterator[E](_head)
# Build an empty list.
init do end
init from(coll: Collection[E]) do append(coll)
# The first node of the list
- attr _head: nullable ListNode[E]
+ var _head: nullable ListNode[E]
# The last node of the list
- attr _tail: nullable ListNode[E]
+ var _tail: nullable ListNode[E]
# Get the `i'th node. get `null' otherwise.
- private meth get_node(i: Int): nullable ListNode[E]
+ private fun get_node(i: Int): nullable ListNode[E]
do
var n = _head
if i < 0 then
end
# get the first node that contains e after 'after', null otherwise
- private meth search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
+ private fun search_node_after(e: E, after: nullable ListNode[E]): nullable ListNode[E]
do
var n = after
while n != null and n.item != e do n = n.next
end
# Remove the node (ie. atach prev and next)
- private meth remove_node(node: ListNode[E])
+ private fun remove_node(node: ListNode[E])
do
if node.prev == null then
_head = node.next
end
end
- private meth insert_before(element: E, node: ListNode[E])
+ private fun insert_before(element: E, node: ListNode[E])
do
var nnode = new ListNode[E](element)
var prev = node.prev
# This is the iterator class of List
class ListIterator[E]
special IndexedIterator[E]
- redef meth item do return _node.item
+ redef fun item do return _node.item
- # redef meth item=(e) do _node.item = e
+ # redef fun item=(e) do _node.item = e
- redef meth is_ok do return not _node == null
+ redef fun is_ok do return not _node == null
- redef meth next
+ redef fun next
do
_node = _node.next
_index += 1
end
# The current node of the list
- attr _node: nullable ListNode[E]
+ var _node: nullable ListNode[E]
# The index of the current node
- redef readable attr _index: Int
+ redef readable var _index: Int
end
# Linked nodes that constitute a linked list.
end
# The next node.
- readable writable attr _next: nullable ListNode[E]
+ readable writable var _next: nullable ListNode[E]
# The previous node.
- readable writable attr _prev: nullable ListNode[E]
+ readable writable var _prev: nullable ListNode[E]
end