Custom linked list in Java

What is linked list?

A linked list is a data structure where each element (node) contains a value and a reference to the next node in the sequence.

Analogy / Think

• Imagine a diary as a form of memory and each page in the diary as a spot where you can write notes.
• Each page in the diary has a page number, which acts like a reference to other pages.
• When you write notes for a particular day, you choose any available empty page in the diary to record those notes.
• The next day, instead of writing on the consecutive page, you simply find any other available empty page in the diary and record your notes there. You also update the previous day's page with this new page number, maintaining a reference so that anybody can navigate to this new page from any previous page.

This way, the diary doesn't need to have notes in consecutive pages; instead, it uses page numbers to keep track of where each set of notes is stored.

Properties

• nodes may not be in consecutive memory locations
• first node is not referenced by any other node and can be marked as a Head
• last node does not reference any other node and can be marked as a Tail
• nodes can be added to removed from any position in the list without any copying or shuffling of elements
• Adv: insertions will be faster than data structures where the nodes need to be in consecutive location
• reaching a node is always in sequence - traverse the list from start till we find the node we are looking for (keep following the address / reference to the next node to traverse the list).
• Disadv: iterating through the list to find elements is slowers in a linked list.

Constraints

• No constraint on the size - can be as large as the memory is available

Operations on the list

• create a new empty list (think: new customLinkedList()) - O(1) since the list is empty
• update the list
• add nodes at any position (think: customLinkedList.add(position p)) - O(n) since in the worst case, we are traversing the whole list to find the end and then add a new node
• remove node from any position (think: customLinkedList.remove(position p)) - O(n) since in the worst case, we are traversing the whole list to find the end and then add a new node
• destroy / delete the list (think: customLinkedList.delete() ) - O(1) Just delete the first node and all other nodes will be orphaned, ready to be garbage collected
• list elements
• list all elements (think: list()) - O(n) since we will have to traverse the whole list
• list elements in a range (think: list(2,8)) - O(n) since in the worst case, the range could be the whole list
• search for an element (think: hasValue() or containsValue() ) - O(n) since in the worst case, we may have to traverse through the whole list