11
\$\begingroup\$

I've been practicing implementing a linked list from scratch. Can someone help review my code?

class Node {
    Node next;
    int num;

    public Node(int val) {
        num = val;
        next = null;
    }
}

public class LinkedList {

    Node head;

    public LinkedList(int val) {
        head = new Node(val);
    }

    public void append(int val) {
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        tmpNode.next = new Node(val);
    }

    public void insert(int val) {
        Node currentNode = head;
        Node nextNode = head.next;

        if (currentNode.num > val) {
            Node tmpNode = head;
            head = new Node(val);
            head.next = tmpNode;
            return;
        }

        if (nextNode != null && nextNode.num > val) {
            currentNode.next = new Node(val);
            currentNode.next.next = nextNode;
            return;
        }

        while (nextNode != null && nextNode.num < val) {
            currentNode = nextNode;
            nextNode = nextNode.next;
        }

        currentNode.next = new Node(val);
        currentNode.next.next = nextNode;
    }

    public void delete(int val) {
        Node prevNode = null;
        Node currNode = head;

        if (head.num == val) {
            head = head.next;
            return;
        }

        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }

        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
        }
        else {
            prevNode.next = currNode.next;
        }

    }

    public void print() {
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
        System.out.print("null");
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList(5);
        myList.append(7);
        myList.append(16);
        myList.insert(9);
        myList.insert(4);
        myList.insert(6);
        myList.insert(17);
        myList.delete(16);
        myList.delete(5);
        myList.delete(4);
        myList.delete(17);
        myList.delete(34);
        myList.print();
    }
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Just realized my append function doesn't check if head is null at the beginning also. My current function would throw an NPE if it was null. \$\endgroup\$
    – Adam Johns
    Nov 19, 2013 at 18:54

3 Answers 3

7
\$\begingroup\$
  1. Your implementation does not allow for an empty list.

    1. It's a bit odd to only have the constructor which takes a node value.
  2. You should probably implement the List interface.

  3. You should look into generics instead of hard-coding your list to only take ints.

  4. It looks like from looking at insert() that you are trying to create an ordered linked list. However, append() does not. (If you really want to define an ordered linked list, you can still use generics, but you'll have to use types which are children of Comparable).

  5. In insert() and delete() you have some if-conditions followed by a while-loop. My guess is that they can be merged in a single while-loop. I was lazy and haven't tried doing it, so it might not be true.

\$\endgroup\$
4
\$\begingroup\$

What @toto2 said plus

  • I would change the print method. Override toString method.

  • Do not put System.out.println in an API class. You will be reusing your LinkedList class in future in GUI or Web app. Then unwanted SOPs will hamper your code.

\$\endgroup\$
4
\$\begingroup\$

Exactly as already said:

  • Mixing insert() with append()? Does it make sense? Choose one
  • You do not accept an empty list.

Here is a turbo-fast example with append() accepting an empty list:

class Node {
    Node next;
    int num;
    public Node(int val) {
        num = val;
        next = null;
    }
}

class LinkedList {

    private Node head = null;

    public void append(int val) {
        Node lastNode = getLastNode();
        if (lastNode == null) {
            head = new Node(val);
        } else {
            lastNode.next = new Node(val);
        }
    }

    public void delete(int val) {
        if(head == null){
            return;
        }

        Node prevNode = null;
        Node currNode = head;
        while (currNode != null && currNode.num != val) {
            prevNode = currNode;
            currNode = currNode.next;
        }
        if(prevNode == null){
            head = head.next;
            return;
        }
        if (currNode == null) {
            System.out.println("A node with that value does not exist.");
            return;
        }
        prevNode.next = currNode.next;
    }

    public void print() {
        System.out.println("");
        if(head == null){
            System.out.print("EMPTY");
            return;
        }
        Node tmpNode = head;
        while (tmpNode != null) {
            System.out.print(tmpNode.num + " -> ");
            tmpNode = tmpNode.next;
        }
    }

    private Node getLastNode() {
        if (head == null) {
            return null;
        }
        Node tmpNode = head;
        while (tmpNode.next != null) {
            tmpNode = tmpNode.next;
        }
        return tmpNode;
    }

    public static void main(String[] args) {
        LinkedList myList = new LinkedList();
        myList.print();
        myList.append(35);
        myList.append(33);
        myList.print();
        myList.delete(33);
        myList.delete(35);
        myList.delete(35);
        myList.print();
    }
}

It's just an example, so you would like to implement the absolute minimum, but of course Generics, Comparable, System.out.print are still actual topics.

\$\endgroup\$

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.