Class: DSA::List

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/DSA/list.rb

Overview

doubly linked list

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ List

Returns a new instance of List.



59
60
61
62
63
64
65
 
# 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

Instance Attribute Details

#head ⇒ Object (readonly)

head and tail are two empty guards



56
57
58
 
# File 'lib/DSA/list.rb', line 56

def head
  @head
end

#length ⇒ Object (readonly)

Returns the value of attribute length.



55
56
57
 
# File 'lib/DSA/list.rb', line 55

def length
  @length
end

#tail ⇒ Object (readonly)

head and tail are two empty guards



56
57
58
 
# File 'lib/DSA/list.rb', line 56

def tail
  @tail
end

Instance Method Details

#[](index) ⇒ Object

access an element at position index(0 based), linear time cost, use with caution



112
113
114
 
# File 'lib/DSA/list.rb', line 112

def [](index)
  get_node(index).element
end

#begin_iterator ⇒ Object

an iterator starting from head



126
127
128
 
# File 'lib/DSA/list.rb', line 126

def begin_iterator
  ListIterator.new @head, self
end

#each ⇒ Object 



116
117
118
119
120
121
122
123
 
# 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? ⇒ Boolean

Returns:

  • (Boolean) 


93
94
95
 
# File 'lib/DSA/list.rb', line 93

def empty?
  @length == 0
end

#end_iterator ⇒ Object

an iterator starting from end



131
132
133
 
# File 'lib/DSA/list.rb', line 131

def end_iterator
  ListIterator.new @tail, self
end

#first ⇒ Object 



85
86
87
 
# File 'lib/DSA/list.rb', line 85

def first
  self[0]
end

#insert_at(index, e) ⇒ Object

insert an element at position index(0 based), linear time cost, use with caution, iterator preferred



98
99
100
101
102
 
# 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) ⇒ Object

the following methods are used to process nodes, user usually does not need to use them insert node between two nodes



137
138
139
140
141
142
143
 
# 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 ⇒ Object 



89
90
91
 
# File 'lib/DSA/list.rb', line 89

def last
  self[@length-1]
end

#pop ⇒ Object 



71
72
73
74
 
# File 'lib/DSA/list.rb', line 71

def pop
  node = remove_node @tail.prev
  node.element
end

#push(e) ⇒ Object 



67
68
69
 
# File 'lib/DSA/list.rb', line 67

def push(e)
  insert_node_between @tail.prev, @tail, ListNode.new(e)
end

#remove_at(index) ⇒ Object

remove an element at position index(0 based), linear time cost, use with caution, iterator preferred



105
106
107
108
109
 
# File 'lib/DSA/list.rb', line 105

def remove_at(index)
  node = get_node index
  remove_node node
  node.element
end

#remove_node(node) ⇒ Object

remove a node

Raises:



146
147
148
149
150
151
152
153
154
 
# 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 ⇒ Object 



80
81
82
83
 
# File 'lib/DSA/list.rb', line 80

def shift
  node = remove_node @head.next
  node.element
end

#unshift(e) ⇒ Object 



76
77
78
 
# File 'lib/DSA/list.rb', line 76

def unshift(e)
  insert_node_between @head, @head.next, ListNode.new(e)
end