Assignment #$4-$ Circular

Background:

Linked List is a sequence of links which contains items. Each node consists of its own data and the address of the next node and forms a chain. The purpose of this assignment is to get familiar with the linked list structure along with generic data type. In this assignment, you will involve constructing Java functions that use linked nodes and list references to operate the elements in the list.

Objectives:

This assignment will assess your mastery of the following objectives:

To construct two circular linked lists that are unsorted and sort.

To understand how node references work in the linked lists.

To perform basic operations in the linked list.

Rules and Explanations:

The original linked list has a reference to the first element $($head$)$ of the list. In this assignment, you are ask to construct a circular linked list that has a reference to the last element $($tail$)$ of the list. To maintain the concept of circular, we do not want the last element points to nowhere, and because of that reason, we will have the last element $($tail$)$ points back to the first element $($head$).$

The list structure must maintain the reference to the last element of the list after every single operation called. The only case we have a list node null when the list is empty, the tail reference is pointing to null. The last element $($tail$)$ must be linked to the first element $($head$)$ of the list. There is an interface called List that has a single generic data type "Type". The List provides prototypes as following:

Method Description

public int getSize$()$ The method returns the number of elements in the list.

public boolean isEmpty$()$ The method returns true if the list is empty otherwise false.

public boolean contains$($Type value$)$ The method returns true if the list contains the given value otherwise false.

public void insert$($Type value$)$ The method insert the given value into the list.

public void clear$()$ The method removes all elements from the list.

public String toString$()$ The method returns the list in string format. For example: $"[1,2,3,4]"$

public Type value remove$($Type value$)$ The method removes and returns the given value from the list.

public int getIndex$($Type value$)$ The method returns the index of the given value. $($return $-1$ if the value is not found$)$

public Type removeAtIndex$($int index$)$ The method removes and returns the value at the given index.

public void set$($int index, Type value$)$ The method assigns the given value to the list at the given index.

public Type get$($int index$)$ The method returns the value of the element at the given index.

public Iterator iterator$()$ The method returns the iterator of the list.