1
\$\begingroup\$

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;
    }
      }
\$\endgroup\$
  • 1
    \$\begingroup\$ this is a different method I've found Please clarify, in your question, whether you yourself coded an algorithm you found vs. present code you found. See What topics can I ask about here? \$\endgroup\$ – greybeard Apr 28 at 7:43
  • 1
    \$\begingroup\$ empty list represented as null will exclude Java instance methods. \$\endgroup\$ – greybeard Apr 28 at 7:45
  • \$\begingroup\$ Coded it myself, and I messed it up totally. I am working on revising it now as I got feed back from my professor on the same issue you brought up, as well as, it being a doubly (the use of previous should have tipped me off). My logic wasn't just fuzzy, it was totally off, I'm stripping most of it to change and now working on the deleteatindex or scrapping it all together as the assignment is easier than previously thought. Thanks for your help \$\endgroup\$ – blazed Apr 28 at 19:26
  • 2
    \$\begingroup\$ A data type does not become doubly linked due to the naming of some external reference into its innards. In the current state (lack of indentation and doc comments, I for one am not willing to try and read the code presented. Do you agree with vnp's presentation of the instructions? Where do these come from? Please give an/your interpretation of only the link class can be referenced. \$\endgroup\$ – greybeard Apr 28 at 19:51
1
\$\begingroup\$

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;
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.