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