Single Link List

Question

So I have implemented Single link list using java.Please advice if this is OK or can be made better.

public class SingleLinkedList<Generic> {

private Generic data;
private SingleLinkedList<Generic> next;

public SingleLinkedList() {
    super();
}

public SingleLinkedList(Generic data, SingleLinkedList<Generic> next) {
    super();
    this.data = data;
    this.next = next;
}

public Generic getData() {
    return data;
}

public void setData(Generic data) {
    this.data = data;
}

public SingleLinkedList<Generic> getNext() {
    return next;
}

public void setNext(SingleLinkedList<Generic> next) {
    this.next = next;
}

public SingleLinkedList<Generic> add(Generic data, SingleLinkedList<Generic> node) {
    SingleLinkedList<Generic> temp = new SingleLinkedList<Generic>(data, null);
    node.setNext(temp);
    return temp;
}

public int size(SingleLinkedList<Generic> node) {
    int size = 0;
    if (node == null || node.getNext() == null)
        return 0;

    // Get the first node
    node = node.getNext();
    do {
        size++;
    } while ((node = node.getNext()) != null);

    return size;
}

public String toString(SingleLinkedList<Generic> node) {

    if (node == null || node.getNext() == null)
        return "List Empty!";

    // Get the first node
    node = node.getNext();
    StringBuilder data = new StringBuilder();
    do {
        data.append(node.getData() + ",");
    } while ((node = node.getNext()) != null);

    data.replace(data.length() - 1, data.length(), "");

    return "SingleLinkedList [data=" + data.toString() + "]";
}

public boolean insertAtPosition(int position, Generic data, SingleLinkedList<Generic> head) {

    if (position < 0)
        return false;

    if (head == null || head.getNext() == null)
        return false;

    int currentPosition = 0;
    SingleLinkedList<Generic> temp;

    // if position 1 then change and update head
    if (position == 0) {
        temp = new SingleLinkedList<Generic>(data, null);

        if (head.getNext() != null)
            temp.setNext(head.getNext());

        head.setNext(temp);

        return true;
    }

    temp = head.getNext();
    SingleLinkedList<Generic> newNode = new SingleLinkedList<>(data, null);
    while (temp != null && temp.getNext() != null && currentPosition <= position - 1) {
        currentPosition++;
        temp = temp.getNext();
    }

    if (position > currentPosition)
        return false;

    newNode.setNext(temp.getNext());
    temp.setNext(newNode);
    return true;
}

}

And the following is the class implementing the same:

public class MyPets {

public static void main(String[] args) {
    // Gather my pets
    // add my missing pets
    // confirm the size
    // print their name

    new MyPets().operationPet();
}

private void operationPet() {
    SingleLinkedList<String> head = new SingleLinkedList<String>(null, null);
    SingleLinkedList<String> temp = head.add("Tom", head);
    temp = head.add("Marcus", temp);
    temp = head.add("Pluto", temp);

    head.insertAtPosition(0, "Noddy", head);

    System.out.println(head.size(head));
    System.out.println(head.toString(head));
}

}

Answer 1

It is customary to have a private Node class when implementing a list. This separates the holding of data from the managing of the list.

You on the other hand have both functionalities in one, which leads to all sorts of confusion.

For example, you expose the internal workings of the list by essentially returning nodes or working on nodes that are passed in from outside.

Your add method is also very confusing. It doesn't actually work on the list it is called on, but instead on a node passed to it. The same is true for size, but not for setNext.

I would completely rewrite your code. Start with a Node class that has nextNode and data as fields, and a SingleLinkedList class that has headNode and size as fields. Then add the methods you need, but keep in mind to not expose the Node class to the outside world.

Answer 2

One improvement might be preventing duplicate keys. A second improvement would be refactoring your add function into a higher order function that calls a search function to find duplicates and a call to an insert function.

It would look like this...

public int add(Generic data) {
    int found = this.search(&pre, &post, data); 
    if (found==1) return 1; //prevent duplicates
    int success = self.insert(pre, data);
    return success;
}
// also  
private int search(Generic data) {...}
private int insert(Node pre, Generic data) {...}