Class: LinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/shea-linked_list/linked_list.rb

Overview

A linear collection of Node data elements that “point” to the next Node by means of a pointer

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ LinkedList

Returns a new instance of LinkedList.



9
10
11
12
 
# File 'lib/shea-linked_list/linked_list.rb', line 9

def initialize
  @head = nil
  @tail = nil
end

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



7
8
9
 
# File 'lib/shea-linked_list/linked_list.rb', line 7

def head
  @head
end

#tail ⇒ Object

Returns the value of attribute tail.



7
8
9
 
# File 'lib/shea-linked_list/linked_list.rb', line 7

def tail
  @tail
end

Instance Method Details

#append(value) ⇒ Object

adds a new node containing value to the end of the list



15
16
17
18
19
20
 
# File 'lib/shea-linked_list/linked_list.rb', line 15

def append(value)
  node = Node.new(value)
  @head ||= node
  @tail.next_node = node if @tail
  @tail = node
end

#at(index) ⇒ Object

returns the node at the given index



44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/shea-linked_list/linked_list.rb', line 44

def at(index)
  return nil if index.negative? || index > size - 1

  i = 0
  node = @head
  while i < index
    i += 1
    node = node.next_node
  end
  node
end

#contains?(value) ⇒ Boolean

returns true if the passed in value is in the list and otherwise returns false.

Returns:

  • (Boolean) 


64
65
66
67
68
69
70
71
72
 
# File 'lib/shea-linked_list/linked_list.rb', line 64

def contains?(value)
  current_node = @head
  while current_node
    return true if current_node.value == value

    current_node = current_node.next_node
  end
  false
end

#find(value) ⇒ Object

returns the index of the node containing value, or nil if not found.



75
76
77
78
79
80
81
82
83
84
 
# File 'lib/shea-linked_list/linked_list.rb', line 75

def find(value)
  current_node = @head
  i = 0
  while current_node
    return i if current_node.value == value

    i += 1
    current_node = current_node.next_node
  end
end

#insert_at(value, index) ⇒ Object

inserts a new node with the provided value at the given index



87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/shea-linked_list/linked_list.rb', line 87

def insert_at(value, index)
  case index
  when 0 then prepend(value)
  when size - 1 then append(value)
  else
    next_node = at(index)
    node = Node.new(value, next_node)
    prev_node = at(index - 1)
    prev_node.next_node = node
  end
end

#pop ⇒ Object

removes the last element from the list



57
58
59
60
61
 
# File 'lib/shea-linked_list/linked_list.rb', line 57

def pop
  new_tail = at(size - 2)
  new_tail.next_node = nil if new_tail
  @tail = new_tail
end

#prepend(value) ⇒ Object

adds a new node containing value to the start of the list



23
24
25
26
27
28
 
# File 'lib/shea-linked_list/linked_list.rb', line 23

def prepend(value)
  next_node = @head if @head
  node = Node.new(value, next_node)
  @tail ||= node
  @head = node
end

#remove_at(index) ⇒ Object

removes the node at the given index



100
101
102
103
104
105
106
107
108
 
# File 'lib/shea-linked_list/linked_list.rb', line 100

def remove_at(index)
  prev_node = at(index - 1)
  next_node = at(index + 1)
  if index.zero?
    @head = next_node
  else
    prev_node.next_node = next_node
  end
end

#size ⇒ Object

returns the total number of nodes in the list



31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/shea-linked_list/linked_list.rb', line 31

def size
  size = 0
  if @head
    current_node = @head
    while current_node
      size += 1
      current_node = current_node.next_node
    end
  end
  size
end

#to_s ⇒ Object

the format should be: ( value ) -> ( value ) -> ( value ) -> nil



111
112
113
114
115
116
117
118
119
 
# File 'lib/shea-linked_list/linked_list.rb', line 111

def to_s
  output = +''
  current_node = @head
  while current_node
    output << "( #{current_node.value} ) -> "
    current_node = current_node.next_node
  end
  output << 'nil'
end