Question

Using the textbook implementation of integer node given below;

public class IntegerNode

{

public int item;

public IntegerNode next;

public IntegerNode(int newItem)

{

item = newItem;

next = null;

} // end constructor

public IntegerNode(int newItem, IntegerNode nextNode)

{

item = newItem;

next = nextNode; } // end constructor

} // end class IntegerNode

You need to implement add( ), delete( ), traverse( ) methods for an ordered linked list. And after insertion and deletion, your linked list will remain ordered.

Here is the procedure for testing. Please include this.

• Add the numbers 2, 3, and 6 to the list
• Display the list contents
• Add 5 to the list
• Display the list contents
• Delete 3 from the list
• Display the list contents
• Delete 2 from the list
• Display the list contents

THANK YOU!!!

Answer 1

public class LinkedList {
  
IntegerNode head; // head of list
  
// Linked list Node.
// This inner class is made static
// so that main() can access it
public static class IntegerNode {
  
public int item;
public IntegerNode next;

public IntegerNode(int newItem)

{
item = newItem;
next = null;
} // end constructor

public IntegerNode(int newItem, IntegerNode nextNode)

{

item = newItem;
next = nextNode;
  
} // end constructor
} // end class IntegerNode
  
// Method to insert a new node
public static LinkedList insert(LinkedList list, int data)
{
// Create a new node with given data
IntegerNode new_node = new IntegerNode(data);
new_node.next = null;
  
// If the Linked List is empty,
// then make the new node as head
if (list.head == null || list.head.item>=new_node.item) {
list.head = new_node;
}
else {
// Else traverse till the last node
// and insert the new_node there
IntegerNode last = list.head;
  
while (last.next != null && last.next.item<new_node.item) {
last = last.next;
}
  
// Insert the new_node
new_node.next=last.next;
last.next = new_node;
}
  
// Return the list by head
return list;
}
  
void deleteNode(int key)
{
// Store head node
IntegerNode temp = head, prev = null;

// If head node itself holds the key to be deleted
if (temp != null && temp.item == key)
{
head = temp.next; // Changed head
return;
}

// Search for the key to be deleted, keep track of the
// previous node as we need to change temp.next
while (temp != null && temp.item != key)
{
prev = temp;
temp = temp.next;
}

// If key was not present in linked list
if (temp == null) return;

// Unlink the node from linked list
prev.next = temp.next;
}

// Method to print the LinkedList.
public static void printList(LinkedList list)
{
IntegerNode currNode = list.head;

System.out.print("LinkedList: ");

// Traverse through the LinkedList
while (currNode != null) {
// Print the data at current node
System.out.print(currNode.item + " ");

// Go to next node
currNode = currNode.next;
}
}

// Driver code
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList list = new LinkedList();
  
//
// ******INSERTION******
//
  
// Insert the values
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 6);
  
// Print the LinkedList
printList(list);
  
list = insert(list, 5);
System.out.println("\n");
printList(list);
  
list.deleteNode(3);
System.out.println("\n");
printList(list);
  
list.deleteNode(2);
System.out.println("\n");
printList(list);
  
}
}

Output Window:

This program has been compiled in online java compiler. The input is taken according to the specification in the question.