GSoC: Linked List || Blog post by Chetan Karwa || #11

Greetings Everyone,

The past week I was basically working on improving my API by fixing some bugs like:

  • Inserting an element at index beyond the size of the list or at a negative index
  • Popping nodes from empty list
  • Connecting the current child list’s tail to the next child list’s head and similar corner cases.

Planning for the coming week:

  • Figured a major issue with APIs concat and slice i.e. APIs were using a shallow copy of the lists that might lead to data leak/fragmentation. So change the code to create a deep copy of the list for both the APIs.
  • Implement a new API absorb (Inspired by the wrong implementation of concat).
    before - ListA, ListB
    API call - ListA.absorb(ListB)
    after - ListA = ListA+ListB(shallow copy), ListB = empty
  • Document my project.

Thank You

3 Likes

Hey Chetan,
I was working on a very similar thing as yours.

Curious to know which approach you preferred when an element is added at a negative index (let’s say x) in an empty list?
1). Do you create some empty nodes before inserting the element at x?
2). OR do you directly add the element and store that the head of the list (as well as the tail, since list contains only one element as of now) is at index x (which is a negative integer)
3). OR do you consider inserting at negative indexes equivalent to inserting at head of the list and similarly inserting at an index greater than length of the list equivalent to inserting at tail of the list?

Hey Aman,
I preferred the 2nd solution to it.
Whenever something is inserted at negative index I have added that new node before the present head of the list.
And similarly if the index mentioned is beyond the size of the list, I have attached the new node at the tail of the list.
This is corrosponding to my get function.