Python class to implement a list with a size limit

Question

I am currently working through a python course about objected oriented programming. I was given this first assignment to work on:

Create a simple class, MaxSizeList, that acts a little bit like a list, with a pre-configured limit on its size.

Here some test calling code that imports the completed MaxSizeList and then uses it to create two new MaxSizeList objects.

from assignments import MaxSizeList # assumes "class MaxSizeList"
 # is in a script called "assignments.py"

Below are the test cases:

a = MaxSizeList(3)
b = MaxSizeList(1)
a.push("hey")
a.push("hi")
a.push("let's")
a.push("go")
b.push("hey")
b.push("hi")
b.push("let's")
b.push("go")
print(a.get_list())
print(b.get_list())

Output

 # ['hi', "let's", 'go']
 # ['go']

I came up with this code which outputs the correct result:

class MaxSizeList(object):
 ls = []
 def __init__(self,mx):
 self.val = mx
 def push(self,st):
 self.ls.append(st)
 def get_list(self):
 while len(self.ls) != self.val:
 self.ls.pop(0)
 return self.ls

Do you have any input on how this can be done more efficiently? Did I do it correctly or is there anything to note from the code I came up with?

Answer 1

Below, I have slightly recast your class. In those changes are incorporated two suggestions.

1) If limiting the size of the structure, do it at the input:

I removed the length check from get_list() and moved it to push()

2) Class attributes are not instance attributes:

You code had a bug whereby the ls attribute was declared on the class and not on the instance. In the case of:

class MaxSizeList(object):
 ls = []

ls will be shared will all instances of MaxSizeList. What you need is actually:

class MaxSizeList(object):
 def __init__(self, max_length):
 self.ls = []

In this case, every instance will get its own ls.

I am going to guess that this is why you needed to do the limiting on the output and not on the input. That combined with using the same test data for the a and the b instance allowed your test cases to pass even with a substantial bug.

Code:

class MaxSizeList(object):
 def __init__(self, max_length):
 self.max_length = max_length
 self.ls = []
 def push(self, st):
 if len(self.ls) == self.max_length:
 self.ls.pop(0)
 self.ls.append(st)
 def get_list(self):
 return self.ls

• Graipher: if you wanted more performance, you could swap out the internal list with a collections.deque, which has O(1) popleft instead of O(n) pop(0).
• Jaff: Thanks for your feedback. I thought the ls variable looked out of place. Anyway, upon further investigation I now understand the difference between shared class variable and self instance variables better.
• njzk2: the problem with this code is that you can do a.get_list().append(value), and bypass the size verification

Answer 2

Your code is incorrect, as easily seen by running the test cases. Lists a and b interfere with each other, due to the sharing of the ls variable. Each object needs its own self.ls.

You should abandon the habit of using cryptic short variable names like ls and st.

The way you store the data is inefficient, and arguably violates the spirit of the exercise even if it happens to produce similar results.

• The likely intention of a size-limited list is to cap the amount of memory needed to store data, if you know that you only care about the most recent n items. You, on the other hand, store everything, and only discard the excess when fetching the result in get_list().
• The way you discard items using self.ls.pop(0) is inefficient. When you remove the first item in a list, it has to copy every subsequent element over to fill in the hole. That is, pop(0) is said to be O(n), and your get_list() has O(n²) performance. You would be better off taking slices of the list — in which case you are guaranteed to copy each element at most once.
• If is likely better to allocate the entire list of size n up front. If you start with an empty list and add elements as necessary, then Python has to guess how much memory to allocate for the list, and may have to reallocate memory and copy the data behind the scenes if it underestimates.

The ideal data structure to use for this problem is a circular-list.

class MaxSizeList(object):
 def __init__(self, size_limit):
 self.list = [None] * size_limit
 self.next = 0
 def push(self, item):
 self.list[self.next % len(self.list)] = item
 self.next += 1
 def get_list(self):
 if self.next < len(self.list):
 return self.list[:self.next]
 else:
 split = self.next % len(self.list)
 return self.list[split:] + self.list[:split]

• Jaff: Thanks for the feedback. I am just having to read it again and again to make sense of some concepts. Will get back to you if i have any questions.
• njzk2: removing data from the list is left as an exercise.
• njzk2: as a side note, the get_list is O(n), but that's necessary anyway if you want to avoid side effects like get_list().append(value) (unless python keeps slices as views until you actually modify them, in which case they are transformed into actual copies?)

Answer 3

If your aim is to make this new object behave somewhat like a list, implement it as closely to a real Python list as possible by inheriting its behavior from the built-in list class. Then extend your class to add the behavior you want. Here's a partial implementation:

class MaxSizeList(list):
 def __init__(self, maxlen):
 self._maxlen = maxlen
 def append(self, element):
 self.__delitem__(slice(0, len(self) == self._maxlen))
 super(MaxSizeList, self).append(element)
a = MaxSizeList(3)
print(a)
a.append("hey")
print(a)
a.append("hi")
print(a)
a.append("let's")
print(a)
a.append("go")
print(a)

Output:

[]
['hey']
['hey', 'hi']
['hey', 'hi', "let's"]
['hi', "let's", 'go']

Now, why do I say that this is a "partial" implementation? Because there are many ways to add elements to a list. For example, if you add these lines to the end of the above script:

a.extend(["some", "more", "stuff"])
print(a)

You'll see this output at the end:

['hi', "let's", 'go', 'some', 'more', 'stuff']

Oops. Your work is not done. We've overridden the append method, but not the extend method. And there are others, like __setslice__, __mul__, and so on.

Essentially, to create a complete implementation, you'd have to extend your class to provide implementations for every built-in method of the list class that could conceivably enlarge the length of the list. Do a dir(list) to see all its built-in "magic" methods, and figure out which ones you'd need to extend.

• kyrill: Very insightful answer. Although it would seem simpler to derive from collections.deque and override the extra methods such as popleft, so it behaves more like a list.
• 200_success: The conventional wisdom is "Prefer composition to inheritance", precisely because of the dangers you mentioned. It is very tricky to ensure that you have overridden everything necessary to prevent a leaky abstraction. This exercise neither requires nor encourages inheritance, I think.