Java linked list API not allowed.
Is it possible to have a linked list inside a list node? If yes, how do I insert data into the linked list that is in the list node?
List Node class (I tried to add a new linked list into the list node which worked I guess?):
public class ListNode {
public Object data;
public ListNode next;
public LinkedList testLL;
// for normal only head/tails
public ListNode(Object data) {
this.data = data;
this.next = null;
this.testLL = null;
}
// for normal nodes in the middle
public ListNode(Object data, ListNode next) {
this.data = data;
this.next = next;
this.testLL = null;
}
// for nodes that are only head/tails with a linked list extending outward
public ListNode(Object data, LinkedList testLL) {
this.data = data;
this.next = null;
this.testLL = testLL;
}
// for nodes in the middle with a linked list extending outward
public ListNode(Object data, ListNode next, LinkedList testLL) {
this.data = data;
this.next = next;
this.testLL = testLL;
}
}
Linked list code:
public class LinkedList {
private ListNode head;
private ListNode tail;
private Comparator comparator;
private int count = 0;
private LinkedList test;
public LinkedList(Comparator comparator) {
head = tail = null;
this.comparator = comparator;
}
public boolean isEmpty() {
return (head==null);
}
public void addToHead(Object item) {
count++;
if (isEmpty()) {
head = tail = new ListNode(item, test);
} else {
head = new ListNode(item, head, test);
}
}
public void addToTail(Object item) {
count++;
if (isEmpty()) {
head = tail = new ListNode(item, test);
} else {
tail.next = new ListNode(item, test);
tail = tail.next;
}
}
public Object removeFromHead() throws EmptyListException {
Object item = null;
if (isEmpty()) {
throw new EmptyListException();
}
item = head.data;
if (head == tail) // there's only one single node
head = tail = null;
else
head = head.next;
count--;
return item;
}
public Object removeFromTail() throws EmptyListException {
if (isEmpty()) {
throw new EmptyListException();
}
Object item = tail.data;
if (head == tail) { // there is only one node
head = tail = null;
return item;
}
ListNode current = head;
while (current.next != tail)
current = current.next;
tail = current;
tail.next = null;
count--;
return item;
}
// removes duplicate nodes
public void removeDuplicate() throws EmptyListException {
ListNode current = head;
ListNode checker = current.next;
iterateLL:
while (current.next != null) {
// start from head, check data one by one until the data is not the same,
// then go to that data and connect it to current
checkRepeated:
while(checker != null){
if(checker.data.equals(current.data)){
if(checker.next == null){
current.next = null;
break iterateLL;
}
else{
checker = checker.next;
continue checkRepeated;
}
}
else{
current.next = checker;
current = current.next;
checker = current.next;
break checkRepeated;
}
}
}
}
public String toString1() { // original toString method, will not be changed, for backup if anything messed up
String s = "[ ";
ListNode current = head;
while (current != null) {
s += current.data + " ";
current = current.next;
}
return s + "]";
}
public String toString2() {
ListNode current = head;
String s = "\nIdentifiers found:";
while (current != null) {
// start from head, check data one by one until the data is not the same,
// then go to that data and input it into String s
s += "\n" + current.data + current.testLL.toString1();
current = current.next;
}
return s;
}
public int getCount(){
return count;
}
public void insertInOrder (Object item) {
if (isEmpty()) {
head = tail = new ListNode (item);
count++;
} else {
if (comparator.isGreaterThanOrEqualTo(head.data, item)) {
addToHead(item);
} else if (comparator.isLessThanOrEqualTo(tail.data, item)) {
addToTail(item);
} else {
// insert in the middle
ListNode current = head;
while (current.next != null) {
if (comparator.isGreaterThanOrEqualTo(current.next.data, item)) {
ListNode newNode = new ListNode(item, test);
newNode.next = current.next;
current.next = newNode;
count++;
return;
}
current = current.next;
}
}
}
}
public void removeItem (Object item) throws ItemNotFoundException {
if (isEmpty()) {
throw new ItemNotFoundException();
}
if (comparator.isEqualTo(head.data, item))
removeFromHead();
else if (comparator.isEqualTo(tail.data, item))
removeFromTail();
else {
// remove a node in the middle
ListNode current = head;
while (current.next != null) {
if (comparator.isEqualTo(current.next.data, item)) {
current.next = current.next.next;
count--;
return;
}
current = current.next;
}
throw new ItemNotFoundException();
}
}
}
The exceptions are custom exceptions and the comparator is used to make the linked list sorted
The toString2 method will have error in the main program since it says that the linked list in the list node is null, which I don't know how to input data into the linked list in list node
In short: yes, if a node can contain an object of any type, then that type can be LinkedList.
Some improvements you might consider:
Object.getHead() and getTail() to access these nodes without needing to remove them.