class DSA::List
doubly linked list
Attributes
head[R]
length[R]
tail[R]
Public Class Methods
new()
click to toggle source
# File lib/DSA/list.rb, line 59 def initialize @head = ListNode.new nil @tail = ListNode.new nil @head.next = @tail @tail.prev = @head @length = 0 end
Public Instance Methods
[](index)
click to toggle source
access an element at position index(0 based), linear time cost, use with caution
# File lib/DSA/list.rb, line 112 def [](index) get_node(index).element end
begin_iterator()
click to toggle source
an iterator starting from head
# File lib/DSA/list.rb, line 126 def begin_iterator ListIterator.new @head, self end
each() { |element| ... }
click to toggle source
# File lib/DSA/list.rb, line 116 def each node = @head.next while 1 break if node == @tail yield node.element node = node.next end end
empty?()
click to toggle source
# File lib/DSA/list.rb, line 93 def empty? @length == 0 end
end_iterator()
click to toggle source
an iterator starting from end
# File lib/DSA/list.rb, line 131 def end_iterator ListIterator.new @tail, self end
first()
click to toggle source
# File lib/DSA/list.rb, line 85 def first self[0] end
insert_at(index, e)
click to toggle source
insert an element at position index(0 based), linear time cost, use with caution, iterator preferred
# File lib/DSA/list.rb, line 98 def insert_at(index, e) push e if index > @length - 1 node = get_node index insert_node_between node.prev, node, ListNode.new(e) end
insert_node_between(a, b, new_one)
click to toggle source
the following methods are used to process nodes, user usually does not need to use them insert node between two nodes
# File lib/DSA/list.rb, line 137 def insert_node_between(a, b, new_one) a.next = new_one new_one.prev = a new_one.next = b b.prev = new_one @length += 1 end
last()
click to toggle source
# File lib/DSA/list.rb, line 89 def last self[@length-1] end
pop()
click to toggle source
# File lib/DSA/list.rb, line 71 def pop node = remove_node @tail.prev node.element end
push(e)
click to toggle source
# File lib/DSA/list.rb, line 67 def push(e) insert_node_between @tail.prev, @tail, ListNode.new(e) end
remove_at(index)
click to toggle source
remove an element at position index(0 based), linear time cost, use with caution, iterator preferred
# File lib/DSA/list.rb, line 105 def remove_at(index) node = get_node index remove_node node node.element end
remove_node(node)
click to toggle source
remove a node
# File lib/DSA/list.rb, line 146 def remove_node(node) raise( ListRemovalError, 'List is empty' ) if @length == 0 before = node.prev after = node.next before.next = after after.prev = before @length -= 1 node end
shift()
click to toggle source
# File lib/DSA/list.rb, line 80 def shift node = remove_node @head.next node.element end
unshift(e)
click to toggle source
# File lib/DSA/list.rb, line 76 def unshift(e) insert_node_between @head, @head.next, ListNode.new(e) end
Private Instance Methods
get_node(index)
click to toggle source
# File lib/DSA/list.rb, line 157 def get_node(index) index += @length if index < 0 raise(ListIndexError, 'Index out of bound: ' + index.to_s) if index > @length - 1 || index < 0 if index > @length / 2 node = @tail.prev current_index = @length - 1 while 1 return node if index == current_index node = node.prev current_index -= 1 end else node = @head.next current_index = 0 while 1 return node if index == current_index node = node.next current_index += 1 end end end