Implementing a singly linked list with empty list represented as null

Question

I've implemented a singly linked list in Java and would like a code review as I am still learning and this is a different method I've found to do this. The logic is still fuzzy as well to me and writing it out took ages and I'm sure I may have messed up a bit but still have time to mess around with this.

Instructions

• private data members in list class
• public methods must correspond to operations in data structure
• data members include the head, there will be a get size method and elementcounter for the number of elements in the linked list.
• only the link class can be referenced.
• find method must generate a new list of integers to refer to all positions where given item was found
• no user input output
• Inside the find and deleteItem methods, use the 'equals' method of the data entries to compare values.

• Inside the toString method, use the toString methods of the data entries (implicitly) to display the properties of each entry.

  public class List {
  private Link head;
  private Link tail;
  private int elementCount;
  
  public List() {
  
  head = null;
  tail = head;
  elementCount = 0;
  }
  
  public void insert(int position, Object data) {
  if (position < 1 || position > elementCount + 1) {
  System.out.println("Sorry could not insert due to position problems"
          + "Position can't be less than 1, or position is "
          + "greater than element exists");
  return;
  }
  // insert head
  if (isEmpty() && position == 1) {
  head = tail = new Link(data, null);
  elementCount++;
  return;
  }
  if (!isEmpty() && position == 1) {
  Link temp = head;
  head = new Link(data, temp);
  elementCount++;
  return;
  }
  // insert middle
  if (position <= elementCount) {
  int i = 1;
  Link current = head;
  Link previous = null;
  while (i != position) {
  previous = current;
  current = current.next;
  i++;
  }
  previous.next = new Link(data, current);
  elementCount++;
  return;
  }
  // insert at end
  insertAtEnd(data);
  }
  
  public void insertAtEnd(Object data) {
  tail.next = new Link(data, null);
  tail = tail.next;
  elementCount++;
  }
  // 
  public List find(Object toFind) {
  if (isEmpty()) {
  System.out.println("This List is empty");
  return null;
  }
  List listOfpositions = new List();
  Link current = head;
  int position = 1;
  while (current != null) {
  if (isEmpty(listOfpositions)) {
  if (current.data.equals(toFind)) {
  listOfpositions.insert(1, position);
  }
  } else {
  if (current.data.equals(toFind)) {
  listOfpositions.insertAtEnd(position);
  }
  }
  position++;
  current = current.next;
  }
  return listOfpositions;
  }
  
  public void deleteRange(int start, int end) {
  if (isEmpty()) {
  System.out.println("The list is empty");
  return;
  }
  if (start > end) {
  System.out.println("Your range is inverted");
  return;
  }
  if (start == end) {
  deleteAtIndex(start);
  System.out.println("Operation Complete...");
  return;
  }
  int deleteCount = end - start + 1;
  for (int i = 0; i < deleteCount; i++) {
  deleteAtIndex(start);
  }
  System.out.println("Operation Complete...");
  }
  
  public Object getSize() {
  return elementCount;
  }
  
  public void deleteItem(Object item) {
  if (isEmpty()) {
  System.out.println("This List is empty");
  return;
  }
  Link current = head;
  int index = 1;
  while (current != null) {
  if (current.data.equals(item)) {
  deleteAtIndex(index);
  index--;
  }
  current = current.next;
  index++;
  }
  System.out.println("Operation Complete...");
  }
  
  public Link retrieve(int index) {
  if (isEmpty()) {
  System.out.println("List is empty");
  return null;
  }
  if (index > elementCount || index < 1) {
  System.out.println("Out of bound");
  return null;
  }
  if (index == 1) {
  return head;
  }
  if (index == elementCount) {
  return tail;
  }
  Link current = head;
  int i = 1;
  while (current != null && i != index) {
  current = current.next;
  i++;
  }
  return current;
  }
  
  @Override
  public String toString() {
  String linkedList = "This is your list" +
  "\n[";
  Link node = head;
  while (node != null) {
  linkedList += (node);
  linkedList += ",";
  node = node.next;
  }
  int lastComma = linkedList.lastIndexOf(",");
  if (lastComma != -1) {
  linkedList = linkedList.substring(0, linkedList.length() - 1);
  }
  linkedList += ']';
  
  
  return linkedList;
  }
  
  
  private void deleteAtIndex(int index) {
  if (isEmpty()) {
  return;
  }
  if (index < 1) {
  return;
  }
  if (index > elementCount) {
  return;
  }
  if (index == 1) {
  head = head.next;
  elementCount--;
  return;
  }
  if (index == elementCount) {
  Link currentLink = head;
  while (currentLink.next != tail) {
  currentLink = currentLink.next;
  }
  tail = currentLink;
  currentLink.next = null;
  elementCount--;
  return;
  }
  int i = 1;
  Link current = head;
  Link previous = null;
  while (i != index) {
  previous = current;
  current = current.next;
  i++;
  }
  previous.next = current.next;
  elementCount--;
  }
  
  private boolean isEmpty(List listOfpositions) {
  return listOfpositions.head == null;
  }
  
  private boolean isEmpty() {
  return head == null;
  }
  }
  

