3
\$\begingroup\$

this is my first time on StackExchange. I am new to writing code. This is a singly-linked list I made in Java using generics with no sentinel nodes (i.e. no empty head and tail nodes). Looking for feedback on how to be more efficient, clean, and generally improve my code writing to include best practices. Each method is tested in main and tests for exceptions are commented out for convenience. Any recommendations how to improve are very much appreciated. Thank you very much!

//In this project I created a generic singly-linked list using Java Generics.
public class GenLinkedList<T> {

    //Declare and define Node
    private static class Node<T>
    {
        //Declare value
        public T value;
        //Declare next pointer
        public Node<T> next;

        //Constructor (if next is null)
        public Node(T v)
        {
            value = v;
            next = null;
        }

        //Constructor
        public Node(T v, Node<T> n)
        {
            value = v;
            next = n;
        }

    }

    //Declare list head variable
    //Set to null in case there are no nodes when using addFront
    private Node<T> head = null;

    int size = 0;

    //AddFront method
    //receives an item to add as a parameter, and adds to the front of the list.
    public void addFront(T item)
    {
        head = new Node<T>(item, head);
        size++;
    }

    //AddEnd method
    //receives an item to add as a parameter and adds to the end of the list
    public void addEnd(T item)
    {
        size++;
        if(head == null)
        {
            head = new Node<T>(item);
        } else {
            //Declare a pointer to traverse the list
            Node<T> ptr = head;
            while(ptr.next != null)
            {
                //Advance pointer
                ptr = ptr.next;
            }
            //Call constructor with no next
            ptr.next = new Node<T>(item);
        }
    }

    //RemoveFront method
    //removes a node from the front of the list.
    public void removeFront() throws Exception {

        try {

            if (head == null) {
                throw new Exception("List is empty");
            }

        }
        catch(Exception e){
            System.out.println(e);
            return;
        }

        head = head.next;
        size--;
    }

