3
\$\begingroup\$

I've been working on writing data structures and methods from scratch (with minimal reference) and I'm looking for assistance on my coding style/if there's any way to optimize the methods I've included.

Below is my singular linked list code, all of its methods, and the output of my tests from main. This is also my first time on the board, so let me know if this isn't an appropriate venue for these kinds of questions.

class MySingularlyLinkedList {
// Writing java Linked List singular from scratch (memory)

// Make head node
private Node head;
// Variable to keep track of size of linked list
private int size;

// Function to remove element at end of list
private void removeEnd() {

    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");
    }
    Node current = head;
    // Node variable to store node before current
    Node prev = null;
    // Iterate to end of list (current, prev is one before end)
    while (current.next != null) {
        prev = current;
        current = current.next;
    }

    // Unlink end node from linked list
    prev.next = current.next;
    // Decrement size
    size--;
}

// Function to remove element at front of list
private void removeFront() {

    head = head.next;
    size--;
}

// Function to remove element at given index
private void removeAt(int index) {

    // I know this is the wrong exception, but couldn't think of how else to do this
    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");
    }
    Node current = head;
    Node prev = null;

    for (int i = 0; i < index; i++) {
        prev = current;
        current = current.next;
    }

    prev.next = current.next;
    size--;
}

// Function to remove first instance of a given value
private void removeData(int value) {

    Node current = head;
    Node prev = null;

    // I know this is the wrong exception, but couldn't think of how else to do this
    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");
    }

    if(current.data == value) {
        current = current.next;
    }

    while (current.next != null && current.data != value) {

        prev = current;
        current = current.next;
    }

    // return if value not present in linked list
    if (current.next == null) {
        System.out.println("Value " + value + " not in linked list");
        return;
    }

    prev.next = current.next;
    size--;
}

// Function to return data at given index
public int getData(int index) {

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    // Not sure the best way to do this statement, in main, or in the function? Main because it's not always
    // necessary is my assumption?
    System.out.println("The data at index: " + index + " is: " + (current.data));
    return(current.data);
}

// Function to return index at first instance of data
public int getIndex(int element) {

    Node current = head;
    int index = 0;
    while (current.next != null) {

        if(current.data == (element)) {
            return index;
        }
        index++;
    }
    return -1;
}

// Function to add element to end of linked list
private void insertEnd(int newData) {

    Node newNode = new Node(newData);
    newNode.next = null;

    // if Linked List is empty, make new node head
    if (head == null) {
        head = newNode;
    }
    else {
        // Traverse until current = null
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        // Once end of list is reached, insert new Node
        current.next = newNode;
    }

    // Increment size of list
    size++;
}

// Function to insert node at beginning of list
private void insertFront(int newData) {

    Node newNode = new Node(newData);
    // If list is initally empty insert node at head
    if (head == null) {
        head = newNode;
    }
    else {
        // Set newNode to point to node in front of head
        newNode.next = head;
        // Set head to point to newNode
        head = newNode;
    }
    size++;
}

// Function to insert new node at given index
private void insertAt(int newData, int index) {

    indexCheck(index);
    Node newNode = new Node(newData);
    Node current = head;
    // Iterate until current is node before node at index
    for(int i = 0; i < index - 1; i ++) {
        current = current.next;
    }
    // Set newNode's pointer to node after current (node at specified index)
    newNode.next = current.next;
    // Set current's pointer to newNode
    current.next = newNode;
    // Increment size
    size++;
}

// Function to check if index is within bounds of list
private void indexCheck(int index) {

    if(index < 0 || index > size - 1) {
        throw new IndexOutOfBoundsException("The following index is out of bounds: " + index);
    }
}

 private class Node {

    int data;
    Node next;

    // Default Constructor
    Node(int newData) {

        data = newData;
    }
}

private static void printLinkedList(MySingularlyLinkedList list) {

    Node current = list.head;
    System.out.println("Linked List: ");
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
    System.out.println("The size of the list is now: " + list.size);
}


