hayashi

hayashi

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow. Linked List Insertion method

@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!

First Post!

jaywengrow

jaywengrow

Author of A Common-Sense Guide to Data Structures and Algorithms

Thanks for this! You are correct, and this has indeed been fixed in the Second Edition of the book.

Popular Pragmatic Bookshelf topics Top

mikecargal
Title: Hands-On Rust (Chap 8 (Adding a Heads Up Display) It looks like ​.with_simple_console_no_bg​(SCREEN_WIDTH*2, SCREEN_HEIGHT*2...
New
raul
Page 28: It implements io.ReaderAt on the store type. Sorry if it’s a dumb question but was the io.ReaderAt supposed to be io.ReadAt? ...
New
adamwoolhether
When trying to generate the protobuf .go file, I receive this error: Unknown flag: --go_opt libprotoc 3.12.3 MacOS 11.3.1 Googling ...
New
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
brunogirin
When installing Cards as an editable package, I get the following error: ERROR: File “setup.py” not found. Directory cannot be installe...
New
akraut
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error. lib/pento_web/live/product_l...
New
jonmac
The allprojects block listed on page 245 produces the following error when syncing gradle: “org.gradle.api.GradleScriptException: A prob...
New
Henrai
Hi, I’m working on the Chapter 8 of the book. After I add add the point_offset, I’m still able to see acne: In the image above, I re...
New
dtonhofer
@parrt In the context of Chapter 4.3, the grammar Java.g4, meant to parse Java 6 compilation units, no longer passes ANTLR (currently 4....
New
mcpierce
@mfazio23 I’ve applied the changes from Chapter 5 of the book and everything builds correctly and runs. But, when I try to start a game,...
New

Other popular topics Top

brentjanderson
Bought the Moonlander mechanical keyboard. Cherry Brown MX switches. Arms and wrists have been hurting enough that it’s time I did someth...
New
AstonJ
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
New
PragmaticBookshelf
Build highly interactive applications without ever leaving Elixir, the way the experts do. Let LiveView take care of performance, scalabi...
New
AstonJ
Continuing the discussion from Thinking about learning Crystal, let’s discuss - I was wondering which languages don’t GC - maybe we can c...
New
First poster: joeb
The File System Access API with Origin Private File System. WebKit supports new API that makes it possible for web apps to create, open,...
New
PragmaticBookshelf
Author Spotlight Mike Riley @mriley This month, we turn the spotlight on Mike Riley, author of Portable Python Projects. Mike’s book ...
New
PragmaticBookshelf
Author Spotlight Rebecca Skinner @RebeccaSkinner Welcome to our latest author spotlight, where we sit down with Rebecca Skinner, auth...
New
DevotionGeo
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
New
PragmaticBookshelf
Author Spotlight: Tammy Coron @Paradox927 Gaming, and writing games in particular, is about passion, vision, experience, and immersio...
New
PragmaticBookshelf
A Ruby-Centric Chat with Noel Rappin @noelrappin Once you start noodling around with Ruby you quickly figure out, as Noel Rappi...
New

Sub Categories: