Instructions
Objective
Write a java homework program to work with methods.
Requirements and Specifications
After reviewing the code, provide a high-level description of how each of the listed methods performs its individual task. This is separate from the comment above each method, which describes what the method does, not how it does it. The description should NOT be a line-by-line rehashing of the code, but just a high-level explanation of how it is intended to work. This can be handwritten and supplemented with pictures, for example by explaining the process using drawings of a hypothetical linked list, but it can be just a couple sentences for each method. As long as it explains how it works. Do this for both files.
The methods referred to and what they do:
seeEntry()
- Takes in an integer, n, and returns the entry at the nth node in the linked list (assuming the linked list has at least n entries--if it does not, return null). This method should NOT change the linked list.
removeLast()
- Removes the last node of the linked list and returns its entry.
insert()
- inserts that node as the nth node.
- creates a new node using the entry and
- takes in two pieces of information: an entry and an integer, n,
equals()
- Determines if two doubly linked lists are equal
getNthNode()
- Takes in an integer n and returns the nth node
Source Code
/**
* CircularlyLinkedList.java
*
* @description Creates a class for circularly linked lists
*/
public class CircularlyLinkedList {
// attributes
private Node tail = null; // this is our first AND last node
private int size = 0;
/** empty constructor */
public CircularlyLinkedList() {
}
/**
* return the size of the linked list
*
* @return size
*/
public int size() { // size() or length() are acceptable language
return size;
}
/** return true if linked list is empty, otherwise returns false */
public Boolean isEmpty() { // make sure we cannot have a bunch of nulls
return (size == 0);
}
/**
* returns entry of the head node
*
* @return head.getEntry()
*/
public Type first() {
if (!isEmpty())
return tail.getNextNode().getEntry();
// grab the entry just after the dail
return null; // only happens if the linked list is empty
}
/**
* returns entry of the tail node
*
* @return tail.getEntry()
*/
public Type last() {
if (!isEmpty())
return tail.getEntry();
return null; // only happens if the linked list is empty
}
/**
* it rotates the circularly linked list by shifting the tail to the next node
*/
public void rotate() {
if (!isEmpty()) {
tail = tail.getNextNode();
} else {// otherwise, it is empty
System.out.println("Circularly Linked list empty; nothing " + "has changed");
}
}
/**
* add element to the beginning of the linked list
*
* @params newEntry of the declared type of the CircularlyLinkedList
*/
public void addFirst(Type newEntry) {
if (isEmpty()) {
tail = new Node<>(newEntry, null);
tail.setNextNode(tail);
} else {
Node newNode = new Node<>(newEntry, tail.getNextNode()); // error if empty!
tail.setNextNode(newNode);
}
size++;
}
/**
* add element to the end of the linked list
*
* @params newEntry of the declared type of the SinglyLinkedList
*/
public void addLast(Type newEntry) {
Node newTailNode;
if (isEmpty()) {
newTailNode = new Node<>(newEntry, null);
newTailNode.setNextNode(newTailNode);
} else {
newTailNode = new Node<>(newEntry, tail.getNextNode());
tail.setNextNode(newTailNode);
}
tail = newTailNode;
size++;
}
/**
* remove first entry of the linked list
*
* @return entry of first node
*/
public Type removeFirst() {
// no entries
if (isEmpty()) {
return null;
}
Type entry = tail.getNextNode().getEntry();
// at least two entries
if (size == 1) {
tail = null;
} else {
tail.setNextNode(tail.getNextNode().getNextNode());
}
size--;
return entry;
}
/**
* Gets entry of nth node
* @param n
* @return The entry
*/
Type getEntry(int n) {
// get the Nth node
Node nth = getNthNode(n);
// if null then return null
if (nth == null) {
return null;
}
// else return the entry of node
return nth.getEntry();
}
/**
* Removes the last node from list
* @return Entry at last node before deletion
*/
Type removeLast() {
// last one is the tail
// if no entry then return null
if (isEmpty()) {
return null;
}
Type entry = tail.getEntry();
// if size is 1
if (size == 1) {
tail = null;
} else {
// get node previous to tail, n -1 th
Node prevTail = getNthNode(size - 1);
// set its next to next of tail
prevTail.setNextNode(tail.getNextNode());
// update tail
tail = prevTail;
}
size--;
return entry;
}
/**
* Inserts a entry at nth position
* @param newEntry
* @param n
*/
public void insert(Type newEntry, int n) {
// if empty then add to first
if(isEmpty()) {
addFirst(newEntry);
}
// if n is greater then size + 1 then add to last
if (n > size + 1) {
addLast(newEntry);
}
else {
// get n - 1 th node
Node prevN = getNthNode(n - 1);
Node newNode = new Node(newEntry, prevN.getNextNode());
// add after the node
prevN.setNextNode(newNode);
// if n == size + 1 then update tail
if (n == size + 1) {
tail = newNode;
}
size++;
}
}
/**
* Compares two list to check if they are Equal
* @param other
* @return boolean
*/
public boolean equals(CircularlyLinkedList other) {
// check if size if equal
if (size != other.size()) {
return false;
}
Node curr1 = tail;
Node curr2 = other.tail;
// check the contents
for (int i = 0; i < size; i++ ) {
// if not equal return false
if (curr1.getEntry() != curr2.getEntry()) {
return false;
}
// update the pointers
curr1 = curr1.getNextNode();
curr2 = curr2.getNextNode();
}
// all matched
return true;
}
/**
* Returns the nth node
* @param n
* @return nth node
*/
public Node getNthNode(int n) {
// if n is more then size then return null
if (n > size) {
return null;
}
// forward n times from tail
Node curr = tail;
for (int i = 0; i < n; i++) {
curr = curr.getNextNode();
}
// return curr
return curr;
}
// *********************** NODE CLASS *********************************
// private subclass defining a node
private static class Node {
// attributes - for Node class
private Type entry;
private Node nextNode; // acts as pointer to another node
// methods - for Node Class
/** constructor for node defines entry and pointer */
public Node(Type e, Node nextNode) {
entry = e;
this.nextNode = nextNode;
}
/**
* constructor for node defines entry and pointer
*
* @return entry
*/
public Type getEntry() {
return entry;
}
/**
* method to move to next node
*
* @return nextNode
*/
public Node getNextNode() {
return nextNode;
}
/**
* method to reset the nextNode
*
* @params newNextNode another node to point to
*/
public void setNextNode(Node newNextNode) {
nextNode = newNextNode;
}
}// end of node class
}