Question | Click to View Answer |
A linked list maintains a relative positioning of items. Each node in the list knows the next node in the list. The first node is called the "head" of the linked list. Create a n3 = Node.new(data: :happy)
n2 = Node.new(data: 99, next_node: n3)
n1 = Node.new(data: "cat", next_node: n2)
list = LinkedList.new(head: n1)
This code will construct the |
The class Node
attr_accessor :data, :next_node
def initialize(data:, next_node: nil)
@data = data
@next_node = next_node
end
end
class LinkedList
attr_reader :head
def initialize(head:)
@head = head
end
end
|
Add a |
The class LinkedList
attr_reader :head
def initialize(head:)
@head = head
end
def size
current = head
count = 0
until current.nil?
count += 1
current = current.next_node
end
count
end
end
n3 = Node.new(data: :happy)
n2 = Node.new(data: 99, next_node: n3)
n1 = Node.new(data: "cat", next_node: n2)
list = LinkedList.new(head: n1)
p list.size # => 3
|
Add a |
The def pretty_print
current = head
result = []
until current.nil?
result.push(current.data)
current = current.next_node
end
result
end
|
Add an |
The def include?(data)
current = head
until current.nil?
return true if current.data == data
current = current.next_node
end
false
end
# using the same list from earlier problems
list.include?(:happy) # => true
list.include?(99) # => true
list.include?("cat") # => true
list.include?("fat") # => false
|
Add a |
Removing an item from a linked list is a bit trickier because the def remove(data)
current = head
previous = nil
until current.nil?
if current.data == data
if previous.nil?
@head = current.next_node
return
end
previous.next_node = current.next_node
return
end
previous = current
current = current.next_node
end
false
end
|
Add an |
The def add(node)
node.next_node = head
@head = node
end
|
Add a |
This video provides an awesome tutorial on how to reverse a linked list. At each step of the iteration, we need to keep track of the current node, the previous node, and the next node. During each step of the iteration, the def reverse
current = head
previous = nil
next_node = nil
until current.nil?
next_node = current.next_node
current.next_node = previous
previous = current
current = next_node
end
@head = previous
end
|