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;
}
}
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!
