Need help with Java data structure please. Thank you. 250 Chapter 4 Linked Lists
ID: 3828759 • Letter: N
Question
Need help with Java data structure please. Thank you.
250 Chapter 4 Linked Lists protected LinkedListNode first; //variable to store address of the firs //node of the list protected LinkedListNode last //variable to store the address of the last //node of the list protected int count; //Place the definitions of the nonabstract methods and //abstract methods here. UNORDERED LINKED LISTS As described in the preceding section we derive the class UnorderedLinkedtini the abstract class LinkedIistclass and implement the operations deleteNode. Class: UnorderedLinkedIist public class UnorderedLinkedList extends LinkedListclass Instance Variables: Same as the instance variables of the class LinkedIistclass Constructors and Instance Methods: public UnorderedLinkedList //default constructor public UnorderedLinkedList (UnorderedLinkedList other List) //copy constructor public boolean search (DataElement searchItem) //Method to determine whether searchItem is in the //Postcondition. Returns true if searchItem is found in the list false otherwise public void deleteNode (DataElement deleteltem) //Method to delete deleteltem from the list //Postcondition: If found, the node containing deleteltem is deleted from the first list. Also, first points to the node, last points to the last node of the updated list and count is decremented by 1.Explanation / Answer
3)a.
void linkedListType<T>::deleteSmallest()
{
nodeType<T> *current;
nodeType<T> *trailCurrent; // used for pointing to node just before current
nodeType<T> *small;
nodeType<T> *trailSmall;
if (first == NULL)
cout << "Cannot delete from an empty list." << endl;
else
if (first->link == NULL)
{
first = NULL;
delete last;
last = NULL;
}
else
{
small = first;
trailCurrent = first;
current = first->link;
while (current != NULL)
{
if (small->info > current->info)
{
trailSmall = trailCurrent;
small = current;
}
trailCurrent = current;
current = current->link;
}
if (small == first)
first = first->link;
else if (small != first)
{
trailSmall->link = small->link;
if (small == last)
last = trailSmall;
}
delete small;
}
}
3)b,
public class LinkedList{
Node head;
class Node{
int data;
Node next;
Node(int d){data =d; next = null;}
}
public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
public void insertAfter(Node givenNode, int new_data){
if(givenNode == null)
System.out.println("Given node cannot be empty");
Node new_node = new Node(new_data);
new_node.next = givenNode.next;
givenNode.next = new_node;
}
public void append(int new_data){
Node new_node = new Node(new_data);
if(head == null)
head = new_node;
else{
Node last = head;
while(last.next != null)
last = last.next;
last.next = new_node;
}
}
public void printList(){
Node temp = head;
while(temp != null){
System.out.println(temp.data + " ");
temp = temp.next;
}
}
void deleteNode(int key){
// Store head node
Node temp = head, prev=null;
// If head node itself holds the key or multiple occurrences of key
while(temp != null && temp.data == key){
head = temp.next;
temp = head;
}
// Delete occurrences other than head
while(temp != null){
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev.next'
while(temp != null && temp.data != 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;
//Update Temp for next iteration of outer loop
temp = prev.next;
}
}
public static void main(String[] args){
LinkedList llist = new LinkedList();
llist.push(6);
llist.append(7);
llist.append(7);
llist.append(7);
llist.append(9);
llist.push(10);
llist.deleteNode(7);
llist.printList();
}
}