Objective:The purpose of this lab exercise is to create a Singly Linked List data structure . Please note that the underlying implementation should follow with the descriptions listed below.
Instructions: Create the following Linked List Data Structure in your"utils" packageand ONLY use"for loops"for your repetitive tasks. Use the internal generic node class specified below to implement the underlying linked data structures.
Where to place your code in my-api
package.class :utils.SinglyLinkedList
Where to place your test code in my-api
package.class :tests.console.week01.SLLPrintTest
Where to find the JUnit Test code in my-api
package.class :tests.junit.SLLJUnitTest
Task Check List
- ONLY "for" loops should be used within the data structure class. There is anautomatic 30% deduction,if other loops are used.
- The names of identifiers MUST match the names listed in the description below. Deductions otherwise.
- You cannot use any other references as data fields other than first and size.
- The Node class must be generic and a nested class within SinglyLinkedList.
- Complete coding Assignment in your "my-api"GitHub Repository. You will not be graded otherwise and will receive a 0, if not uploaded there.
- Run JUNIT TEST and take a SNAPSHOT of results. Upload PDF of snapshot of yourJUnitTest results to Canvas.
Description
The internal structure of this Linked List is asingly linked Node data structureand should have at a minimum the following specifications:
data fields: The data fields to declare are private and you will keep track of the size of the list with the variable size and the start of the list with the reference variable data.
- firstis a reference variable for the first Node in the list.
- sizekeeps track of the number of nodes in the list of type int. This will allow you to know the current size of the list without having to traversing the list.
constructors: initializes the data fields size and data.
- A constructor that is a default constructor initializes the starting node location “first” and size to a zero equivalent, that is, constructs an empty list.
public SinglyLinkedList()
outer class methods: manages the behavior of the linked nodes.Together, these methods below give the illusion of an index or countable location.
- Validate all methods with indexes. However, you should think critically about where to throw exceptions!
- Implement these methodswithinyour generic Singly Linked List outer class.NOTE : All methods must be implemented according to the description. DEDUCTIONS Apply otherwise.
Method | Description | Header |
| add(item) | uses the append method. This method returns true, if the data was added successfully. | public boolean add(T item) |
| add(index, item) | inserts elements at a given location in the list, front, middle and end. Uses helper methods "append " and "insertBefore" to achieve this. | public void add(int index, T item) |
| append(item) | appends items to the "end" of the list. This is a private helper method. | public void append(T item) |
| checkIndex(index) | checks if the given index is valid. Throws anIndexOutOfBoundsException, if invalid. This is a private helper method. | private void checkIndex(int index) |
| detach(index) | detaches the node at the specified index from list. This is a private helper method.
| private T detach(int index) |
| get(index) | returns the item at the specified position in the list. This method first checks if the index requested is valid. | public T get(int index) |
| insertBefore(index, item) | inserts an item before the non-null node at the specified index in the list. This is a private helper method.
| private void insertBefore(int index, T item) |
isEmpty()
| returns true, if the list is empty, i.e., the list contains no elements. | public boolean isEmpty()
|
| node(index) | returns the address of the node at the given position in the list. This is a private helper method.
| private Node node(int index) |
| remove(index) | removes and returns the item at indicated index. Removal includes index validation, size reduction and detaching the specified node using the "detach" helper method. | public T remove(int index) |
| set(index, item) | replaces the item at the specified position with the one passed. This method checks if the index requested is valid before it does the replacement and returns the replaced item. | public T set(int index, T item) |
size()
| returns the number of elements in the list. | public int size() |
| toString() | displays the contents of the list. | public String toString()
|
Node Data Structure
The generic Linked List class includes a static Node class as a nested class, i.e. astatic innerclass within the Linked List class.
inner class: class inside the body of another class.
Note: This private class does not require access to instance members of the outer class, so it is declaredstatic. This means that the node object won’t be coupled to the outer class object, thus will be more optimal since it won’t require additional heap/stack memory.
data fields:
- data: hold the data stored in each node as is of typeE.
- next: stores the location of the next node in the list.
constructor:
A constructor that receives parameters for data, and prev and calls the second constructor.
public Node(Edata)
A constructor that receives parameters for data, and next.
public Node(Edata, NodeE> next)