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:
Circularly Linked List
/**
* CircularlyLinkedList.java
*
* @description Creates a class for circularly linked lists
*/
public class CircularlyLinkedList< Type > {
// attributes
private Node< Type > 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< Type > 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< Type > 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< Type > 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< Type > 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< Type > prevN = getNthNode(n - 1);
Node< Type > newNode = new Node< Type >(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< Type > other) {
// check if size if equal
if (size != other.size()) {
return false;
}
Node< Type > curr1 = tail;
Node< Type > 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< Type > getNthNode(int n) {
// if n is more then size then return null
if (n > size) {
return null;
}
// forward n times from tail
Node< Type > 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< Type > {
// attributes - for Node class
private Type entry;
private Node< Type > nextNode; // acts as pointer to another node
// methods - for Node Class
/** constructor for node defines entry and pointer */
public Node(Type e, Node< Type > 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< Type > getNextNode() {
return nextNode;
}
/**
* method to reset the nextNode
*
* @params newNextNode another node to point to
*/
public void setNextNode(Node< Type > newNextNode) {
nextNode = newNextNode;
}
}// end of node class
}
Doubly Linked List
/**
* DoublyLinkedList.java
*
* @description Creates a class for doubly linked lists
*/
import java.lang.reflect.Type;
public class DoublyLinkedList{
//attributes
private Node headBookEnd; //- > no information ever held
private Node tailBookEnd; //- > no information ever held
private int size = 0;
/** empty constructor */
public DoublyLinkedList(){
//set up headBookEnd and tailBookEnd
headBookEnd = new Node(null, null, null);
tailBookEnd = new Node(null, null, headBookEnd);
headBookEnd.setNextNode(tailBookEnd);
}
/** return the size of the linked list
@return size */
public int size(){
return size;
}
/** return true if linked list is empty, otherwise returns false */
public Boolean isEmpty(){
return (size == 0);
}
/** returns entry of the head node
@return
*/
public Type first(){
if (isEmpty())
return null;
// the book end never has information, but the following node should
return headBookEnd.getNextNode().getEntry();
}
/** returns entry of the tail node
@return
*/
public Type last(){
if (isEmpty())
return null;
return tailBookEnd.getPreviousNode().getEntry();
}
/** add element to the beginning of the linked list
@params newEntry */
public void addFirst(Type newEntry){
insertNode(newEntry, headBookEnd.getNextNode(), headBookEnd);
}
/** add element to the end of the linked list
@params newEntry */
public void addLast(Type newEntry){
insertNode(newEntry, tailBookEnd, tailBookEnd.getPreviousNode());
}
/**
*/
public void insertNode(Type newEntry, Node nextNode,
Node previousNode){
// ensure that nextNode and previousNode are next to each other
Node newNode = new Node(newEntry, nextNode,
previousNode);
previousNode.setNextNode(newNode);
nextNode.setPreviousNode(newNode);
size++;
}
/** remove first entry of the linked list
@return entry of first node */
public Type removeFirst(){
// no entries
if (isEmpty()){
return null;
}
Node oldFirstNode = headBookEnd.getNextNode();
headBookEnd.setNextNode(oldFirstNode.getNextNode());
oldFirstNode.getNextNode().setPreviousNode(headBookEnd);
size--;
return oldFirstNode.getEntry();
}
/** remove last entry of the linked list
@return entry of last node */
// approach is same as remove first
public Type removeLast(){
// no entries
if (isEmpty()){
return null;
}
// take the last element in the list
Node oldLastNode = tailBookEnd.getPreviousNode();
// make tailbookend's previous as second last element
tailBookEnd.setPreviousNode(oldLastNode.getPreviousNode());
// make second last's next as tailbookend
// this makes second last as last element in the list
oldLastNode.getPreviousNode().setNextNode(tailBookEnd);
// decrease the size
size--;
// return the deleted entry
return oldLastNode.getEntry();
}
//this function starts from head and traverse till nth element and
// return the nth entry
public Type seeEntry(int n) {
// n is greater tha size of list, return null
if (n >=size()) {
return null;
}
// make a temp node to store head, as we going to traverse list from head
Node temp = headBookEnd;
for (int i=0;i< n;i++) {
// in each loop iteration, move to next node of the list
// so after n iteration, we reach at nth node
temp = temp.getNextNode();
}
// return entry of nth node
return temp.getEntry();
}
//this function starts from head and traverse till nth element and
// insert the new entry after nth node
public void insert(Type newEntry, int n) {
// n is greater tha size of list, return null
if (n >size()) {
return;
}
// make a temp node to store head, as we going to traverse list from head
Node temp = headBookEnd;
for (int i=0;i< n;i++) {
// in each loop iteration, move to next node of the list
// so after n iteration, we reach at nth node
temp = temp.getNextNode();
}
// now call insert node where entry is newEntry,
// previous node is the nth node which is temp and
// next node is the n+1th node
insertNode(newEntry, temp, temp.getNextNode());
}
//this function starts from head and traverse till nth element and
// return the nth node
public Type getNthNode(int n) {
// n is greater tha size of list, return null
if (n >=size()) {
return null;
}
// make a temp node to store head, as we going to traverse list from head
Node temp = headBookEnd;
for (int i=0;i< n;i++) {
// in each loop iteration, move to next node of the list
// so after n iteration, we reach at nth node
temp = temp.getNextNode();
}
// return nth node
return temp.getEntry();
}
// this function get doubly linked list as input parameter and
// compare that list with the current list
// current list means the list which calls the function
public boolean equals(DoublyLinkedList doublyLinkedList) {
// if size is not same, return false
if (size() != doublyLinkedList.size()) {
return false;
}
// if both list are empty, return true
if (isEmpty() && doublyLinkedList.isEmpty()) {
return true;
}
// make a temp node to store head, as we going to traverse list from head
Node temp1 = headBookEnd.getNextNode();
Node temp2 = doublyLinkedList.headBookEnd.getNextNode();
for (int i=0;i< size();i++) {
// if any one entry don't match, return false
if (temp1.getEntry()!= temp2.getEntry()) {
return false;
}
// move to next node
temp1 = temp1.getNextNode();
temp2 = temp2.getNextNode();
}
// if every entry match, return true
return true;
}
//*********************** NODE CLASS *********************************
// private subclass defining a node
private static class Node{
//attributes - for Node class
private Type entry;
private Node nextNode;
private Node prevNode;
//methods - for Node Class
/** constructor for node defines entry and pointer */
public Node(Type e, Node nextNode, Node prevNode){
entry = e;
this.nextNode = nextNode;
this.prevNode = prevNode;
}
/** 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 move to previous node
@return prevNode
*/
public Node getPreviousNode() {
return prevNode;
}
/** method to reset the nextNode
@params newNextNode another node to point to
*/
public void setNextNode(Node newNextNode) {
nextNode = newNextNode;
}
/** method to reset the prevNode
@params newPrevNode another node to point to
*/
public void setPreviousNode(Node newPrevNode) {
prevNode = newPrevNode;
}
}// end of node class
}