I have scoured the internet and cannot find the answer to my question. I am currently in a data structures course, which is important to this question because I need to make EVERYTHING from scratch. I am currently working on homework and the question is this:
Using a USet, implement a Bag. A Bag is like a USet—it supports the add(x), remove(x), and find(x) methods—but it allows duplicate elements to be stored. The find(x) operation in a Bag returns some element (if any) that is equal to x. In addition, a Bag supports the findAll(x) operation that returns a list of all elements in the Bag that are equal to x.
I have done almost all of it and now when I am trying to test my code it throws a null pointer exception right off the bat. I went through the debugger and although I know where it is failing (when trying to create my array list and fill it with linked lists) I just dont know how to fix it. Here is what the error states:
Exception in thread "main" java.lang.NullPointerException
at Bag.<init>(Bag.java:10)
at Bag.main(Bag.java:198)
because I havent even gotten it to start I obviously dont know of any other errors it will encounter, but I will face those when this is fixed. I appreciate any help.
Reminder: I cannot use pre-built java dictionaries, everything needs to be done from the basics.
Here is my entire code:
public class Bag<T> {
final int ARR_SIZE = 128;
LinkedList[] theArray;
public Bag() {
for (int i = 0; i < ARR_SIZE; i++) {
theArray[i] = new LinkedList();
}
}
public boolean add(T x) {
T element = x;
int hashKey = element.hashCode() % ARR_SIZE;
theArray[hashKey].addFirst(element, hashKey);
return true;
}
public T find(T x) {
T element = x;
int hashKey = element.hashCode() % ARR_SIZE;
return theArray[hashKey].findNode(element).getData();
}
public T findAll(T x) {
T element = x;
int hashKey = element.hashCode() % ARR_SIZE;
System.out.print(theArray[hashKey].findAllElements(element));
return element;
}
public T remove(T x) {
T element = x;
int hashKey = element.hashCode() % ARR_SIZE;
return theArray[hashKey].removeElement(element);
}
public int size() {
return ARR_SIZE;
}
public class Node {
T data;
int key;
Node next;
Node prev;
public Node(T t, int k, Node p, Node n) {
data = t;
key = k;
prev = p;
next = n;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public void display() {
System.out.println(data);
}
}
public class LinkedList {
Node header;
Node trailer;
int size = 0;
public LinkedList() {
header = new Node(null, -1, trailer, null);
trailer = new Node(null, -1, null, null);
header.setNext(trailer);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size() == 0;
}
public void addFirst(T t, int hashKey) {
Node currentLast = header.getNext();
Node newest = new Node(t, hashKey, header, currentLast);
header.setNext(newest);
currentLast.setPrev(newest);
size++;
}
public T add(T t) {
Node currentLast = header.getNext();
Node newest = new Node(t, -1, header, currentLast);
header.setNext(newest);
currentLast.setPrev(newest);
size++;
return newest.getData();
}
public T removeElement(T t) {
if (isEmpty()) {
return null;
}
T element = t;
return removeNode(findNode(element));
}
public T removeNode(Node node) {
if (isEmpty()) {
return null;
}
Node pred = node.getPrev();
Node succ = node.getNext();
pred.setNext(succ);
succ.setPrev(pred);
size--;
return node.getData();
}
public LinkedList findAllElements(T t) {
Node current = header.getNext();
T element = t;
if (isEmpty()) {
return null;
}
LinkedList all = new LinkedList();
while (current != null) {
if (current.getData() == element) {
all.addFirst(element, -1);
} else {
current = current.getNext();
}
}
return all;
}
public Node findNode(T t) {
Node current = header.getNext();
T element = t;
if (isEmpty()) {
return null;
}
while (current.getNext() != null && current.getData() != element) {
current = current.getNext();
}
if (current.getNext() == null && current.getData() != element) {
System.out.println("Does not exist");
}
return current;
}
}
public static void main(String[] args) {
Bag<Integer> bag = new Bag();
bag.add(1);
bag.add(1);
bag.add(2);
bag.add(2);
bag.add(8);
bag.add(5);
bag.add(90);
bag.add(43);
bag.add(43);
bag.add(77);
bag.add(100);
bag.add(88);
bag.add(555);
bag.add(345);
bag.add(555);
bag.add(999);
bag.find(1);
}
}
