Mod 4

Question 1

What are the advantages and disadvantages of linked lists?

Answer 1

We can always add and remove from the start/end of the linked list in constant time.

However, it takes a long time to access elements in the middle of the list. Also, we need to use a bit of space for each link.

This means that linked lists tend to be good for implementing ADTs where we only do operations at the ends of a structure.

Question 2

What two fields are required for a node in a linked list?

Answer 2

1. value – This is where the value associated with the node is stored.
2. next – This points to the next node in the list (or to None, if there is no next node).

Question 3

What are sentinel nodes?

Answer 3

Basically, they are nodes that hold a piece of data that indicates it is the start or end of the linked list. Sentinel nodes differ from the head of a linked list, in that their data isn’t actually used in the program. For example, they might hold None data in Python.

Question 4

Explain what a stack ADT is?

Answer 4

A stack is a linear ADT that imposes a last in, first out (or LIFO) order on elements. In other words, in a stack, the last element that was inserted must always be the first one to be removed.

Because of the LIFO ordering it imposes, the stack ADT behaves much like a physical stack in the real world (e.g., a stack of books or a stack of dishes). With a physical stack in the real world, items may only be placed on top of the stack, and only the top item may be removed.

Question 5

What are three operations of a stack?

Answer 5

1. push()
2. pop()
3. peek()

Question 6

What is the preferred implementation of a stack? Why?

Answer 6

We can implement a stack using a singly linked list, where the head of the list corresponds to the top of the stack.

When a value is pushed onto a linked list-based stack, it simply becomes the new head of the list. When a value is popped, the current head of the list is removed, and the next node becomes the new head (or top of the stack).

Since the push() and pop() operations of a stack built on top of a linked list simply manipulate the head of the list (which we always maintain a reference to), they are both O(1) operations (best-case, worst-case, and average).

This is preferable to using an array because an array must either add elements to the end and occasionally resize or shift elements. The former is amortized O(1).

Question 7

How would you implement a queue with a linked list?

Answer 7

I would use variables to track the head and tail of the linked list. When enqueue is called the value can be added at tail and when deque is called the value can be retrieved from head and then removed from the queue. Hence both operations are in O(1).

Question 8

How would you implement a queue with an array so that all operations have amortized O(1)?

Answer 8

We will add values to the end and remove from the beginning. We will also set variables to track the beginning and end. When we remove values we will leave space in the array and increment our beginning. When we add values, if size != capacity, we will either add the value at the end or wrap around to the beginning (index 0), aka circular buffer. If we need to resize the array then we will reindex the array by copying values in a loop that starts at the beginning index. As all operations except resize are O(1), this achieves amortized O(1).

Question 9

Should we use sentinels when implementing a deque with a linked list?

Answer 9

Yes. Remember, a deque must support four primary operations: adding to both the front and back and removing from both the front and back. Without using sentinels, each of these four operations would have to be implemented differently.

For example, when adding to the front of a list without sentinels, we would have to explicitly update the list’s head pointer upon each insertion; while on the other hand, adding to the back would require explicitly updating the list’s tail pointer.

However, when we use a list with front and back sentinels, we eliminate the need to implement different functionality in the deque’s insertion operations, and different functionality in its removal operation.

In this way, we have greatly simplified our implementation, factoring four operations down to just two methods: add_node_before() and remove_node().

Question 10

Describe linked lists and evaluate where it is appropriate to use them.

Answer 10

Linked lists are a series of nodes that use a link structure to point to subsequent items. They are ideal for linear data structures, like stacks and queues because they are dynamic and can add/remove/insert values at runtime O(1). They are efficient for large datasets as they do not waste any memory. However, more memory is required for each item as each object must hold a link to the next. Also, as items are not contiguous, traversal is more time consuming and random access is not possible. This makes them inefficient for small dataset or datasets that will frequently encounter searches and sorts.

Question 11

What is the difference between a queue and stack?

Answer 11

A queue is like a line for a ride, it is a FIFO structure. Oppositely, a stack is like a stack of pancakes, it is a FILO structure. When we insert into a queue we do it at the back (bottom), when we insert into a stack we do it at the top (front).

Stacks are often used for tasks that require backtracking, such as parsing expressions or implementing undo functionality.

Queues are often used for tasks that involve processing elements in a specific order, such as handling requests or scheduling tasks.

Question 12

What are the steps required to delete an item at the beginning of a linked list?

Answer 12

If we are not using a sentinel, we only need to change the head to the next element. If we are using a sentinel than we change the sentinels “next” (link structure) to the next element.

Question 13

What operations does a stack allow?

Answer 13

1. push
2. pop
   3.top/peek

Question 14

What operations does a queue allow?

Answer 14

1. enqueue
2. deque
   3.peek/front

Question 15

What operations does a dequeue allow?

Answer 15

push_front()

push_back()

pop_front()

pop_back()

front() Gets the front element from the deque.

back() Gets the last element from the deque

Question 16

How would you add a value to a DLL?

Answer 16

Assume we have sentinels. Lets insert node u. Find the node, lets say w, after the target location of our insertion. Set u.prev to w.prev. Set u.next** to w. Set u.next.prev to u. Set u.prev.next to u. Now u is a node in a dounbly linked list (DLL).