Unit tests are tests meant to verify the external behavior of some data structure. More precisely, a good suite of tests should decisively answer the following question: "Does data structure X match the expected behavior of some abstract data type Y? For example, if I'm writing some custom stack implementation, does it behave in all the ways a stack should?"
Not only that, you should be testing to make sure your data structure breaks in the correct ways as well. If somebody tries using your data structure in an invalid way, does it crash correctly?
Here are some specific things you might want to try checking when testing:
The happy cases:
Test how your clients will normally use your code.
Errors and exceptions:
Do you throw the correct exceptions when bad input is given? Did you forget to implement a certain exception? Do you check for an error condition too late?
Preconditions and postconditions:
Try checking/stress-testing your preconditions. Are your postconditions always satisfied afterwards?
Empty and null cases:
What happens when you pass in zero? An empty string or list? A null object?
Edge cases:
Test for edge cases and off-by-one errors. Look for "boundaries" in your input data.
(What do we mean by "boundaries"? As an example, suppose you're testing an arraylist designed to resize after 16 elements are inserted. We woulc consider that magic number "16" as a "boundary", since the behavior of your class changes significantly once you hit that point. What happens if you try inserting 15 items? 16 items? 17 items?)
Another strategy is to try generating randomized data to hunt for weird edge cases.
Mixing multiple methods:
Each method individually might work fine, but what happens if you try using multiple of them, called in all kinds of different orders?
All data structures have "invariants" — assumptions (usually about their fields or other internal details) that must be true both before and after any method is called.
Testing invariants using unit tests can be challenging because most invariants tend to be about the state of your private fields which are not easily accessible. Here are some strategies you can use instead:
Rigorously check user input:
Certain kinds of user input can break your code, ultimately violating your invariants. This is why the spec often mandates you throw exceptions in certain circumstances.
Write invariant checks:
Another strategy you can use is to write invariant checks: a helper method that deliberately checks to make sure your invariants are true and throws an exception if it isn't.
Then, call that helper method at the start and end of every method and run your unit tests as usual.
This can help subtle errors before they propagate. For example, suppose
your DoubleLinkedList.add(...) method will start throwing exceptions
after a while. Why might that be? Is it because of add(...), or
because of some other previously called method?
Your invariant check method can help you figure this out. If it starts failing
at the end of your delete(...) method, you know that method was the
true culprit. Alternatively, if it starts failing at the end of your
add(...), you know that's the broken method.
Important: Be sure to comment out or delete your invariant check before submitting your code! Your invariant checks will typically need to look through your entire data structure which can be expensive and cause you to fail runtime performance checks.
Try writing JUnit tests that call multiple methods:
Calling multiple methods and testing how they interact can be a good way of indirectly testing your invariants.
See the above section for more details.