Re-implementing an Array Class in Python

Question

I gave an attempt at reinventing the wheel and recreate list methods using my own Array Class to broaden my understanding about lists. I would like advice regarding efficiency, and in implementing negative indexes, since my code only works for positive ones.

class Array: def __init__(self, List=[]): self.array = List def display(self): print(self.array) def len(self): array = self.array count = 0 for _ in array: count += 1 return count def append(self, value): array = self.array length = self.len() results = [None] * (length+1) for i in range(length): results[i] = array[i] results[length] = value self.array = results def search(self, value): array = self.array pos = -1 for index in range(self.len()): if array[index] == value: pos = index return pos def insert(self, index, value): array = self.array length = self.len() results = [None] * (length+1) if index > length: raise IndexError elif index == length: self.append(value) results = self.array else: for i in range(length): if i == index: for j in range(index + 1, length + 1): results[j] = array[j-1] results[index] = value break else: results[i] = array[i] self.array = results def delete(self, value): array = self.array length = self.len() results = [None] * (length-1) pos = self.search(value) if pos == -1: raise "Index Error: Element Not Found" else: for i in range(length): if i != pos: results[i] = array[i] else: for j in range(pos+1, length): results[j-1] = array[j] break self.array = results def pop(self): array = self.array length = self.len() results = [None] * (length-1) if length == 0: raise IndexError value = array[-1] for i in range(length-1): results[i] = array[i] self.array = results return value 

Answer 1

Seems like cheating to re-implement a list using a list... I feel like the real challenge would be doing so without a list of any sort, say creating a linked list or a tree or something like that. That might be pedantic, but it'd clarify what your limitation are and thus what efficient solutions are available versus what you're making needlessly hard for yourself because it's fun.

Most of your functions are going to be very expensive because you're constantly copying memory around. A more common approach is to over-allocate space and then keep two values, "length" and "_allocated". The first is how many valid elements your array contains; the second is how much space you've reserved to store values. When you want to append X to your array, you can just assign X to self.array[self.length] and then increment self.length. If that would take you beyond what you've allocated, only then you do the expensive act of allocating a new chunk of memory (in your case, the [None] * (length + 1) line) and copying the data. To minimize the number of copies, it's common practice to double the length of the array each time you resize it (maybe up to some maximum, at which point you add on new 4K element blocks or whatever rather than multiplying, to prevent running out of memory prematurely). When inserting, then, you'd just need to shift the later values rather than copy everything; similarly, when popping values off, just decrement self.length to mark that last element as unimportant and available to be overwritten.

To complement that approach, if you want to optimize for mid-array insertions and deletions, you can maintain a parallel bit-array of which values are valid and which aren't. Iterating through the array becomes trickier (you need to zip the values with the validity flags and only return the valid ones), but deleting an item becomes cheaper since you only need to find the element and mark it as deleted (no shifting required), and inserting an item only requires shifting things until you find an unused element that can be overwritten instead of shifted.

Caching the length of the array is a good idea in general (though not necessary if you don't over-allocate). It requires extra code and care to keep synchronized with the rest of the array, but checking a list's length is a very common thing for users to want to do, and the O(N) computation each time can get painful.

As a general Python'ism, I'd say use def __len__ instead of def len and implement __get_item__, as well as any other magic methods that generally correspond to an array. For reference see this documentation page, and consider that most people think of an array as some combination of a "Collection" and "[Mutable]Sequence"