public static void main(String args[]) {

    MySingularlyLinkedList newList = new MySingularlyLinkedList();

    newList.insertEnd(5);
    newList.insertEnd(2);
    newList.insertEnd(66);
    newList.insertEnd(1);

    System.out.println("Adding elements 5 2 66 and 1 to linked list ");
    printLinkedList(newList);

    System.out.println("Insert 22 at front of linked list ");
    newList.insertFront(22);
    printLinkedList(newList);

    System.out.println("Insert 50 at index 3 of linked list ");
    newList.insertAt(50,3);
    printLinkedList(newList);

    System.out.println("Removing end node of of linked list ");
    newList.removeEnd();
    printLinkedList(newList);

    System.out.println("Removing front node of of linked list ");
    newList.removeFront();
    printLinkedList(newList);

    System.out.println("Removing node at index 2 of of linked list ");
    newList.removeAt(2);
    printLinkedList(newList);

    System.out.println("Getting data at index 0 ");
    newList.getData(0);

    System.out.println("Removing node at first instance of value 2 ");
    newList.removeData(2);
    printLinkedList(newList);

    System.out.println("Removing node at first instance of value -55");
    newList.removeData(-55);
    printLinkedList(newList);

    // Test indexCheck
    // newList.insertAt(1,-1);
}

Output

Adding elements 5 2 66 and 1 to linked list 

Linked List: 
5
2
66
1

The size of the list is now: 4

Insert 22 at front of linked list 

Linked List: 
22
5
2
66
1

The size of the list is now: 5

Insert 50 at index 3 of linked list 

Linked List: 
22
5
2
50
66
1

The size of the list is now: 6

Removing end node of of linked list 

Linked List: 
22
5
2
50
66

The size of the list is now: 5

Removing front node of of linked list 

Linked List: 
5
2
50
66
The size of the list is now: 4

Removing node at index 2 of of linked list 

Linked List: 
5
2
66

The size of the list is now: 3

Getting data at index 0 

The data at index: 0 is: 5

Removing node at first instance of value 2 

Linked List: 
5
66

The size of the list is now: 2

Removing node at first instance of value -55

Value-55 not in linked list

Linked List: 
5
66

The size of the list is now: 2
\$\endgroup\$
1
  • \$\begingroup\$ Accepting an answer very quickly discourages further answers. \$\endgroup\$
    – Eric Stein
    Commented Aug 29, 2019 at 13:40

1 Answer 1

2
\$\begingroup\$

It's good that you have tests (and great to get them reviewed!), but including all the output is probably unnecessary, unless you're including it because some tests are failing and you don't understand why.

As to your question

I'm looking for assistance on my coding style/if there's any way to optimize the methods I've included

I'll write my comments inline:

class MySingularlyLinkedList {
// Writing java Linked List singular from scratch (memory)

// Make head node
private Node head;
// Variable to keep track of size of linked list
private int size;

// Function to remove element at end of list
private void removeEnd() {

    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");

Careful here: is this the case (no list exists) or is the list just empty? Remember, this code is inside the list itself. Would you want an object you're using after instantiating to tell you it doesn't exist?

    }
    Node current = head;
    // Node variable to store node before current
    Node prev = null;
    // Iterate to end of list (current, prev is one before end)
    while (current.next != null) {
        prev = current;
        current = current.next;
    }

    // Unlink end node from linked list
    prev.next = current.next;
    // Decrement size
    size--;
}

// Function to remove element at front of list
private void removeFront() {

    head = head.next;
    size--;
}

// Function to remove element at given index
private void removeAt(int index) {

    // I know this is the wrong exception, but couldn't think of how else to do this
    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");

Same as above - the list exists, it's just empty. You probably want the No Such Element Exception, which is what Java's LinkedList uses.

    }
    Node current = head;
    Node prev = null;

    for (int i = 0; i < index; i++) {
        prev = current;
        current = current.next;
    }

    prev.next = current.next;
    size--;

Careful - if your list has 5 elements and you're asked to remove the 99th element, what happens?

}

// Function to remove first instance of a given value
private void removeData(int value) {

    Node current = head;
    Node prev = null;

    // I know this is the wrong exception, but couldn't think of how else to do this
    if (head == null) {
        throw new IllegalArgumentException("No list exists to remove an element from");
    }

    if(current.data == value) {
        current = current.next;
    }

    while (current.next != null && current.data != value) {

        prev = current;
        current = current.next;
    }

    // return if value not present in linked list
    if (current.next == null) {
        System.out.println("Value " + value + " not in linked list");
        return;
    }

    prev.next = current.next;
    size--;
}

// Function to return data at given index
public int getData(int index) {

The convention is for this method to be called get()

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    // Not sure the best way to do this statement, in main, or in the function? Main because it's not always
    // necessary is my assumption?
    System.out.println("The data at index: " + index + " is: " + (current.data));
    return(current.data);
}

// Function to return index at first instance of data
public int getIndex(int element) {

Similarly, this is usually indexOf()

    Node current = head;
    int index = 0;
    while (current.next != null) {

        if(current.data == (element)) {
            return index;
        }
        index++;
    }
    return -1;
}

// Function to add element to end of linked list

This comment doesn't tell me anything I don't know from the method signature itself

