@jaywengrow
A Common-Sense Guide to Data Structures and Algorithms - insertion at wrong index (page 140)
I tested the example of a linked list insertion method on page 140 (2017 edition):
class Node
attr_accessor :data, :next_node
def initialize(data)
@data = data
end
end
class LinkedList
attr_accessor :first_node
# rest of code omitted here...
def insert_at_index(index, value)
current_node = first_node
current_index = 0
# First, we find the index immediately before where the new node will go:
while current_index < index do
current_node = current_node.next_node
current_index += 1
end
# We create the new node:
new_node = Node.new(value)
new_node.next_node = current_node.next_node
# We modify the link of the previous node to point to our new node:
current_node.next_node = new_node
end
end
The method seems to be inserting a new node after the provided index, e.g.
node_1 = Node.new("once")
node_2 = Node.new("upon")
node_1.next_node = node_2
node_3 = Node.new("a")
node_2.next_node = node_3
node_4 = Node.new("time")
node_3.next_node = node_4
list = LinkedList.new(node_1) # 0. "once" 1. "upon" 2. "a" 3. "time"
list.insert_at_index(3, "beautiful") # 0 "once" 1. "upon" 2. "a" 3. "time" 4. "beautiful"
Shouldn’t the while loop be while current_index < index-1 instead?
Thank you for the brilliant book anyway @jaywengrow . It’s a great learning resource!