Doubly-linked list program with delete functions

Question

I'm starting to learn Java (started with C++), and still getting to get used to the syntax and whatnot. For practice, I made a doubly-linked list program. Is there any way this could be improved at all, or is this okay code?

// Doubly Linked-List Practice
package doublylinkedlist;
public class DoublyLinkedList {
node head, tail;
class node // Creates node class
{
 double num;
 node next;
 node prev;
 public node()
 {
 num = 0;
 next = null;
 prev = null;
 }
 public node (double p)
 {
 num = p;
 next = null;
 prev = null;
 }
}
public void append(double x) // Appends data to list
{
 node p = new node(x);
 if (head == null) // Creates head node if empty list
 {
 head = p;
 tail = p;
 return;
 }
 p.prev = tail; // Skips to end of list and appends
 tail.next = p;
 tail = p;
 return;
}
public void showF() // Displays list forward
{
 for (node q = head; q != null; q = q.next)
 System.out.print(q.num + " ");
 System.out.println();
}
public void showR() // Displays list in reverse
{
 for (node q = tail; q != null; q = q.prev)
 System.out.print(q.num + " ");
 System.out.println();
}
public double findAvg()
{
 double mean = 0, total = 0;
 int i = 0;
 for (node p = head; p != null; p=p.next)
 { 
 total += p.num;
 ++i;
 }
 return(mean = total/i);
}
public void delete(double x) // Deletes a single node
{ 
 node p = new node(x);
 node temp = head;
 node pre, nex;
 if (head.num == p.num) // If head node needs to be removed
 {
 head = head.next;
 return;
 }
 while (temp != null) // If a node in between is to be deleted
 {
 if (p.num == temp.num)
 {
 System.out.println("Node found! Deleting " + x + "...");
 temp.prev.next = temp.next;
 temp.next.prev = temp.prev;
 return;
 }
 else temp = temp.next;
 }
 if (tail.num == p.num) // If tail is to be deleted
 {
 tail = tail.prev;
 return;
 }
}
public void deleteMore(double x) // Removes all nodes of certain key
{
 node temp = head;
 if(head == null) // If list is empty 
 {
 System.out.println("Empty list!");
 return;
 }
 while (head != null && head.num > x) // If head node needs to be deleted
 {
 head = head.next;
 head.prev = null;
 temp = head;
 }
 while(temp !=null) // Every remaining occurrence to be removed
 {
 if(temp.num > x)
 {
 if (temp.num == tail.num) // If tail node needs to be removed
 {
 tail = tail.prev;
 tail.next = null;
 temp = tail;
 } else
 {
 temp.prev.next = temp.next;
 temp.next.prev = temp.prev;
 }
 } 
 temp = temp.next;
 }
}
public static void main(String[] args) {
 DoublyLinkedList myList = new DoublyLinkedList();
 double[] arr = {600.0, 100.0, 10.0, 15.0, 20.0, 200.0, 30.0, 40.0, 300.0, 350.0, 400.0, 500.0};
 for (int i = 0; i < arr.length; ++i)
 myList.append(arr[i]);
 System.out.println("Here's your list foreward...");
 myList.showF();
 System.out.println("Average = " + myList.findAvg());
 System.out.println("Removing all excess averages...");
 myList.deleteMore(myList.findAvg());
 System.out.println("Here's your revised list");
 myList.showF();
 System.out.println("And here's your list in reverse");
 myList.showR();
 System.out.println("Removing 30, just because I can");
 myList.delete(30.0);
 myList.showF();
}
}

• AJNeufeld: You have bugs in delete(x). If you delete the head node, the next node’s prev still points to it. If there was only 1 node, tail will still point to it. If you delete the last node, temp.next.prev is a NullPointerException. You need more testing of deleteMore(x), it has bugs too! (Try adding a 500.0 in the middle of the list!)
• Nghia Do: What Java version you are using?

Answer 1

Comments in mostly top-down order.

---

class node // Creates node class

Classes in Java should begin with an uppercase letter. Ie) class Node.

As it stands, this class can only be used inside DoublyLinkedList, so it should be declared private. Ie) private class Node.

As a non-static inner class, it implicitly contains a pointer to the DoublyLinkedList object. You never use this, nor with your current implementation do you need to use it. It is just taking up extra space. You can get rid of it by declaring the class static. Ie) private static class Node.

---

public node()
{
 num = 0;
 next = null;
 prev = null;
}

This constructor is never used, so probably should be deleted.

If you did want to keep it, you should use constructor chaining, so you don't have to repeat initializations. Such as:

public node()
{
 this(0); // Calls node::node(double) constructor
}

---

public double findAvg()
{
 double mean = 0, total = 0;
 ...
 return(mean = total/i);
}

1. The parenthesis are not needed.
2. Possible division by zero, if called on an empty list.
3. Assignment to mean is unnecessary. You can remove the assignment and the mean variable.

---

public void delete(double x) // Deletes a single node
{ 
 node p = new node(x);

There is no need to create a node here. You are looking for a node which contains the value x. Wrapping x in a node and then needing to refer to p.num in tests added complexity for no gain.

 node temp = head;
 node pre, nex;

pre and nex are unused an should be deleted.

 if (head.num == p.num) // If head node needs to be removed

NullPointerException if the list is empty.

 {
 head = head.next;

What of .prev of the new head? It still points to the removed node. But if there was only one node in the list, head is now null, and tail is still pointing to the removed node.

 return;
 }
 while (temp != null) // If a node in between is to be deleted

Actually, this will loop for all the nodes, not just the ones "in between". You will be testing the head node a second time. And it will test the last tail node as well.

 {
 if (p.num == temp.num)
 {
 System.out.println("Node found! Deleting " + x + "...");
 temp.prev.next = temp.next;
 temp.next.prev = temp.prev;

Fortunately, if the head node matched, the test at the start of the function would process the removal and return. Otherwise, temp.prev.next = would raise a NullPointerException.

Unfortunately, if the last node happens to match, temp.next.prev = will raise a NullPointerException.

 return;
 }
 else temp = temp.next;
 }

If we get to this point, the number wasn't in the list, so the next code is pointless.

 if (tail.num == p.num) // If tail is to be deleted
 {
 tail = tail.prev;

But if we did get here, tail.prev.next would still point to the original tail node!

 return;
 }

You might consider raising a NoSuchElementException if you never found the value to remove.

}

---

Many similar comments for deleteMore().

After deleting 1 or more head nodes, you never set the new head.prev to null, or tail to null if you actually ended up deleting all the nodes.

if (temp.num == tail.num) // If tail node needs to be removed

This does not test for reaching the end of the list. If the list has nodes in the middle which happen to match the value at the end, and that value is above the removal threshold, when you get to that middle node, your processing will skip to the tail node.

To test for the last node, you want

if (temp == tail) // If tail node needs to be removed

or

if (temp.next == null) // If tail node needs to be removed

---

You should add more test cases, to cover the bug found above. Once you can show the code breaks, you can fix the code, and demonstrate it works because the test cases now pass.