1) SortedLinkedList extends BasicLinkedList but both have
private Node head;
private Node tail
this is wrong. If you want to inherit those field in the sub class, you should mark the variables as protected in the super class and remove them from the subclass.
2) Same goes for private class Node. You are declaring the Node class in both the SortedLinkedList and BasicLinkedList. What you should do is declare it once, (maybe in the super class?) and use the same class in both places. If you do this, the constructor, and the fields should be accessible to both classes. So you will have to change the access modifier (private is what you have now).
I will post below code that works, but I haven't spent any time on the design. Just posting it to demonstrate how you could change the code to make it work. You will have to decide which access modifiers to use and where to put the classes.
import java.util.Comparator;
import java.util.Iterator;
public class Test {
public static void main(String[] args) {
System.out.println("---------------SortedLinkedList--------------");
SortedLinkedList<Integer> sortedList = new SortedLinkedList<Integer>(new intComparator());
sortedList.add(3);
sortedList.add(5);
sortedList.add(2);
for (int i : sortedList) {
System.out.println(i);
}
}
}
class BasicLinkedList<T> implements Iterable<T> {
public int size;
class Node {
T data;
Node next;
Node(T data) {
this.data = data;
next = null;
}
}
protected Node head;
protected Node tail;
public BasicLinkedList() {
head = tail = null;
}
// Add, remove method
public Iterator<T> iterator() {
return new Iterator<T>() {
Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public T next() {
if (hasNext()) {
T data = current.data;
current = current.next;
return data;
}
return null;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove not implemented.");
}
};
}
}
class SortedLinkedList<T> extends BasicLinkedList<T> {
private Comparator<T> comp;
public SortedLinkedList(Comparator<T> comparator) {
super();
this.comp = comparator;
}
public SortedLinkedList<T> add(T element) {
Node n = new Node(element);
Node prev = null, curr = head;
if (head == null) {
head = n;
tail = n;
}
// See if the element goes at the very front
else if (comp.compare(n.data, curr.data) <= 0) {
n.next = head;
head = n;
}
// See if the element is to be inserted at the very end
else if (comp.compare(n.data, tail.data) >= 0) {
tail.next = n;
tail = n;
}
// If element is to be inserted in the middle
else {
while (comp.compare(n.data, curr.data) > 0) {
prev = curr;
curr = curr.next;
}
prev.next = n;
n.next = curr;
}
size++;
return this;
}
}
class intComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
Answer from Can't Tell on Stack OverflowI found 5 main ways to iterate over a Linked List in Java (including the Java 8 way):
- For Loop
- Enhanced For Loop
- While Loop
- Iterator
- Collections’s stream() util (Java8)
For loop
LinkedList<String> linkedList = new LinkedList<>();
System.out.println("==> For Loop Example.");
for (int i = 0; i < linkedList.size(); i++) {
System.out.println(linkedList.get(i));
}
Enhanced for loop
for (String temp : linkedList) {
System.out.println(temp);
}
While loop
int i = 0;
while (i < linkedList.size()) {
System.out.println(linkedList.get(i));
i++;
}
Iterator
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
collection stream() util (Java 8)
linkedList.forEach((temp) -> {
System.out.println(temp);
});
One thing should be pointed out is that the running time of For Loop or While Loop is O(n square) because get(i) operation takes O(n) time(see this for details). The other 3 ways take linear time and performs better.
Linked list is guaranteed to act in sequential order.
From the documentation
An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.
iterator() Returns an iterator over the elements in this list in proper sequence.
Does the code comply with the Java coding conventions?
I think it does comply quite well. A tiny thing is that it would be better to put a space between ){, for example in if (list.isEmpty()){. More importantly, it can be simplified.
There is no need for the inner list variable pointing to this.
The inner (non-static) class has direct access to the containing class' fields and methods: it can access firstNode directly from the containing list. So in this code:
final MyLinkedList<T> list = this; return new Iterator<T>() { final Node<T> firstNode = list.firstNode;
You can drop both the list variable and the firstNode variable.
It's a minor thing, but currentNode can be private.
The hasNext method can be simplified by a lot:
@Override public boolean hasNext() { if (list.isEmpty()) { return false; } else if (currentNode == null){ return true; } else if (currentNode == list.lastNode){ return false; } return true; }
This is equivalent:
@Override
public boolean hasNext() {
return !isEmpty() && currentNode != lastNode;
}
Could this be made significantly faster?
Slightly. Notice that the isEmpty() check is pointless to perform for every iteration of a non-empty list. So as a minor optimization,
you could check for emptiness once, in the beginning,
and then omit all the isEmpty() checks from the rest of the code.
Suggested implementation
Putting it all together:
public Iterator<T> iterator() {
if (isEmpty()) {
return Collections.<T>emptyList().iterator();
}
return new Iterator<T>() {
private Node<T> currentNode = null;
@Override
public boolean hasNext() {
return currentNode != lastNode;
}
@Override
public T next() {
if (currentNode == null) {
currentNode = firstNode;
return currentNode.data;
}
if (currentNode.nextNode == null) {
throw new NoSuchElementException();
}
currentNode = currentNode.nextNode;
return currentNode.data;
}
};
}
Unit testing
I didn't just refactor aggressively. I wrote unit tests first to know that I'm not breaking anything. After that I could go ahead and refactor aggressively:
@Test
public void testEmpty() {
MyLinkedList<Integer> list = new MyLinkedList<>();
assertFalse(list.iterator().hasNext());
}
@Test(expected = NoSuchElementException.class)
public void throwIfNextOnEmpty() {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.iterator().next();
}
@Test(expected = NoSuchElementException.class)
public void throwIfIterateBeyond() {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(1);
list.add(2);
Iterator<Integer> iter = list.iterator();
iter.next();
iter.next();
iter.next();
}
@Test
public void testStandardIteration() {
MyLinkedList<Integer> list = new MyLinkedList<>();
Integer[] items = { 12, 3, 4 };
for (int i : items) {
list.add(i);
}
Iterator<Integer> iter = list.iterator();
for (Integer item : items) {
assertTrue(iter.hasNext());
assertEquals(item, iter.next());
}
assertFalse(iter.hasNext());
}
These may not be perfect, and might not cover all corner cases, but I hope they are enough to get you started.
There's a trick with Iterator implementations that can make the logic much simpler, if you caan get your head around the slightly back-to-front implementation.
In your code, you have implemented a system where it checks the state of the list before iterating, but, if you think of an iterator as being a cycle of:
- check if there's another member
- advance to the next member
- return the member
- go to 1.
then, what you are doing, is having your 'mindset' anchored at the spot just before step 1. Step 1 is what you consider to be the 'base' state of the cycle.
But, there's no reason for that, you can actually anchor the cycle at the spot just in between step 2 and step 3.
The way this works, is easier to explain with code, rather than words....
... as an aside, there's no need to have the final MyLinkedList list = this because you can reference MyLinkedList.this.firstNode, etc.
public Iterator<T> iterator() {
return new Iterator<T>() {
private Node<T> followingNode = firstNode;
@Override
public boolean hasNext() {
return followingNode != null;
}
@Override
public T next() {
if (followingNode == null) {
throw new NoSuchElementException();
}
T toReturn = followingNode.data;
followingNode = followingNode.nextNode;
return toReturn;
}
};
}
Notice how the 'state' of the iterator is 'ready' to return the next() value. Because the iterator is set up that way, the check to see hasNext() is really easy... all you have to do is see if the current state is valid. Also, in the next() method the state check is also very easy, and we harvest the return value from the known-valid state, and then we advance to the next state before returning the value. We don't need to check if the next state is valid because that will happen on the next-go-around.
While I was putting that together, I noticed some other things too. In your code you have:
if (list.isEmpty()){ throw new NoSuchElementException(); } else if (currentNode == null){ this.currentNode = firstNode; return currentNode.data; } else if (currentNode.nextNode == null) { throw new NoSuchElementException(); }
Those else-if blocks are not necessary. Each block exits the function (either through a throw or a return. You should write blocks like that as:
if (list.isEmpty()){
throw new NoSuchElementException();
}
if (currentNode == null){
this.currentNode = firstNode;
return currentNode.data;
}
if (currentNode.nextNode == null) {
throw new NoSuchElementException();
}