Add Linked Lists

[rohansingh9001]

Description of the problem

Currently the package does not have Queues or Linked Lists.
While working with issue #22-Add Queue
It was discovered that to add a Queue which is efficient enough to perform popleft() action in O(1) time we need linked lists to implement Queues just like the collections.deque implementaion of a Queue.

Since the original goal of issue #22 was to reduce dependencies on other libraries, LInked List must be added to pydatastructs to ensure an efficient implementation of Queues.

Example of the problem

sample_queue = Queue()
for i in range(N) # N be a large number
... sample_queue.append('#')
...
sample_queue.popleft() # Takes O(N) time

References/Other comments

See the original issue -
#22

Read about the efficiency issue here -
https://www.geeksforgeeks.org/deque-in-python/
https://stackoverflow.com/questions/55578874/dequeue-complexity-on-using-python-list-as-a-queue

[rohansingh9001]

I have already written the code for Double LInked LIsts I am Currently Adding Single Linked Lists
and Documentation within the code.
After this I can start working on Queue which should not take much time

[czgdp1807]

Please discuss the API first before moving on to a PR. Share your code here in the comments.

[rohansingh9001]

API for Double Linked List:

1. A Doubly linked list should be initialised with DoubleLinkedList()

2. Elements can be pushed at the start of the list using .push(data)

3. Elements can be appended at the end using .append(data)

4. Elements can be popped from the list at a certain index by .pop(index)

5. __getitem__ and __setitem__ support using python syntax,
   eg -
   list[1]
list[5] =4

6. Print the Linked List in List form using print() function
   eg -
   if elements in linked list named sample_list are 1-2-3-4
   >>>print(sample_list)
[1,2,3,4]

7. Return length of the Linked List using len() function.

8. .popright() and .popleft() pops items from the right and the left respectively.

9. .insertAt(index, data) inserts a new Node at the index.

10. .insertBefore(Node, data) and .insertAfter(Node, data) inserts a new Node before and after the input Node respectively.

API names can be changes easily in order to keep them parallel with norms please suggest any change in the names of the functions.

I will share the temporary code in the next comment. Documentation is incomplete. Some examples with expected output has been provided at the end.

[czgdp1807]

2. Elements can be pushed at the start of the list using .push(data)

appendleft would be a better name.

4. Elements can be popped from the list at a certain index by .pop(index)

What would be the amortized time complexity of this operation?

[czgdp1807]

I will comment on the code you shared just now a bit later.

[rohansingh9001]

It would have to traverse through the string so the .pop(index)
will take O(n) in worst case scenarios.
Since I have added a List tail as well along with the list head, we can easily start traversal from the end.
If we consider starting the traversal from the head or the tail depending upon the nearness of the index from the start or the end, the worst time can be brought down to (n/2)

I cannot find any way to improve upon this without making extra arrays and increasing the memory consumed by the List. If you are aware of any methods please share any resources so I can add it.

The operations at the ends take O(1) time though.

Also should I change the .append() to .appendright in view of symetry?

I was facing difficulty uploading the .py file so I have uploaded the txt file with the code
linked_list.txt

[czgdp1807]

The code is fine but follow the coding style of the code in current master, especially the documentation. Please read the guidelines in the README file. The code should go in a new file under, linear_data_structures folder with the name, linked_lists.
Please cite reliable references in the code, like Wikipedia. Make separate PRs for adding each type(singly linked lists, doubly linked lists, etc.) for better management.

[rohansingh9001]

Sorry for the sudden absence, due to my current location in Delhi, internet services were down due to some orders and I could not inform you before leaving for travelling. I have learned a bit about code coverage in the meantime and I will resume work on the single linked lists.

[rohansingh9001]

I have read the feedback. I will make sure to follow them in any future PRs.