Question

Modify the classes so that it accepts integers instead of characters. (If you understand the concept of generic classes, convert the Node and Linked List classes to a generic so that they can be instantiated with either integers or characters)

JAVA Code

class aNode {

char data;
aNode next;

aNode(char mydata) { // Constructor
data = mydata;
next = null;
}
};
//-----------------------------------------------------

class linkedList {

aNode head; // Head of the linked list
int size;

linkedList() { // Constructor
head = null;
size = 0;
}
//-----------------------------------------------------

public void insert_at_beginning(char value) {
aNode newNode = new aNode(value); // create aNew node
newNode.next = head;
head = newNode;
size++;
}
//-----------------------------------------------------

public void insert_at_end(char value) {
aNode newNode = new aNode(value); // create aNew node
if (isEmpty()) {
newNode.next = head;
head = newNode;
size++;
} else {
//find the last node
aNode ptr;
ptr = head;
while (ptr.next != null) {
ptr = ptr.next;
}
ptr.next = newNode; //add the node to the end
size++;
}
}
//-----------------------------------------------------

public void insert_after(char value, char searchValue) {
if (isEmpty()) {
System.out.println("Linked List is empty, no way to insert " + value + " after " + searchValue);
} else {
//find the node with searchValue
aNode ptr;
boolean found = false;
ptr = head;
while (ptr != null && found == false) {
if (ptr.data == searchValue) {
found = true;
} else {
ptr = ptr.next;
}
}
if (ptr == null) {
System.out.println("Did not find " + searchValue + "Nothing Inserted");
} else {
aNode newNode = new aNode(value); // create aNew node
newNode.next = ptr.next;
ptr.next = newNode; //add the node after the searchValue
size++;
}
}
}
//-----------------------------------------------------
// Delete the first node with the value

public void delete(char deleteValue) {
if (isEmpty()) {
System.out.println("Linked List is empty, nothing to delete");
} else {
aNode deletePtr = head; // create a reference to head
if (head.data == deleteValue) {
head = head.next; // remove the head
deletePtr = null; // make the node available for garbage collection.
size--;
} else {
aNode prevPtr;
deletePtr = prevPtr = head;
boolean found = false;
//find the value to be deleted
while (deletePtr != null && found == false) {
if (deletePtr.data == deleteValue) { // Read about the difference between == and .equals()
found = true;
prevPtr.next = deletePtr.next;
deletePtr = null; // make deletePtr available to garbage collection
size--;
} else {
prevPtr = deletePtr;
deletePtr = deletePtr.next;
}
}
if (found == false) {
System.out.println("Not able to find/delete " + deleteValue + " in the Linked List");
}
}
}
}
//-----------------------------------------------------

public boolean isEmpty() {
if (head == null) {
return (true);
} else {
return (false);
}
}
//-----------------------------------------------------

public void print() {
aNode ptr;
ptr = head;
System.out.print("Head--> ");
while (ptr != null) {
System.out.print(ptr.data + " --> ");
ptr = ptr.next;
}
System.out.println("NULL");
}
//-----------------------------------------------------

public int getSize() {
return (size);
}
//-----------------------------------------------------

public void freeAll() {

aNode freePtr = head;
while (head != null) {
head = head.next;
// the next two lines are unnecessary, but are included for
// illustration of how memory is freed up
//
freePtr = null; // make the node available for garbage collector
freePtr = head; // now let the freePtr to the new head
}
head = null;
size = 0;

Answer 1

class Node<T> {

T data;

Node<T> next;

Node(T mydata) { // Constructor

data = mydata;

next = null;

}

};

//-----------------------------------------------------

class LinkedList<T> {

Node<T> head; // Head of the linked list

int size;

LinkedList() { // Constructor

head = null;

size = 0;

}

//-----------------------------------------------------

public void insert_at_beginning(T value) {

Node<T> newNode = new Node<T>(value); // create aNew node

newNode.next = head;

head = newNode;

size++;

}

//-----------------------------------------------------

public void insert_at_end(T value) {

Node<T> newNode = new Node<T>(value); // create aNew node

if (isEmpty()) {

newNode.next = head;

head = newNode;

size++;

} else {

//find the last node

Node<T> ptr;

ptr = head;

while (ptr.next != null) {

ptr = ptr.next;

}

ptr.next = newNode; //add the node to the end

size++;

}

}

//-----------------------------------------------------

public void insert_after(T value, T searchValue) {

if (isEmpty()) {

System.out.println("Linked List is empty, no way to insert " + value + " after " + searchValue);

} else {

//find the node with searchValue

Node<T> ptr;

boolean found = false;

ptr = head;

while (ptr != null && found == false) {

if (ptr.data == searchValue) {

found = true;

} else {

ptr = ptr.next;

}

}

if (ptr == null) {

System.out.println("Did not find " + searchValue + "Nothing Inserted");

} else {

Node<T> newNode = new Node<T>(value); // create aNew node

newNode.next = ptr.next;

ptr.next = newNode; //add the node after the searchValue

size++;

}

}

}

//-----------------------------------------------------

// Delete the first node with the value

public void delete(T deleteValue) {

if (isEmpty()) {

System.out.println("Linked List is empty, nothing to delete");

} else {

Node<T> deletePtr = head; // create a reference to head

if (head.data == deleteValue) {

head = head.next; // remove the head

deletePtr = null; // make the node available for garbage collection.

size--;

} else {

Node<T> prevPtr;

deletePtr = prevPtr = head;

boolean found = false;

//find the value to be deleted

while (deletePtr != null && found == false) {

if (deletePtr.data == deleteValue) { // Read about the difference between == and .equals()

found = true;

prevPtr.next = deletePtr.next;

deletePtr = null; // make deletePtr available to garbage collection

size--;

} else {

prevPtr = deletePtr;

deletePtr = deletePtr.next;

}

}

if (found == false) {

System.out.println("Not able to find/delete " + deleteValue + " in the Linked List");

}

}

}

}

public boolean isEmpty() {

if (head == null) {

return (true);

} else {

return (false);

}

}

public void print() {

Node<T> ptr;

ptr = head;

System.out.print("Head--> ");

while (ptr != null) {

System.out.print(ptr.data + " --> ");

ptr = ptr.next;

}

System.out.println("NULL");

}

public int getSize() {

return (size);

}

public void freeAll() {

Node<T> freePtr = head;

while (head != null) {

head = head.next;

freePtr = null; // make the node available for garbage collector

freePtr = head; // now let the freePtr to the new head

}

head = null;

size = 0;

}

};

class LinkedListMain {

public static void main(String args[]) {

LinkedList<Integer> l = new LinkedList<Integer>();

l.insert_at_beginning(1);

l.insert_at_beginning(2);

l.insert_after(3, 1);

l.print();

LinkedList<Character> l1 = new LinkedList<Character>();

l1.insert_at_beginning('a');

l1.insert_at_beginning('b');

l1.insert_after('c', 'a');

l1.print();

}

}