200k views
21 votes
Hey, I am in need of urgent help! My teacher is REALLY bad at his job (no exaggeration) and if I dont get a 100 on this lab, I will fail the class. Please help me, thank you!!!

This link contains the instructions and classes needed for the lab:
https://www.dropbox.com/sh/469usrw1vctot52/AAARAgfqC63k3OPksAkvdRsGa?dl=0

Please put the code in the Circular List Class, the rest is already done, thanks!

User Hidemyname
by
6.8k points

1 Answer

4 votes

Answer:

public class CircularList

{

private ListNode head; // front of the LinkedList

private ListNode tail; // last node of the LinkedList

private int size; // size of the LinkedList

// constructs a new CircularList

public CircularList()

{

head = tail = null;

size = 0;

}

// returns the size of the array

public int size()

{

return size;

}

// returns whether the list is empty

public boolean isEmpty()

{

return (size == 0);

}

// returns the value of the first node

public Integer first()

{

if (head != null) {

return head.getValue();

}

return -1;

}

// returns the value of the last node

public Integer last()

{

if (tail != null) {

return tail.getValue();

}

return -1;

}

// adds a node to the front of the list

public void addFirst(Integer value)

{

head = new ListNode(value, head);

if (tail == null) {

tail = head;

}

size++;

}

// adds a node to the end of the list

public void addLast(Integer value)

{

ListNode newTail = new ListNode(value, null);

if (tail != null) {

tail.setNext(newTail);

tail = newTail;

} else {

head = tail = newTail;

}

size++;

}

// adds a node at the position pos

public void addAtPos(int pos, Integer value)

{

if (pos == 0) { // Add at the start

addFirst(value);

return;

}

if (pos <= 0 || pos > size) { // Ignore attempts to add beyond the ends

return;

}

if (pos == size) { // Special case, tail has to be adjusted

addLast(value);

return;

}

// size and pos are guaranteed both non-zero

ListNode ptr = head; // ptr is the node before the new one

for(int i=0; i<pos-1; i++) {

ptr = ptr.getNext();

}

ListNode newNode = new ListNode(value, ptr.getNext());

ptr.setNext(newNode);

size++;

}

// removes the first node and returns the value of the removed node or -1 if the list is empty

public Integer removeFirst()

{

Integer retVal = -1;

if (head != null) {

retVal = head.getValue();

head = head.getNext();

size--;

}

if (size == 0) {

head = tail = null;

}

return retVal;

}

// removes the node at position pos and returns the value of the removed node or -1 if pos is not a valid position

public Integer removeNode(int pos)

{

Integer retVal = -1;

if (head == null || pos < 0 || pos >= size) {

return retVal;

}

if (pos == 0) {

return removeFirst();

}

ListNode ptr = head; // ptr is the node before the deleted

for(int i=0; i<pos-1; i++) {

ptr = ptr.getNext();

}

retVal = ptr.getNext().getValue();

if (pos == size-1) { // Is it the last element?

tail = ptr;

tail.setNext(null);

} else {

ptr.setNext(ptr.getNext().getNext());

}

size--;

return retVal;

}

// finds and returns the position of find, or -1 if not found

public int findNode(Integer find)

{

ListNode ptr = head;

for(int pos=0; pos<size; pos++) {

if (ptr.getValue() == find) {

return pos;

}

ptr = ptr.getNext();

}

return -1;

}

// rotates the list by placing the first element at the end

public void rotate()

{

addLast(removeFirst());

}

// returns the list of values in the LinkedList

public String toString()

{

String output = "";

ListNode iter = head;

while(iter != null) {

output += String.format("%d ", iter.getValue());

iter = iter.getNext();

}

return output;

}

}

Step-by-step explanation:

Enjoy. Linked list are always more complex than you expect. It is a good exercise to try once, then start using libraries. Life is too short to debug linked lists!

User Giorgy
by
7.5k points