Answer to Question #198671 in Java | JSP | JSF for Lucy ukoh

Question

A. A list data structure unlike stacks and queues ensure items are added and removed from any location within the list. This is useful for manipulating some forms of storage or processing requirements. a. Nodes in a list can be added in two ways. Using diagrams, explain the two (2) forms of adding a new node to an existing list. [4 marks]

b. Using diagrams, explain how the head pointer can be implemented in a single list such that it does not have to change during additions and deletions. Your resulting list should have five (5) regular nodes. [3 marks]

c. Provide the algorithm and supporting diagram for updating your list with a single node at the front of the List. Name the currently added node “Q”. Your resulting list will now have six (6) regular nodes. [3 marks]

Answer 1

a) There are two forms of adding new elements to the linked list. One of them is when we put the current node as the first or last node of the list. The current first (or last) element gets the referrence to the current as the previous (or next), and the referrence variable of the list which denotes the first (or last) node is assigned with the current node. The previous (or the next) node referrence of the current one is assigned with the header. The second form - inserting into the middle. Denote the required position of the node as N. The current Nth element gets the referrence to the current instead of the referrence to N+1th one and assigns the referrence of the previous one for the current one. The current node assigns its next element referrence with the N+1th node, and the N+1th node loses its link to the Nth one as a previous and replaces it as a current one, becomes N+2th node, and the current one- N+1th.

b)The header point does not require the change, it only changes the link to the first and last element. When the new node is added into the beginning of the list, then the header's link to the next node refers to the current node instead the one which was the first node before. Else if it is put into the tail, the header's link to the previous node refers to the current node instead the one which was the last node before.

When the node is erased from the head of the list, the link to the next node of the header does not refers to it anymore, it refers to the element next to the current one.

And when it is deleted from the tail, the link to the previous node of the header refers to the previous element of the current one instead of it.

c) When some element is added firstly, for example, to the head, it becomes the first node, the existing element (denote is at 1st) gets the referrence on it as the previous node and becomes the 2nd one, and the last, gets the link to the header as the next node. The header gets the link to the new first node as the next node. Being put to the tail, next one becomes the last node, the existing element, which is second one, gets the referrence on it as the next node and becomes the 2nd one. The header gets the link to the new last node as the prevoius node. And according to this algorithm the next 4 nodes will be inserted. If they are inserted into the middle, it can be performed by the algorithm stated in the point a.