On Sep 21, 3:47 am, Steven D'Aprano <[EMAIL PROTECTED] cybersource.com.au> wrote: > On Sat, 20 Sep 2008 16:27:41 -0700, Alex Snast wrote: > > Another quick question please, is the List data structure just a dynamic > > array? If so how can you use static size array, linked list, AVL trees > > etcetera. > > Before I answer your question, I should say that you can go a LONG way > with just the standard Python built-in data structures list, dict and > set, plus a handful of standard modules like array and collections. It's > often (but not always) better to modify an algorithm to use a built-in > data structure than to try to implement your own. > > The underlying data structure for lists is implementation specific. Only > the behaviour is specified by the language. > > In the standard Python implementation written in C (usually known as > "Python", although sometimes people explicitly describe it as CPython), > lists are implemented as a fixed array of pointers. The array is > periodically resized, either up or down, but only as needed. The largest > consequence of that is that appending to the end of a list is much faster > than inserting at the beginning of the list. > > Other implementations (IronPython, Jython, PyPy, CLPython...) are free to > implement lists whatever way they need. > > If you want a static list, the simplest way is to create a list and > simply not resize it. If you want to enforce that, here's a subclass to > get you started: > > class StaticList(list): > def _resize(self): > raise RuntimeError("list can't be resized") > extend = append = pop = insert = remove = \ > __delitem__ = __delslice__ = _resize > > I haven't dealt with __setitem__ or __setslice__, because they're more > complicated: you need to make sure the slice you're setting has the same > size as the bit you're replacing, so that this is allowed: > > mylist[3:6] = [1, 2, 3] > > but not these: > > mylist[3:6] = [1, 2] > mylist[3:6] = [1, 2, 3, 4] > > As for linked lists and trees, don't worry about pointers, just go ahead > and implement them. > > # basic, no-frills tree > class Node(object): > def __init__(self, data, left=None, right=None): > self.left = left > self.right = right > self.info = data > > tree = Node('top of the tree') > tree.left = Node('left subtree') > tree.right = Node('right subtree', None, Node('another subtree')) > t = tree.right.right > t.left = Node('yet another subtree') > > etc. > > The CPython implementation of dict is a hash table, and dicts are > extremely fast and efficient. So long as you don't mind losing the order > of insertion, you won't beat dicts for speed and efficiency in anything > you write in pure Python. > > -- > Steven
WOW you guys are really helpful, thanks everyone for all the replies. Last question: What IDE do you guys recommend, I'm currently using pydev. Thanks again, Alex -- http://mail.python.org/mailman/listinfo/python-list