[Chicago] "open source" project / linked lists

[Thomas Johnson]

Sorry, you're right

On Mon Feb 09 2015 at 11:59:12 AM sheila miguez <shekay at pobox.com> wrote:

> 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
>  _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150209/4b40a88a/attachment.html>