---

link class

     public class Link {

    public Object data; 
    public Link next;
    /*
     * OR USE THIS CODE
     *  public Object data;
     * public Node next;
     * 
     * public Node (Object _data) {
     * data = _data
     * next = null
     * }
     */
    // have each link  include a reference to an object
    public Link(Object _data, Link node) {
    data = _data;
    next = node;
    }

    @Override
    public String toString() {
    return "Links data:" + data;
    }
      }

Answer 1

The code as presented is poorly formatted, which makes it difficult to read. If this is how it is in your editor, then you should consider reformatting it to a standard indentation. Most IDEs / code editors can do this automatically for you.

public class List {

The list you've implemented is a linked list. This impacts on how it performs. Consider giving it a name that reflects this. The standard library defines a List<T> interface, which is then implemented by concrete implementations (such as LinkedList). This gives a common interface that can be used for working with lists, but allows different concrete selections to be made if particular performance charactersistics are required.

    private Link head;
    private Link tail;
    private int elementCount;

    public List() {

        head = null;
        tail = head;

Consider tail = null, it's more explicit.

        elementCount = 0;
    }

    public void insert(int position, Object data) {

The levels of abstraction in this method are mixed. Some clauses directly change the list, whereas others delegate to member functions. Consider consolidating these levels of abstraction. On approach might be:

• If Invalid position, handle

• If Position == Start, call insertHead

• If Position == End, call insertEnd

• Otherwise, call insertMiddle

       if (position < 1 || position > elementCount + 1) {
           System.out.println("Sorry could not insert due to position problems"
                   + "Position can't be less than 1, or position is "
                   + "greater than element exists");
  

Whilst you may be writing this list with user interaction in mind, it's generally better to separate the user interaction from the actual logic of the list. If this list was being used from a different program, you might not want it outputting directly to the console like this.

            return;

Whilst you've indicated to the console that the insert has failed, the caller has no way to know that the insertion has failed.

        }
// insert head
        if (isEmpty() && position == 1) {
            head = tail = new Link(data, null);
            elementCount++;
            return;
        }
        if (!isEmpty() && position == 1) {
            Link temp = head;
            head = new Link(data, temp);

Consider, if the list was empty, what temp would be if this code was executed, rather than the clause above. Really, the only difference between your processing for an empty list and a list with items is that the empty list also assigns the tail to head...

            elementCount++;
            return;
        }
// insert middle
        if (position <= elementCount) {
            int i = 1;
            Link current = head;
            Link previous = null;
            while (i != position) {
                previous = current;
                current = current.next;
                i++;
            }
            previous.next = new Link(data, current);
            elementCount++;
            return;
        }
// insert at end

Comments should add meaning to the code, otherwise they just add noise. Would the code be any harder to understand without the comment above?

        insertAtEnd(data);
    }

    public void insertAtEnd(Object data) {

This method is called from insert and it appears to be written with that in mind. However, it's declared as a public method. Consider what would happen if it was called on an empty list.

        tail.next = new Link(data, null);
        tail = tail.next;
        elementCount++;
    }

    //

Is something important missing from this comment section?