    //RemoveEnd method
    //removes a node from the end of the list.
    public void removeEnd() throws Exception
    {
        try {
            if (head == null) {
                throw new Exception("List is empty");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }

        size--;
        Node<T> ptr = head;
        Node<T> ptr2 = ptr;

        while(ptr.next != null)
        {
            ptr2 = ptr;
            ptr = ptr.next;
        }

        if(ptr2.next == null)
        {
            head = null;
        } else {
            ptr2.next = null;
        }
    }

    //Set method
    //receives a position and item as parameters, sets the element at this
    // position, provided it is within the current size
    private void set(T item, int position) throws Exception
    {
        //Check if position exceeds size
        try {
            if (position > size) {
                throw new Exception("Position exceeds list size");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }

        Node<T> ptr = head;
        for(int i = 1; i < position; i++)
        {
            ptr = ptr.next;
        }
        ptr.value = item;
    }

    //Get method
    //receives a position as a parameter, returns the item at this position,
    // provided it is within the current size
    private T get(int position) throws Exception
    {
        //Check if position exceeds size
        try {
            if (position > size || size == 0 || position <= 0) {
                throw new Exception("Invalid position");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            //Must return something
            return null;
        }

        Node<T> ptr = head;
        for(int i = 1; i < position; i++)
        {
            ptr = ptr.next;
        }
        return ptr.value;
    }

    //Swap method
    //receives two index positions as parameters, and swaps the nodes at
    // these positions, provided both positions are within the current size
    private void swap(int position, int position2) throws Exception
    {
        //Check if positions exceeds size
        try {
            if (position > size || position2 > size) {
                throw new Exception("Invalid position");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }

        //Instead of swapping arrows, swap the values
        T temp = get(position);
        T temp2 = get(position2);
        set(temp2, position);
        set(temp, position2);
    }

    //Shift method
    // receives an integer as a parameter, and shifts the list forward or
    // backward this number of nodes, provided it is within the current size
    private void shift(int shift) throws Exception
    {
        //Note: you can include two different exceptions in a try
        try {
            if (size <= 1) {
                throw new Exception("List is empty");
            }

            if(shift >= size || shift * -1 >= size)
            {
                throw new Exception("Invalid shift amount");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }



        //Convert a negative shift to a positive value
        if(shift < 0)
        {
            shift += size;
        }

        Node<T> ptr = head;
        Node<T> prevPtr = ptr;
        Node<T> tailPtr = head;

        //Find the tail
        while(tailPtr.next != null)
        {
            tailPtr = tailPtr.next;
        }
        //Have tail point to head
        tailPtr.next = head;

        //Advance pointers by shift amount to find new list head node and new tail node
        for(int i = 0; i < shift; i++)
        {
            prevPtr = ptr;
            ptr = ptr.next;
        }

        //Set head pointer
        head = ptr;
        //Make new tail point to null
        prevPtr.next = null;

        return;

    }

    //Erase method
    //receives an index position and number of elements as parameters, and
    // removes elements beginning at the index position for the number of
    // elements specified, provided the index position is within the size
    // and together with the number of elements does not exceed the size
    private void erase(int position, int numElements) throws Exception {
        try {
            if (position + numElements > size + 1) {
                throw new Exception("Index exceeds list size");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }

        if(position == 1)
        {
            for(int i = 0; i < numElements; i++)
            {
                removeFront();
            }
            return;
        }

        if(position == size)
        {
            removeEnd();
            return;
        }

        Node<T> ptr = head;
        Node<T> prevPtr = head;
        for(int i = 1; i < position; i++)
        {
            prevPtr = ptr;
            ptr = ptr.next;
        }

         for(int i = 0; i < numElements - 1; i++)
         {
             ptr = ptr.next;
         }

         prevPtr.next = ptr.next;
         size = size - numElements;
         return;

    }

    //RemoveMatching method
    //receives a value of the generic type as a parameter and removes all
    // occurrences of this value from the list.
    private void removeMatching(T item) throws Exception {
        Node<T> ptr = head;
        //System.out.println("Size is: " + size);
        for(int i = 1; i < size + 1; i++)
        {
            //System.out.println("Size in FOR loop is : " + size);
            //System.out.println("Looking at position: " + i + ", value: " + ptr.value);
            if(item == ptr.value)
            {
                ptr = ptr.next;
                erase(i, 1);
                i--;

            } else {
                ptr = ptr.next;
            }
        }
        return;
    }

    //InsertList method
    //receives a generic List (a Java List) and an index position as parameters,
    // and copies each value of the passed list into the current list starting
    // at the index position, provided the index position does not exceed the size.
    // For example, if list has a,b,c and another list having 1,2,3 is inserted at
    // position 2, the list becomes a,b,1,2,3,c
    private void insertList(GenLinkedList list, int position) throws Exception
    {
        try {
            if (position > size) {
                throw new Exception("Invalid position");
            }

            if(list.size == 0){
                throw new Exception("New list is empty");
            }

        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }


        Node<T> ptr = head;
        Node<T> nextPtr = ptr.next;

        if(position == 0)
        {
            Node<T> listPtr = list.head;
            for(int i = 1; i < list.size; i++)
            {
                listPtr = listPtr.next;
            }
            listPtr.next = head;
            size = size + list.size;

            head = list.head;
            return;
        }

        for(int i = 1; i < position; i++)
        {
            ptr = ptr.next;
            nextPtr = ptr.next;
        }

        Node<T> listPtr = list.head;
        ptr.next = list.head;
        for(int i = 1; i < list.size; i++)
        {
            listPtr = listPtr.next;
        }
        listPtr.next = nextPtr;
        size = size + list.size;
        return;

    }

    //Print method
    private void print()
    {
        Node<T> ptr = head;
        for(int i = 0; i < size; i++)
        {
            System.out.println(ptr.value);
            ptr = ptr.next;
        }
        return;
    }

    public static void main(String args[]) throws Exception {

        //Test constructor, addFront, and addEnd.  Created a print function for ease of testing.
        GenLinkedList<Integer> jensList = new GenLinkedList<>();
        jensList.addFront(5);
        jensList.addFront(3);
        jensList.addFront(4);
        jensList.addFront(2);
        jensList.addFront(1);
        jensList.addEnd(4);
        jensList.addEnd(4);
        jensList.addEnd(6);
        jensList.addEnd(7);


        System.out.println("Original list is: ");
        jensList.print();
        System.out.println();

        //Test removeFront and removeEnd
        jensList.removeFront();
        jensList.removeEnd();

        System.out.println("List updated to remove front and end: ");
        jensList.print();
        System.out.println();

        //Test set
        jensList.set(1, 1);

        System.out.println("List updated to set the first node value to 1: ");
        jensList.print();
        System.out.println();

        //Test get
        System.out.println("Get method finds the value of the second node: " + jensList.get(2));
        System.out.println();

        //Test swap
        jensList.swap(4, 3);
        System.out.println("Swap node positions 3 and 4: ");
        jensList.print();
        System.out.println();

        //Test removeMatching
        jensList.removeMatching(4);
        System.out.println("Remove nodes with value 4: ");
        jensList.print();
        System.out.println();

        //Test erase
        jensList.erase(2, 2);
        System.out.println("Erase 2 nodes starting at position 2: ");
        jensList.print();
        System.out.println();


        //Create a second list and test insertList
        GenLinkedList<String> list2 = new GenLinkedList<>();
        list2.addFront("c");
        list2.addFront("b");
        list2.addFront("a");
        System.out.println("List2 is: ");
        list2.print();
        System.out.println();
        jensList.insertList(list2, 1);
        System.out.println("Original list combined with List2 is:");
        jensList.print();

        //Test shift
        System.out.println("Shift the list by +2:");
        jensList.shift(2);
        jensList.print();
        System.out.println();
        System.out.println("Shift the list by -2:");
        jensList.shift(-2);
        jensList.print();
        System.out.println();

        //The following tests exceptions with try-catch to prevent crashing
        //GenLinkedList<Integer> emptyList = new GenLinkedList<>();
        //emptyList.removeFront();
        //emptyList.removeEnd();
        //emptyList.set(2, 1);
        //emptyList.get(0);
        //jensList.get(0);
        //emptyList.swap(1,2);
        //jensList.swap(6,7);
        //emptyList.shift(3);
        //jensList.shift(9001);
        //jensList.insertList(list2, 12);
        //jensList.shift(-5);

        //System.out.println("New jenslist is : ");
        //jensList.print();

    }
}

```
\$\endgroup\$
1
  • \$\begingroup\$ Operations like addEnd and removeEnd and basically all operations that accept a position, have time complexity O(n) and they don't belong on a singly linked list. If these operations are needed, a different data structure, ie doubly linked list, should be used instead. \$\endgroup\$
    – slepic
    Sep 21, 2020 at 15:26

1 Answer 1

4
\$\begingroup\$

Javadoc.


Your formatting is off. Use an automatic-formatter (configured as you'd like it) and always format your code with that.


If you feel bored, you can ask yourself whether this should be thread-safe or not.


Maybe implementing a standard Java interface would be off benefit here, like List.


If you haven't done so, write unit tests for this. This is a perfect class for exercising writing unit tests.


You don't need to return at the end of void methods.


public class GenLinkedList<T> {

Stop shortening words and names just for the sake of it, it makes the code harder to read and maintain.

The same goes for this:

        Node<T> ptr = head;
        Node<T> ptr2 = ptr;

The names are completely useless. They should be something like lastNode and secondToLastNode.


int size = 0;

I'm not a fan of package-private variables. They might be used to introduce unhealthy coupling between components.


    public void addEnd(T item)

You're not checking whether item is null, which would explode your implementation in one way or the other.


    public void removeFront() throws Exception {

        try {

            if (head == null) {
                throw new Exception("List is empty");
            }

        }
        catch(Exception e){
            System.out.println(e);
            return;
        }

        head = head.next;
        size--;
    }

Your exception handling here doesn't make any sense. First, try to avoid throwing or declaring Exception, use appropriate exceptions. For example an IllegalStateException or an IndexOutOfBoundsException. Second, you're throwing an exception just to catch it, print it to stdout and then return. Third, don't print to stdout from utility/"library" classes, either throw exceptions and let the caller deal with showing the message, or use an appropriate logger.


        size--;
        Node<T> ptr = head;
        Node<T> ptr2 = ptr;

        while(ptr.next != null)
        {
            ptr2 = ptr;
            ptr = ptr.next;
        }

        if(ptr2.next == null)
        {
            head = null;
        } else {
            ptr2.next = null;
        }

You could do some form of peeking in the loop, something like this:

if (head.next == null) {
    head = null;
} else {
    Node<T> secondToLastNode = head;
    
    while(secondToLastNode.next != null && secondToLastNode.next.next != null {
        secondToLastNode = secondToLastNode.next;
    }
    
    secondToLastNode.next = null;
}

        //Check if position exceeds size
        try {
            if (position > size) {
                throw new Exception("Position exceeds list size");
            }
        }
        catch(Exception e)
        {
            System.out.println(e);
            return;
        }

Perfect place for an IndexOutOfBoundsException.


            if (position > size || size == 0 || position <= 0) {

Why is 0 an invalid index?


if(shift >= size || shift * -1 >= size)

You can negate even variables by prefixing them with a minus.

if(shift >= size || -shift >= size)

But actually, you want to use Math.abs.

if(Math.abs(shift) >= size)

    //InsertList method
    //receives a generic List (a Java List)...

That's not correct.


    //Print method
    private void print()
    {
        Node<T> ptr = head;
        for(int i = 0; i < size; i++)
        {
            System.out.println(ptr.value);
            ptr = ptr.next;
        }
        return;
    }

That should not be in your class, it should not be concerned with printing itself to stdout.

\$\endgroup\$
1
  • \$\begingroup\$ Also main function should not be part of the class :) \$\endgroup\$
    – slepic
    Sep 22, 2020 at 5:21

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.