RunestoneInteractive / RunestoneInteractive/pythonds

ArrayList code last_index issue - Section 9.2

Open
#94 1 comment 0 reactions 1 assignee View on GitHub

@bnmnetp is already working on this.

Since Jul 24, 2020.

Dominant language
Python
Stars
273
Forks
160
PR merge metrics
No merged PRs in 30d

Description

Chapter 9, Section 2: Python Lists Revisited

The last_index in this code is tracking one position past the last item in the list.
It starts pointing to index 0 in an empty list.
Then, let's say we add 1 to a fresh instance of ArrayList, it will be the only (and also the last) item on index 0, but last_index will be 1
Up to this point, it's not a problem, but could cause problems when trying to pop an item from the list

class ArrayList:
    def __init__(self):
        self.size_exponent = 0
        self.max_size = 0
        self.last_index = 0
        self.my_array = []

    def append(self, val):
        if self.last_index > self.max_size - 1:  |\label{line:lst_arr_size}|
            self.__resize()
        self.my_array[self.last_index] = val
        self.last_index += 1

But then, there's a problem on this listing:

def insert(self, idx, val):
    if self.last_index > self.max_size - 1:
        self.__resize()
    for i in range(self.last_index, idx - 1, -1):  |\label{line:lst_arrlistins_range}|
        self.my_array[i + 1] = self.my_array[i]
    self.last_index += 1
    self.my_array[idx] = val

Let's say we have a list [1,0] with max_size == 2. According to the first snippet, after appending one item last_index == 1. If we insert anything, the first iteration on the loop will try to access the array on index 2, which should cause an IndexError

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.