APIs for linked list module.

[ChetanKarwa]

Description

I am currently working on the Linked List module for stdlib (under GSoC 2021).
This issue is somewhat an extension to an already existing issue #68.
This especially focuses on APIs for Linked List. This thread is to welcome ideas for APIs that can be implemented in the module and ideas for optimum implementation of the same.

For my project, I have implemented 3 types of lists:

• A simple linked list
• A list of list
• A list of arrays

Based on some tests with random data set, we decided that out of all the 3 implementations "list of list" is better compared to the other 2.
So for the time being, I intend to implement all the APIs on the "list of list" model.

APIs that I intend to implement

• insert: Insert an element at the specified index of the list
• set/replace: Replaces an element at the given index
• clear: Deletes the whole list (Without memory leaks)
• Size: Returns the size of the list
• reverse: Reverse the list
• sort: Sort the items in the list (if homogenous, not sure)
• Concat: Appends a list to another list
• slice: Returns a Slice (a continuous part) of the list
• splice: Removes a continuous part of the list

Already Implemented

• Get: Returns the element stored at index.
• pop: Removes an element from the end of the list.
• remove: Removes an element present at given index
• append: Append an element at the end of the list

My works (link).

[ChetanKarwa]

APIs that I have already implemented are pretty straight forward but the others are a bit tricky.
For instance,
Insert API, there can be many possible implementations but for now, I have decided to use the following idea to implement the same.
There can be 2 possible scenarios when it comes to inserting an element:

• The child list where we need to insert the element is not full (i.e. number of elements < MaxSize)
  - Directly insert the element.
• The child list is already full.
  - Splits the child list into two adjacent child lists (split the list at the index where we need to insert the element)

This is just one way to get past it, other ideas that occurred to me:

• Create a new adjacent child list that will hold just the last element of the current list.
• Create a new adjacent child list that will hold the last 50% of the elements of the current list. (More time consuming to traverse to the middle of the list)

This is just some example, so for writing such APIs I wish for as many perspectives as I can receive from the community.
Thank you.

[arjenmarkus]

I thought at first that inserting a new element in a full child list could be done in such a way that you get new child lists with just a few elements all the time. That may occur, perhaps by inserting two elements at the end of the child list: FIrst just before very end - N-1, causing a new child list to appear, with the new element and the last element. Then insert another in the shortened original child list - that would be full then and you can repeat the process. An alternative migh tbe to allow for some wiggle room - do not fill the child list up to its maximum capacity but split it with some probability even when it is shorter. The effect would be that not all your child lists are of maximum length, but when the random splitting is chosen strategically, you might get child lists of roughly equal size. Something like: if the child list is at 90% or more of its capacilty, then spit it up with a probability of x%. If it is full, then split it up anyway. Mind you this thinking out loud! I can imagine all manner of small experiments to determine a useful threshold and probability to see whether the lengths of the child lists do not vary too much. Not an easy task, actually, you should carefully define what you want to achieve. Op wo 14 jul. 2021 om 21:18 schreef ChetanKarwa ***@***.***>:

…

APIs that I have already implemented are pretty straight forward but the others are a bit tricky. For instance, Insert API, there can be many possible implementations but for now, I have decided to use the following idea to implement the same. There can be 2 possible scenarios when it comes to inserting an element: - The child list where we need to insert the element is not full (i.e. number of elements < MaxSize) - Directly insert the element. - The child list is already full. - Splits the child list into two adjacent child lists (split the list at the index where we need to insert the element) This is just one way to get past it, other ideas that occurred to me: - Create a new adjacent child list that will hold just the last element of the current list. - Create a new adjacent child list that will hold the last 50% of the elements of the current list. (More time consuming to traverse to the middle of the list) This is just some example, so for writing such APIs I wish for as many perspectives as I can receive from the community. Thank you. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#463 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAN6YRZYCHM3LB4VX2IYBGTTXXPIBANCNFSM5AMAVMNA> .