Class: LinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/linkedlist.rb

Overview

A simple implementation of doubly linked list data type

Autor

Thiago Gonzaga

License

MIT

Instance Method Summary collapse

Constructor Details

#initialize(length = 0, item = nil) ⇒ LinkedList

Creates a new instance of a list

  • length

  • initial data



13
14
15
16
17
18
19
20
21
 
# File 'lib/linkedlist.rb', line 13

def initialize(length=0, item=nil)
  @tail = nil
  @head = nil
  @length = 0
  for i in (1..length)
    self << item
    yield(item) if block_given?
  end
end

Instance Method Details

#<<(info) ⇒ Object 



185
186
187
 
# File 'lib/linkedlist.rb', line 185

def <<(info)
  add(info)
end

#[](index) ⇒ Object 



170
171
172
173
 
# File 'lib/linkedlist.rb', line 170

def [](index)
  i = get(index)
  i.info if !i.nil?
end

#[]=(index, info) ⇒ Object 



175
176
177
178
179
180
181
182
183
 
# File 'lib/linkedlist.rb', line 175

def []=(index, info)
  i = get(index)
  if !i.nil?
    i.info = info
  else
    insert_at(index, info)
  end
  info
end

#add(info) ⇒ Object

insert an item on end



56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/linkedlist.rb', line 56

def add(info)
  _new = Node.new(info, previous: @tail)
  if @head.nil?
    @head = _new
    @tail = @head
  else
    @tail.next = _new
    @tail = _new
  end
  @length += 1
  self
end

#clear ⇒ Object

remove all itens



161
162
163
164
165
166
167
168
 
# File 'lib/linkedlist.rb', line 161

def clear
  @length = 0
  @head.next.previous = nil if !@head.next.nil?
  @tail.previous.next = nil if !@head.previous.nil?
  @head = nil
  @tail = nil
  self
end

#deq ⇒ Object

dequeue the first item



51
52
53
 
# File 'lib/linkedlist.rb', line 51

def deq
  remove(0)
end

#each ⇒ Object

go forward



120
121
122
123
124
125
126
 
# File 'lib/linkedlist.rb', line 120

def each
  curr = @head
  while !curr.nil?
    yield(curr.info) if block_given?
    curr = curr.next
  end
end

#empty? ⇒ Boolean

verify if the list is empty

Returns:

  • (Boolean) 


156
157
158
 
# File 'lib/linkedlist.rb', line 156

def empty?
  @length == 0
end

#enq(info) ⇒ Object

enqueue an item on end



46
47
48
 
# File 'lib/linkedlist.rb', line 46

def enq(info)
  add(info)
end

#first ⇒ Object

the first item of the list



110
111
112
 
# File 'lib/linkedlist.rb', line 110

def first
  @head.info
end

#get(index) ⇒ Object

get data from it index starting at 0



89
90
91
92
 
# File 'lib/linkedlist.rb', line 89

def get(index)
  dir = index > @length/2? -1: 1
  go(dir: dir, index: index)
end

#insert_at(index, info) ⇒ Object

insert at a certain position



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/linkedlist.rb', line 70

def insert_at(index, info)
  curr = get(index)
  if !curr.nil?
    _new = Node.new(info, previous: curr.previous, _next: curr)
    curr.previous.next = _new if !curr.previous.nil?
    curr.previous = _new
    @head =  _new if @head == curr
    @tail = _new if @tail == curr
    @length += 1
  else
    for i in (@length...index)
      self << nil
    end
    add(info)
  end
  self
end

#last ⇒ Object

the last item of the list



115
116
117
 
# File 'lib/linkedlist.rb', line 115

def last
  @tail.info
end

#length ⇒ Object

retorna o tamanho da lista



24
25
26
 
# File 'lib/linkedlist.rb', line 24

def length
  @length
end

#pop ⇒ Object

remove the last item



41
42
43
 
# File 'lib/linkedlist.rb', line 41

def pop
  remove(@length - 1)
end

#push(info) ⇒ Object

Insert data on end

alias

add()



36
37
38
 
# File 'lib/linkedlist.rb', line 36

def push(info)
  add(info)
end

#remove(index) ⇒ Object

remove date by it index



95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/linkedlist.rb', line 95

def remove(index)
  dir = index > @length/2? -1: 1
  curr = go(dir: dir, index: index)
  if !curr.nil?
    curr.previous.next = curr.next if !curr.previous.nil?
    curr.next.previous = curr.previous if !curr.next.nil?
    @tail = curr.previous if curr == @tail
    @head = curr.next if curr == @head
    curr.previous, curr.next = nil, nil
    @length -= 1
  end
  curr.info if !curr.nil?
end

#reverse_each ⇒ Object

go backwards



129
130
131
132
133
134
135
 
# File 'lib/linkedlist.rb', line 129

def reverse_each
  curr = @tail
  while !curr.nil?
    yield(curr.info) if block_given?
    curr = curr.previous
  end
end

#size ⇒ Object

Alias for length

alias

length()



30
31
32
 
# File 'lib/linkedlist.rb', line 30

def size
  @length
end

#to_a ⇒ Object

Convert to an array



149
150
151
152
153
 
# File 'lib/linkedlist.rb', line 149

def to_a
  arr = []
  each {|valor| arr << valor}
  arr
end

#to_s ⇒ Object

Convert to a string



138
139
140
141
142
143
144
145
146
 
# File 'lib/linkedlist.rb', line 138

def to_s
  s = "["
  curr = @head
  while !curr.nil?
    s << curr.to_s
    curr = curr.next
  end
  s << "]"
end