Week-04 | Doubly Linked Lists
About
Objective:The purpose of this exercise is to create a Linked List data structure that mimics the behavior of the Java Standard Library Version (Java API). The outcomes/results of using the library features should be identical with your own version (My API). However, the underlying implementation should follow with the descriptions listed below.
Instructions: Create the following Linked List Data Structure with the given description below in yourutils packageand use "for loops" for your repetitive tasks.
Where to find starter code in my-api
package.class :utils.LinkedList
package.class :tests.console.week04.LinkedListTest
Where to find your JUNIT test in my-api
package.class :tests.junit.LinkedListJUnitTest
Nested Class that has to be added to LinkedList class
package.class :utils.LinkedList.Node
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.
- 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 the Linked List is adoubly 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.
- lastis a reference variable for the last 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: The overloaded constructors will initialize 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 LinkedList()
methods: methods that manages the behavior of the linked nodes.
Together, the methods below give the illusion of a index or countable location. Implement these methods within your generic Linked List class.
Method
|
Description
|
Header
|
add(item) |
uses the append method and ensures that there is enough spaces to store each element in the list. Also updates the number of elements in the list by one. This method returns true, if the data was added successfully. |
public boolean add(E item)
|
add(index, item) |
inserts elements at a given location in the list, shifting subsequent elements to the right. Uses the append and insertBefore methods to assist with adding items to the front, back and middle of the list. Updates the number of elements in the list by one. |
public void add(int index, E item)
|
append(item) |
appends elements to the end of the list, but does not update the number of elements. This is a private helper method. |
public void append( E item)
|
checkIndex(index) |
checks if the given index is valid. Validation means that you cannot access indexes where elements have not been placed. Throws anIndexOutOfBoundsException, if invalid. This is a private helper method. |
private void checkIndex(int index)
|
contains(item) |
searches for a specific item within the linked structure and returns true, if the item is in the list. |
public boolean contains(E item)
|
clear()
|
clears list of all elements, returns size back to zero. |
public void clear()
|
detach(index) |
detaches the node at the specified index from list and returns the deleted element, but does not reduce the size of the list. This is a private helper method.
|
private E 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 E get(int index)
|
indexOf(item) |
searches for a specific item within the linked structure and returns the first occurrence (i.e. index location) in the list, otherwise returns -1, if NOT found. |
public int indexOf(E item)
|
insertBefore(index, item) |
inserts an item before the non-null node at the specified index in the list. Traverses the list to find this node. This method also checks for insertions at the start and end of the list, as well as when empty. This is a private helper method.
|
private void insertBefore(int index, E item)
|
isEmpty()
|
returns true, if the list is empty, i.e., the list contains no elements. |
public boolean isEmpty()
|
node(index) |
returns a reference to the node at the given position in the list. This node traverses the list in two directions from front to middle and back to middle. This is a private helper method.
|
private Node node(int index)
|
remove(index) |
removes the item at the given position in the list for a valid index. Checks for valid index before it proceeds with removal. Shifts subsequent elements to the left and returns the item removed. The number of elements in the list is reduced by one. |
public E remove(int index)
|
remove(item) |
removes the first occurrence of the specified item from the list, if present. Shifts subsequent elements to the left and returns true, if the item is removed. The number of elements in the list is reduced by one. |
public boolean remove(E item)
|
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 E set(int index, E item)
|
size()
|
returns the number of elements in the list. |
public int size()
|
toString() |
displays the contents of the list according to the same format at shown in the Java API. |
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 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.
- prev: stores the location of the previous node in the list.
constructor:
A constructor that receives parameters for data, and prev and calls the second constructor.
public Node(NodeE> prev, E data)
A constructor that receives parameters for data, next and prev.
public Node(NodeE> prev, E data, NodeE> next)
JUNIT Jupiter Tests
The instructorwill provide a JUnit 5 Testfor you to test your Linked List data structure.
Run it and take a SNAPSHOT of results. Upload as a PDF to Canvas.