[Chicago] "open source" project / linked lists

[Thomas Johnson]

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:

>
>> >> There's a project in the class, an "open source" project.  It could
>> >> require programming, but not necessarily.  Maybe beta testing or
>> helping to
>> >> organize events, etc.  Any ideas or recommendations?  Are you guys on
>> >> Github?
>>
>>
> So, for sure ChiPy has a Github account, and it looks like there are
> currently some open issues for our webpage -- maybe contributors can give
> advice?:
>
> https://github.com/chicagopython/chipy.org/issues
>
>
> >> By the way, does someone know how to implement linked lists in Python.
>
>
> It seems you are interested in memory management -- what about
> contributing to the *boost.NumPy* project? I've not contributed yet, but
> it looks like the goal is to add more C++ capability to the Boost.Python project,
> which is connected to Boost -- (IMO) the best library in C++.
>
> https://github.com/ndarray/Boost.NumPy
>
>
>
>> >> ... 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
> _______________________________________________
> 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/8c031de4/attachment.html>