In Section 7.7 we implement a recursive version of the list insert operation, fo

Question

In Section 7.7 we implement a recursive version of the list insert operation, for
sorted linked lists. Using that as a model, design and implement a recursive version
of the list delete operation, for sorted linked lists. Note that the code for our
recursive insert method is included in the SortedLinkedList2 class.

code example 7.7

private ListNode recursiveInsert(ListNode subList, Listable item)
{
if (subList == null || item.compareTo(subList.info) < 0)
{
// Insert new node at the front of this sublist
ListNode newNode = new ListNode();
newNode.info = item;
newNode.next = subList;
// Return reference to new node
return newNode;
}
else
{
// Recursively insert item into list referenced by next
// field of current sublist
subList.next = recursiveInsert(subList.next, item);
// Return reference to this sublist
return subList;
}
}
public void insert(Listable item)
// Adds a copy of item to list
{
list = recursiveInsert(list, item);
}

Explanation / Answer

import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node link; /* Constructor */ public Node() { link = null; data = 0; } /* Constructor */ public Node(int d,Node n) { data = d; link = n; } /* Function to set link to next Node */ public void setLink(Node n) { link = n; } /* Function to set data to current Node */ public void setData(int d) { data = d; } /* Function to get link to next node */ public Node getLink() { return link; } /* Function to get data from current Node */ public int getData() { return data; } } class linkedList { protected Node start; public int size; public linkedList() { start=null; size = 0; } /* Function to check if list is empty */ public boolean isEmpty() { return start == null; } /* Function to check size of list */ public int getSize() { return size; } /* Function to insert an element */ public void insert(int val) { Node nptr, ptr, tmp = null; nptr = new Node(val, null); boolean ins = false; if (start == null) start = nptr; else if (val = tmp.getData() && val list.getSize() ) System.out.println("Invalid position "); else list.deleteAtPos(p); break; case 3 : System.out.println("Empty status = "+ list.isEmpty()+" "); break; case 4 : System.out.println("Size = "+ list.getSize() +" "); break; default : System.out.println("Wrong Entry "); break; } /* Display List */ list.display(); System.out.println(" Do you want to continue (Type y or n) "); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.