Question

Linked List-Based Queue Sketches

In this section you will sketch several linked list-based queues. Hint: Recall that a proper sketch of a linked list-based queue is just a series of boxes with elements inside.

2, 3, 4

Sketch the linked list-based queue that results from the following operations:

1. Default constructor (create empty)

2. Add(2)

3. Add(3)

4. Add(4)

? Replace this with your sketch

Add and Remove

Sketch the linked list-based queue that results from the following operations:

5. Default constructor (create empty)

6. Add(2)

7. Add(3)

8. Add(4)

9. Remove()

? Replace this with your sketch

Answer 1

Preliminaries :

As we are implementing LinkedList Queue. It Follows FIrst IN FIrst Out which says that which node comes earlier will leave earlier. So the newly created nodes always create at linkedlist ending and the remove will always follow remove at beginning.

The LinkedList Node is represented as below,

< value of the node >

< next address pointed by the current node >

Sketch the linked list-based queue that results from the following operations:

1. Default constructor (create empty)
2. Add(2)
3. Add(3)
4. Add(4)

Solution :

Explanation :

Step 1 : Default constructor ( create empty)

In the step one, the empty node is created and its marked as header. NULL is shown as \0. and NULL says empty value. Whenever a new node is created always have the pointing address as NULL.

Step 2 : Add(2)

Adding first node replaces the NULL value with value 2. The address is assumed to be 100. Now the Head pointer points to the address 100.

Step 3: Add(3)

Up on adding value 3 lets say the address of this node is 102. Whenever a new node is created always have the pointing address as NULL. This node is pointed by the last created node here it is head node. Now the head node pointing addres is changed as 102. ( address of the new node with value 3)

Step 4: Add(4)

Up on adding value 3 lets say the address of this node is 102. Whenever a new node is created always have the pointing address as NULL. This node is pointed by the last created node starting from the head node it traverses till the \0 { which says pointing to none } appears. Now the head node pointing addres is changed as 102. ( address of the new node with value 3).

Add and Remove

Sketch the linked list-based queue that results from the following operations:

1. Default constructor (create empty)
2. Add(2)
3. Add(3)
4. Add(4)
5. Remove()

Solution:

Step 1 : Default constructor ( create empty)

In the step one, the empty node is created and its marked as header. NULL is shown as \0. and NULL says empty value. Whenever a new node is created always have the pointing address as NULL.

Step 2 : Add(2)

Adding first node replaces the NULL value with value 2. The address is assumed to be 100. Now the Head pointer points to the address 100.

Step 3: Add(3)

Up on adding value 3 lets say the address of this node is 102. Whenever a new node is created always have the pointing address as NULL. This node is pointed by the last created node here it is head node. Now the head node pointing addres is changed as 102. ( address of the new node with value 3)

Step 4: Add(4)

Up on adding value 3 lets say the address of this node is 102. Whenever a new node is created always have the pointing address as NULL. This node is pointed by the last created node starting from the head node it traverses till the \0 { which says pointing to none } appears. Now the head node pointing addres is changed as 102. ( address of the new node with value 3).

Step 5 : Remove

As we are implementing the LinkedList Queue. The Queue always follows FIFO ( First IN First Out). So the header node is deleted and the address node pointed by the header node becomes the new header.