please help me fix this add method for my soreteddoublylinked list class as it i
ID: 3810229 • Letter: P
Question
please help me fix this add method for my soreteddoublylinked list class as it is supposed to do as it suggests but i cant get it right what am i doing wrong?
/**Inserts the specified element at the correct position in the sorted list.
* Notice we can insert the same element several times.
* Your implementation must traverse the list only once in order to perform the insertion.
* Do not implement this method using iterators.
* Notice that you don't need to call any of the super class methods in order to implement this method.
* @param data -the data to be added to the list
* @return a reference to the current object
*/
public SortedDoubleLinkedList<T> add(T data) {
/*if (data == null) {
return null;
}
Node <T>newnode = new Node<T>(data, null, null);
if (head == null) {
// The list was empty
head = tail = new Node<T>(data, head, tail);
} else {
// Check if it needs to go right at the head
if (comparator.compare(data, head.getData()) <= 0) {
newnode.setNext(head);
head = newnode;
}
// Check if it needs to go right at the tail
else if (comparator.compare(data, tail.getData()) >= 0) {
tail.setNext(newnode);
tail = newnode;
} else {
// It needs to be inserted into the middle of the list
Node <T>next = head.getNext();
Node<T> prev = head;
while (comparator.compare(data, next.getData()) > 0) {
prev = next;
next = next.getNext();
}
// Do the actual insertion
prev.setNext(newnode);
newnode.setNext(next);
}
}
size++;*/
Node <T>nptr = new Node<T>(data, null, null);
Node <T>tmp, ptr;
boolean ins = false;
if(head == null)
head = nptr;
else if(comparator.compare(data, head.getData()) <= 0)
{
nptr.setNext(head);
head.setPrev(nptr);
head = nptr;
}
else
{
tmp = head;
ptr = head.getNext();
while(ptr != null)
{
if(comparator.compare(data, head.getData()) <= 0)
{
tmp.setNext(nptr);
nptr.setPrev(tmp);
nptr.setNext(ptr);
ptr.setPrev(nptr);
ins = true;
break;
}
else
{
tmp = ptr;
ptr = ptr.getNext();
}
}
if(!ins)
{
tmp.setNext(nptr);
nptr.setPrev(tmp);
}
}
size++;
return this;
}
Explanation / Answer
You are doing it right logically, there is just a small thing you need to check.
First, I recommend you to use the code you have commented in the starting of your add() function.
The code is completely as per the logic. You just need to take care of 'previous' of the nodes at insertion because it is the doubly linked list. Every other line and the logic are exact, so I would tell you use that commented portion if you can with these modifications:
public SortedDoubleLinkedList<T> add(T data) {
if (data == null) {
return null;
}
Node <T>newnode = new Node<T>(data, null, null);
if (head == null) {
// The list was empty
head = tail = new Node<T>(data, head, tail);
} else {
// Check if it needs to go right at the head
if (comparator.compare(data, head.getData()) <= 0) {
newnode.setNext(head);
head.setPrev(newnode);
newnode.setPrev(tail);
tail.setNext(newnode);
head = newnode;
}
// Check if it needs to go right at the tail
else if (comparator.compare(data, tail.getData()) >= 0) {
tail.setNext(newnode);
newnode.setPrevious(tail);
newnode.setNext(head);
head.setPrev(newnode);
tail = newnode;
} else {
// It needs to be inserted into the middle of the list
Node <T>next = head.getNext();
Node<T> prev = head;
while (comparator.compare(data, next.getData()) > 0) {
prev = next;
next = next.getNext();
}
// Do the actual insertion
prev.setNext(newnode);
newnode.setPrev(prev);
newnode.setNext(next);
next.setPrev(newnode);
}
}
size++;
return this;
}
Check all the underlined lines. Here, you have assigned every node the appropriate next pointer, you are inserting them using sorted manner as well, but as this is a doubly linked list, you need to make sure that you properly handle the previous nodes as well. For example, if you do tail->next = newnode then you should also do newnode->prev = tail at every place.
I have modified the code as per that. The reason I suggested the commented portion of code to use is because it is so well documented and if you can use that, it has better naming conventions as well.
If you can't use that portion of code, please comment I will modify the second part you wrote, that's not an issue for sure. As I said, just to make sure you get better result, I used the commented portion.
Please comment if there is any query. Thank you. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.