Question

Are the ff. implementations good or bad? Explain your answer.

a. ArrayStack: push the items to the front of the array (index 0), not at the back

b. SLLStack: use the SLL’s tail node as the top of the stack

c. SLLDeque: using a singly-linked list to implement the Deque ADT

d. DLLVector: using a doubly-linked list to implement the Vector ADT

Answer 1

Q1. ArrayStack : push the items to the front of the array(index 0), not at the back;

Ans: Stack follows the FIFO order. FIFO stands for first in first out.The element you add last will be removed or processed first..

Implementing an arraystack by pushing the items to the front of the array is a bad way of implementing the arraystack. It is because, before pushing a element to the front of the arraystack you have to push all elements to the right of the index 0 and then first position will be empty and after this you can store the element to the first position.

Q2.  SLLStack: use the SLL’s tail node as the top of the stack
Ans: It is also a bad way of implementing the STACK using the tail of the single linked list. It is beacause, pushing a element to the stack is taking a constant tiime. Therefore, it has a complexity of O(1). But poping an element from the the stack will take the linear time, it is because we cannot refer to the previous node of the tail node. The only way of reaching at that node is by travelling all the nodes from the head node with the help of head node and after that we can remove the element from the linked list. Therefore, it has the complexity of the O(n).

For example: Let we have a SLLStack as :

1 -> 2 -> 3 -> 4 where head is pointed to 1 and tail is pointed to 4.

Push Operation : Inserting a new element will take a constant time as we have the tail pointed to 4. we only have to make 4 pointed to 5 and new tail will become 5. Therefore push(5) will leads to
1 -> 2 -> 3 -> 4 -> 5

Pop Operation: it has the complexity of O(n). As head is pointed to the 1 and we have to pop the element from the stack, therefore it will remove 5 but there doen't exist any variable which is pointed to 4. Therefore we have to travel upto 4 in the LinkedList and then we have to make the 4 pointed to Null. As we have to traverse through the list in order to delete the 5. Therefore, it has the complexity of O(n).

After pop operation, SLLStack will become:

1 -> 2 -> 3 -> 4

Therefore, due to the complexity of O(n) for the pop operation. It is the bad way of implementing stack using tail node of the linked list.

Q3: SLLDeque: using a singly-linked list to implement the Deque ADT

Ans: It is the good way of implementing Deque ABT using a singly-linked list.

Explanation:

Push operation: In Deque, element can be added in front as well as the end of the deque. and suppose head is pointed to the first element and tail is pointed to the last element. Therefore, adding a elment to the front and at the end can be done in a constant time.. It is O(1) in this case as inserting element at the front and end in a list can be done in a constant time. if head is pointed to firist element and end is pointed to the last element.

Pop Operation : In Deque, element can be remove from front as well as from the end of the deque. As head is pointed to the first element and the tail is pointed to the last element. Here there are two scenario of complexity.

O(1) complexity- for removing the element from the front. It is because we can refer to the next element with the help of head node as it is pointed to the next element. Therefore, deleting the element from the front of the linked list can be done in a constant time.

O(n) complexity - for removing the element from the end. It is because we cannot refer to the previous node of the tail node. The only way of reaching at that node is by travelling all the nodes from the head node with the help of head node and after that we can remove the element from the linked list. Therefore, it has the complexity of the O(n).

Q4. DLLVector: using a doubly-linked list to implement the Vector ADT

Ans4. It is also a good way of implementing Vector Abstract Data Type using doubly-linked list.

Vector abstract data type provides resizable array means that you are not bound to add and remove only definite numbers of elements from the array but you can add and remove elements as much you want. As it involves adding and removing elements from the array. Using double linked list implementation. you can add and remove the elements in a constant time. So it is a good way of implementing the vector abstract data type using the double linked list.