private void insertEnd(int newData) {

    Node newNode = new Node(newData);
    newNode.next = null;

    // if Linked List is empty, make new node head
    if (head == null) {
        head = newNode;
    }
    else {
        // Traverse until current = null
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        // Once end of list is reached, insert new Node
        current.next = newNode;
    }

    // Increment size of list
    size++;
}

// Function to insert node at beginning of list

Same as above

private void insertFront(int newData) {

    Node newNode = new Node(newData);
    // If list is initally empty insert node at head
    if (head == null) {
        head = newNode;
    }
    else {
        // Set newNode to point to node in front of head
        newNode.next = head;
        // Set head to point to newNode
        head = newNode;
    }
    size++;
}

// Function to insert new node at given index
private void insertAt(int newData, int index) {

    indexCheck(index);
    Node newNode = new Node(newData);
    Node current = head;
    // Iterate until current is node before node at index
    for(int i = 0; i < index - 1; i ++) {
        current = current.next;
    }
    // Set newNode's pointer to node after current (node at specified index)
    newNode.next = current.next;
    // Set current's pointer to newNode
    current.next = newNode;
    // Increment size
    size++;

Seems like this doesn't work if index = 0

}

// Function to check if index is within bounds of list
private void indexCheck(int index) {

    if(index < 0 || index > size - 1) {
        throw new IndexOutOfBoundsException("The following index is out of bounds: " + index);
    }
}

 private class Node {

    int data;
    Node next;

    // Default Constructor
    Node(int newData) {

        data = newData;
    }
}

private static void printLinkedList(MySingularlyLinkedList list) {

    Node current = list.head;
    System.out.println("Linked List: ");
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
    System.out.println("The size of the list is now: " + list.size);
}


public static void main(String args[]) {

    MySingularlyLinkedList newList = new MySingularlyLinkedList();

    newList.insertEnd(5);
    newList.insertEnd(2);
    newList.insertEnd(66);
    newList.insertEnd(1);

    System.out.println("Adding elements 5 2 66 and 1 to linked list ");
    printLinkedList(newList);

    System.out.println("Insert 22 at front of linked list ");
    newList.insertFront(22);
    printLinkedList(newList);

    System.out.println("Insert 50 at index 3 of linked list ");
    newList.insertAt(50,3);
    printLinkedList(newList);

    System.out.println("Removing end node of of linked list ");
    newList.removeEnd();
    printLinkedList(newList);

    System.out.println("Removing front node of of linked list ");
    newList.removeFront();
    printLinkedList(newList);

    System.out.println("Removing node at index 2 of of linked list ");
    newList.removeAt(2);
    printLinkedList(newList);

    System.out.println("Getting data at index 0 ");
    newList.getData(0);

    System.out.println("Removing node at first instance of value 2 ");
    newList.removeData(2);
    printLinkedList(newList);

    System.out.println("Removing node at first instance of value -55");
    newList.removeData(-55);
    printLinkedList(newList);

    // Test indexCheck
    // newList.insertAt(1,-1);

These tests are a good start, but you could do a better job of testing edge cases. I.e. there should be tests for calling size and remove on an empty list, adding elements to an empty list, adding elements to the start, end, and middle of a full list, etc. Consider using a unit testing framework, like junit, instead of putting tests in a main method. It'll give you much better visibility and separation between tests.
}

Overall notes:

Your code is pretty clean, and easy to understand. However, it's missing a couple things that would make it cleaner. First: some of your methods are public, and some private, but there doesn't seem to be a logical separation between the two - think about which methods actually belong to the API of a linked list, and make those public, and make the rest private. A public method that's definitely needed that you don't have yet is size().

Stylistically:

Methods should be ordered top to bottom: constructors -> public methods -> private methods. (Public) constructors and public methods should have javadoc explaining what they do. Methods can have inline or block comments, but they should be used sparsely, and only where the code itself is tricky to understand or potentially confusing. Comments should not be redundant, so if the code explains itself leave them out. If the code doesn't explain itself, first ask why: it's likely possible to change it to be easier to follow, and not require commenting. Only if the answer is "because of something that can't be changed" should you add a comment to explain it.

Logically:

Be careful of edge cases, especially for public methods. Private methods will only be called by you - you can assume some things about your input based on how you use the methods in your other code. Public methods will be used by everyone, and you can't be sure what they'll pass. Be sure to account for potentially erroneous input.

Overall, nice job and good attempt. A suite of unit tests and clarification on the interface will go a long way to make this production-quality.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you! This is incredibly helpful \$\endgroup\$
    – aorta
    Commented Aug 28, 2019 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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