On Mon, Jan 11, 2010 at 1:03 AM, Alf P. Steinbach <al...@start.no> wrote: > * Steven D'Aprano: >> >> On Mon, 11 Jan 2010 08:56:36 +0100, Alf P. Steinbach wrote: >> >>> * Paul Rudin: >>>> >>>> Sebastian <sebastian.lan...@gmx.de> writes: >>>> >>>>> I have an array x=[1,2,3] >>>> >>>> In python such an object is called a "list". >>>> >>>> (In cpython it's implemented as an automatically resizable array.) >>> >>> I don't think the OP's terminology needs correction. >>> >>> A Python "list" is an array functionality-wise. >>> >>> If one isn't observant of that fact then one ends up with O(n^2) time >>> for the simplest things. >> >> Well that's certainly not true. Some operations may be O(N**2), but others >> are not: list.append() is amortized O(N) and for individual appends, may be >> can be as fast as O(1). > > The second sentence may or may not be true. I don't know of any fundamental > 'list' operations that have quadratic time. Is there? > > The first sentence is just baffling -- what on Earth is the "that" that > you think is not true? > > OK, I can guess (correct me if I'm guessing wrong, please): you think I'm > talking about elementary operations. I'm not. I'm talking about algorithmic > complexity for loops doing e.g. insertions. > > >>> Using the term "array" accentuates and clarifies this most important >>> aspect. >> >> But Python lists are designed to behave as lists. > > No, I'm sorry, they're not. > > A Python 'list' has de facto constant time indexing, or "random access". > > A linked list -- what the informal "list" means in programming
Eh, it's a bit context-dependent. The abstract data type definition is a superset that includes both linked lists and dynamic arrays. FWIW, Java likewise uses "list" in its ADT sense. Cheers, Chris -- http://blog.rebertia.com -- http://mail.python.org/mailman/listinfo/python-list
