_15.51.49.png)
UnrolledLinkedList:
This data structure consists of two classes that work inherently together: The main class UnrolledLinkedList, and a helper class named Node.
At first, I made a base setup for I wanted to prepare myself for a university task that would need some self implementation akin to it. As you can see in https://github.com/feralriosv/Data_Structures_Learning_Project/commit/c1f646646368c13ed1232f0f4b67171890023588, It was not very good coded, but it really helped me a lot when I began de real task.
To practice a little with git commands, I created a new branch to finish the implementation and then ended up merging the branches.
When I began with the task, I immediately noticed that the current method was not optimal, as it needs to iterate through all the Nodes to count the total number of arrays in the UnrolledLinkedList. This implementation results in an O(n) runtime, which could be significantly improved by simply adding an attribute to the class. This attribute would track the addition and removal of Nodes, incrementing and decrementing the count accordingly.
Image: amountArrays()
To optimize this, the assignment of the tail pointer when appending or removing nodes must be precise to ensure that there are no undercounts or overcounts. That is why both push and pop methods had to be changed. As below in Image A, the assignation tail.setNext(newTail) wasn’t really doing the complete job in the push method. The tail would have indeed a next Node, but there missed the opposite connection, that is, newTail.setPrev(tail), as shown in Image B.
It also can be appreciated that in the pop method missed another crucial assignation. Since the tail of the list will always be the last node of it, it is important to set null as next value. Further, when the tail node results to be the head as well, calling tail.getPrev() origins NullPointerException, so it was necessary to handle this condition in the code. Image C shows the result. This implementation, in turn, allowed for correct and more optimal handling of the total array count.
_17.44.48.png)
Image A
_17.52.28.png)
Image B
_18.22.53.png)
Image C
These are the core methods of the class. Once you understand the logic behind the head and tail nodes, as well as their replacement process and the correct handling of additions and removals, the rest of the code becomes easier to implement.
The following method, for example (Image: get(int)), was supposed to return the value of the element at the index given. As mentioned above, the implementation now uses a single attribute to keep track of the total number of arrays. This not only simplifies the logic but also improves the efficiency of the code by avoiding the need to iterate through all the nodes. In addition, careful handling of the head and tail pointers ensures that the list maintains its integrity, even during add and remove operations.
_18.32.34.png)
Image: get(int)
Another functionality was the toString method, which was implemented both in the Node and in the list class. In Node, the method works only on the internal elements, iterating up to (but not including) the last element to avoid adding an extra comma. In the list class, the method works hierarchically, iterating over the nodes, which each receive the same separator.
_18.44.49.png)
Image: Node - toString(String)
_18.45.19.png)
Image: UnrolledLinkedList - toString(String)
It’s important to note that the loop in the list class iterates as long as current is not tail, since in tail we must avoid adding the separator.
Overall, the implementation of this data structure demonstrates the importance of precise pointer management and the value of maintaining auxiliary attributes for optimization. By properly updating the totalArrays attribute and ensuring correct bidirectional linking between nodes, the code achieves both reliability and efficiency.