In Computer Science one of the most basic and fundamental data structures is the linked list, which functions similarly to an array. The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation of any other elements.
In some programming languages the size of an array is a concern and one of the ways to overcome that problem and allow dynamically allocated data is using linked lists.
Structure of a Linked List
A linked list is a linear collection of data elements called nodes that “point” to the next node by means of a pointer.
Each node holds a single element of data and a link or pointer to the next node in the list.
A head node is the first node in the list, a tail node is the last node in the list. Below is a basic representation of a linked list:
[ NODE(head) ] -> [ NODE ] -> [ NODE(tail) ] -> null
For a more thorough explanation, use these resources:
You will need two classes or factories:
LinkedListclass / factory, which will represent the full list.
Nodeclass / factory, containing a
valuefunction and a link to the
nextNode, set both as
Build the following functions in your linked list class:
append(value)adds a new node containing
valueto the end of the list
prepend(value)adds a new node containing
valueto the start of the list
sizereturns the total number of nodes in the list
headreturns the first node in the list
tailreturns the last node in the list
at(index)returns the node at the given
popremoves the last element from the list
contains(value)returns true if the passed in value is in the list and otherwise returns false.
find(value)returns the index of the node containing value, or null if not found.
toStringrepresents your LinkedList objects as strings, so you can print them out and preview them in the console. The format should be:
( value ) -> ( value ) -> ( value ) -> null
insertAt(value, index)that inserts a new node with the provided
valueat the given
removeAt(index)that removes the node at the given
Extra Credit Tip: When you insert or remove a node, consider how it will affect the existing nodes. Some of the nodes will need their
nextNode link updated.