Question

In JAVA, students will create a linked list structure that will be used to support a role playing game. The linked list will represent the main character inventory. The setting is a main character archeologist that is traveling around the jungle in search of an ancient tomb. The user can add items in inventory by priority as they travel around (pickup, buy, find), drop items when their bag is full, and use items (eat, spend, use), view their inventory as a whole or by category, request the number of items in inventory, and request to see values for specific inventory items. The categories for items are food, coins, archeology tools, artifacts, and documents. Each item should have an item number (unique integer value in priority order), category (string or integer), a description (string), and a value (integer). The program will use the linked list structure to allow the user to do the functions mentioned above; add (beginning/end), remove (from end), insert (based on ID number), delete (based on ID number), print inventory, print inventory by category, tell if the inventory is empty, tell how many items are in inventory, tell how many items in each category, and search for an item by name or ID and return its value. The code must validate the user input for valid choices and valid input type and throw exceptions that result in an appropriate message to the user. The code must also throw exceptions for trying to retrieve/print a node from an empty list. Please help ASAP

Answer 1

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at the contiguous location, the elements are linked using pointers as shown below.

In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

filter_none

brightness_4

class LinkedList {     Node head; // head of list        /* Linked list Node*/     class Node {         int data;         Node next;            // Constructor to create a new node         // Next is by default initialized         // as null         Node(int d) { data = d; }     } }

Creation and Insertion

In this article, insertion in the list is done at the end, that is the new node is added after the last node of the given Linked List. For example, if the given Linked List is 5->10->15->20->25 and 30 is to be inserted, then the Linked List becomes 5->10->15->20->25->30.

Since a Linked List is typically represented by the head pointer of it, it is required to traverse the list till the last node and then change the next of last node to new node.

import java.io.*;

  

// Java program to implement

// a Singly Linked List

public class LinkedList {

  

    Node head; // head of list

  

    // Linked list Node.

    // This inner class is made static

    // so that main() can access it

    static class Node {

  

        int data;

        Node next;

  

        // Constructor

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Method to insert a new node

public static LinkedList insert(LinkedList list, int data)

    {

        // Create a new node with given data

        Node new_node = new Node(data);

        new_node.next = null;

  

        // If the Linked List is empty,

        // then make the new node as head

        if (list.head == null) {

            list.head = new_node;

        }

        else {

            // Else traverse till the last node

            // and insert the new_node there

            Node last = list.head;

            while (last.next != null) {

                last = last.next;

            }

  

            // Insert the new_node at last node

            last.next = new_node;

        }

  

        // Return the list by head

        return list;

}

1. Search the key for its first occurrence in the list
2. Now, Any of the 3 conditions can be there:
   • Case 1: The key is found at head
     1. In this case, Change the head of the node to the next node of current head.
     2. Free the memory of replaced head node.
   • Case 2: The key is found at in the middle or last, except at head
     1. In this case, Find previous node of the node to be deleted.
     2. Change the next of previous node to the next node of current node.
     3. Free the memory of replaced node.
   • Case 3: The key is not found in the list
     1. In this case, No operation needs to be done.