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.

[prshnt19]

Is it resolved?

[czgdp1807]

Only doubly linked lists are added as of writing this comment.

[prshnt19]

Should there be a single CircularLinkedList or two of them- implemented using SinglyLinkedList and DoublyLinkedList?

The API for CircularLinkedList should contain basic functions (insert, delete, displayList)
or all the functions of DoublyLinkedList?

[czgdp1807]

What about having, SinglyCircularLinkedList and DoublyCircularLinkedList? Regarding the API they can go along the lines of SinglyLinkedList and DoublyLinkedList.

[prshnt19]

SinglyCircularLinkedList and DoublyCircularLinkedList are fine. They can be inherited from SinglyLinkedList and DoublyLinkedList respectively.

[prshnt19]

I thought LinkedList implementation of Queue and Stack are under this issue.
API for Queue:
Enqueue: Adds an item to the queue.
Dequeue: Removes an item from the queue
Front: Get the front item from the queue.
Rear (optional): Get the last item from the queue.
isEmpty: Returns true if the Queue is empty, else false.

API for Stack:
push: Adds an item in the stack.
pop: Removes an item from the stack.
top: Returns the top element of the stack.
isEmpty: Returns true if the stack is empty, else false.

Should they be inherited from already defined SinglyLinkedList or defined as a new class?

[czgdp1807]

The design of base class Queue can be followed for the class LinkedListQueue and similarly for LinkedListStack, the design of base class Stack can be followed.

pydatastructs/pydatastructs/miscellaneous_data_structures/queue.py

Lines 49 to 67 in 19cabb2

	def __new__(cls, implementation='array', **kwargs):
	if implementation == 'array':
	return ArrayQueue(
	kwargs.get('items', None),
	kwargs.get('dtype', int))
	raise NotImplementedError(
	"%s hasn't been implemented yet."%(implementation))
	def append(self, *args, **kwargs):
	raise NotImplementedError(
	"This is an abstract method.")
	def popleft(self, *args, **kwargs):
	raise NotImplementedError(
	"This is an abstract method.")
	@property
	def is_empty(self):
	return None

pydatastructs/pydatastructs/miscellaneous_data_structures/stack.py

Lines 49 to 71 in 19cabb2

	def __new__(cls, implementation='array', **kwargs):
	if implementation == 'array':
	return ArrayStack(
	kwargs.get('items', None),
	kwargs.get('dtype', int))
	raise NotImplementedError(
	"%s hasn't been implemented yet."%(implementation))
	def push(self, *args, **kwargs):
	raise NotImplementedError(
	"This is an abstract method.")
	def pop(self, *args, **kwargs):
	raise NotImplementedError(
	"This is an abstract method.")
	@property
	def is_empty(self):
	return None
	@property
	def peek(self):
	return None

Should they be inherited from already defined SinglyLinkedList or defined as a new class?

No, we don't need to inherit SinglyLinkedList. See ArrayStack and ArrayQueue class and a similar kind of implementation is needed for the linked list implementations.

[prshnt19]

The Stack and Queue class have to be defined in linear_data_structures or in miscellaneous_data_structures?