// ListNode.java: node for a linked list
public class ListNode {
public int data;
public ListNode next;
public ListNode(int newdata) {
// would be this way by default
data = newdata;
next = null;
}
// no other constructors used
}
// LinkdedList.java: basic linked list
public class LinkedList {
private ListNode first; // front, top
private ListNode last; // rear
public LinkedList() {
last = null;
first = null;
}
public void addLast(int dataItem) {
// or add to rear, i.e. enqueue
if (last == null) { // empty linked list
last = new ListNode(dataItem);
first = last;
}
else { // case of non-empty linked list
last.next = new ListNode(dataItem);
last = last.next;
}
}
public void addFirst(int dataItem) {
// or add to front, i.e. dequeue, or push
ListNode newNode = new ListNode(dataItem);
newNode.next = first;
first = newNode;
if (last == null) // adding to empty list
last = newNode;
}
public int removeFirst() {
// or pop
int valueToReturn = first.data;
first = first.next;
if (first == null) last = null;
return valueToReturn;
}
public boolean empty() {
return first == null;
}
public void printList() {
// first to last, or front to rear
ListNode temp = first;
if (temp == null) System.out.print("Empty");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public void printReverse() {
printReverse0(first);
System.out.println();
}
public void printReverse0(ListNode temp) {
// last to first, or rear to front
if (temp != null) {
printReverse0(temp.next);
System.out.print(temp.data + " ");
}
}
public int delete(int dataItem) {
// delete from anywhere in list
if (first == null) return -1; // empty
if (first == last) { // 1 item in list
if (first.data == dataItem) {
first = last = null;
return 0;
}
else return -1;
}
// >= 2 items in list
if (first.data == dataItem) {
first = first.next;
return 0;
}
// >= 2 items, first not the one
ListNode old = first;
ListNode curr = first.next;
while (curr != null && curr.data != dataItem) {
curr = curr.next;
old = old.next;
}
if (curr == null) return -1;
// now found at curr
if (curr == last) {
last = old;
last.next = null;
return 0;
}
old.next = curr.next;
return 0;
}
}
| // Stack.java: inherited from linked list
public class Stack extends LinkedList{
public void push(int dataItem) {
addFirst(dataItem);
}
public int pop() {
return removeFirst();
}
// Could add main function here
// for testing. (Not required.)
}
// Queue.java: inherited from linked list
public class Queue extends LinkedList{
public void enqueue(int dataItem) {
addLast(dataItem);
}
public int dequeue() {
return removeFirst();
}
// Could add main function here
// for testing. (Not required.)
}
// ListTest.java: test stack and queue
public class ListTest{
public static void main(String[] args) {
int[] a = {2, 3, 5, 7, 11, 13};
Queue q = new Queue();
for (int i = 0; i < a.length; i++)
q.enqueue(a[i]);
System.out.println("Queue:");
q.printList();
q.printReverse();
int t = q.dequeue();
System.out.print(t + " ");
t = q.dequeue();
System.out.print(t + "\n");
Stack s = new Stack();
for (int i = 0; i < a.length; i++)
s.push(a[i]);
System.out.println("Stack:");
s.printList();
s.printReverse();
t = s.pop();
System.out.print(t + " ");
t = s.pop();
System.out.print(t + "\n");
s.push(11);
s.push(13);
System.out.println("Delete test:");
s.printList();
for (int i = a.length - 1; i >= 0; i--) {
s.delete(a[i]);
s.printList();
}
System.out.println("2nd Delete test:");
for (int i = 0; i < a.length; i++)
s.push(a[i]);
s.printList();
System.out.print(s.delete(1) + " ");
System.out.print(s.delete(8) + " ");
System.out.println(s.delete(15));
System.out.println("3rd Delete test:");
for (int i = 0; i < a.length; i++) {
s.delete(a[i]);
s.printList();
}
}
}
|