    public List find(Object toFind) {
        if (isEmpty()) {
            System.out.println("This List is empty");
            return null;

Returning null makes it necessary for the caller to handle the null. Consider using Optional<List> instead to give the caller a hint that the list might not be returned. Or, consider if a better approach would be to return a list of no items instead. This would allow the caller to iterate over zero to many items, without needing to handle the null case explicitly.

        }
        List listOfpositions = new List();
        Link current = head;
        int position = 1;

        while (current != null) {
            if (isEmpty(listOfpositions)) {

If insertAtEnd could be called on an empty list, would you need this branch?

                if (current.data.equals(toFind)) {
                    listOfpositions.insert(1, position);
                }
            } else {
                if (current.data.equals(toFind)) {
                    listOfpositions.insertAtEnd(position);
                }
            }
            position++;
            current = current.next;
        }
        return listOfpositions;
    }

    public void deleteRange(int start, int end) {
        if (isEmpty()) {
            System.out.println("The list is empty");

Again, whilst the console knows nothing has happened the caller doesn't. If these are error conditions, consider if you should be throwing exceptions, rather than just printing and returning.

            return;
        }
        if (start > end) {
            System.out.println("Your range is inverted");
            return;
        }
        if (start == end) {
            deleteAtIndex(start);
            System.out.println("Operation Complete...");

Your other operations like insert don't output this kind of message, does it make sense for this one to?

            return;
        }
        int deleteCount = end - start + 1;

Would this logic still work if start == end?

        for (int i = 0; i < deleteCount; i++) {
            deleteAtIndex(start);

The way deleteAtIndex is implemented, it starts from the head of the list, iterates through to the target item, then removes it. It'll do the same thing for the next item, starting again from the beginning. This is really inefficient. Consider if there's a better way to remove multiple items at once, without having to start from the beginning of the list each time.

        }
        System.out.println("Operation Complete...");
    }

    public Object getSize() {

Size seems like it's a number, should this really be returning an Object?

        return elementCount;
    }

    public void deleteItem(Object item) {
        if (isEmpty()) {
            System.out.println("This List is empty");
            return;
        }
        Link current = head;
        int index = 1;
        while (current != null) {
            if (current.data.equals(item)) {
                deleteAtIndex(index);
                index--;
            }
            current = current.next;
            index++;
        }
        System.out.println("Operation Complete...");
    }

    public Link retrieve(int index) {

Do you want the caller to be able to iterate through the Links themselves? If not, consider returning the Object contained in the list, rather than the Link itself.

        if (isEmpty()) {
            System.out.println("List is empty");
            return null;
        }
        if (index > elementCount || index < 1) {
            System.out.println("Out of bound");
            return null;
        }
        if (index == 1) {
            return head;
        }
        if (index == elementCount) {
            return tail;
        }
        Link current = head;
        int i = 1;
        while (current != null && i != index) {
            current = current.next;
            i++;
        }
        return current;
    }

    @Override
    public String toString() {
        String linkedList = "This is your list" +
                "\n[";
        Link node = head;
        while (node != null) {
            linkedList += (node);
            linkedList += ",";
            node = node.next;
        }
        int lastComma = linkedList.lastIndexOf(",");
        if (lastComma != -1) {
            linkedList = linkedList.substring(0, linkedList.length() - 1);
        }
        linkedList += ']';


        return linkedList;
    }


    private void deleteAtIndex(int index) {

This is a private method. You do a lot of checks in your public methods to make sure that you are operating on valid list elements. Do you still need all of these checks here?

        if (isEmpty()) {
            return;
        }
        if (index < 1) {
            return;
        }
        if (index > elementCount) {
            return;
        }
        if (index == 1) {
            head = head.next;
            elementCount--;
            return;
        }
        if (index == elementCount) {
            Link currentLink = head;
            while (currentLink.next != tail) {
                currentLink = currentLink.next;
            }
            tail = currentLink;
            currentLink.next = null;
            elementCount--;
            return;
        }
        int i = 1;
        Link current = head;
        Link previous = null;
        while (i != index) {
            previous = current;
            current = current.next;
            i++;
        }
        previous.next = current.next;
        elementCount--;
    }

    private boolean isEmpty(List listOfpositions) {

It's unclear why this method exists. Why wouldn't the client call listOfpositions.isEmpty() ? If you do want it, consider making it a static method.

        return listOfpositions.head == null;
    }

    private boolean isEmpty() {
        return head == null;
    }
}