[Chicago] "open source" project / linked lists

[sheila miguez]

I think you meant to reply to Douglas, not Tanya.

She wasn't asking about ArrayList versus LinkedList and the Java
implementation or general implementation thereof, Douglas was.

Good replies from both you and Tanya, though.


On Mon, Feb 9, 2015 at 11:29 AM, Thomas Johnson <thomas.j.johnson at gmail.com>
wrote:

> Regarding link lists / arraylists:
> Linked lists are used for more than just torturing students.
>
> Linked lists have small constant-time append/remove operations at the
> beginning and end of the list.
>
> In an array list, you have constant-time append and remove at the end of
> the list - until you run out of allocated memory. Once that happens, you
> have to allocate a new chunk of memory and copy the whole ArrayList over.
> This can cause a significant performance hit at runtime.
>
> Adding an element at the beginning of the ArrayList also causes a data
> copy each time. Removal at the beginning of the ArrayList can be
> implemented in a clever way by marking nodes as unused (in which case it's
> O(1)), although a naive implementation is O(n).
>
> On Mon Feb 09 2015 at 11:19:04 AM Tanya Schlusser <tanya at tickel.net>
> wrote:
>
>> [various open source project advice]
>>>
>>
>>
>>
>>> >> ... I was wondering if this could be implemented in Python as well.
>>> I don't
>>> >> see why not.  I'm still trying to see the benefits of linked lists.
>>> So far I
>>> >> haven't seen anything in linked lists that couldn't be done more
>>> easily
>>> >> using Arrays or ArrayLists???  But hey, I guess linked lists are cool,
>>> >> especially if you want to torture students and beginning
>>> programmers!!!
>>> >>  ;-)
>>>
>>
>>
>> There are no pointers in Python -- it's a higher level -- with the intent
>> to keep the details of memory management away from the programmer.
>>
>> Linked lists allow you to allocate memory for an object dynamically,
>> during runtime, so you don't have to allocate a ginormous array to hold all
>> of the *potential* contents of your list that may or may not be created.
>> ... at one time long ago (when I was in school) memory was scarce enough
>> that this would have been bad...
>>
>> HTH
>>
>> Best,
>> Tanya
>>
>

-- 
shekay at pobox.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150209/29c2b459/attachment.html>