RunestoneInteractive / RunestoneInteractive/pythonds
ArrayList code last_index issue - Section 9.2
@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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.