4
\$\begingroup\$

I've been working on implementing a doubly linked list from scratch in Java, and if anyone has time, could you critique it?

class Node {
    Node prev;
    Node next;
    int data;

    public Node(int d) {
        data = d;
        prev = null;
        next = null;
    }
}

class LinkedList {
    Node head;

    public LinkedList() {
        head = null;
    }

    public void insert(int d) {
        if (head == null) {
            head = new Node(d);
            return;
        }

        if (head.data > d) {
            Node holder = head;
            Node newNode = new Node(d);
            head = newNode;
            head.next = holder;
            holder.prev = newNode;
            return;
        }

        Node tmpNode = head;

        while (tmpNode.next != null && tmpNode.next.data < d) {
            tmpNode = tmpNode.next;
        }

        Node prevTmp = tmpNode;         
        Node insertedNode = new Node(d);

        if (tmpNode.next != null) {
            Node nextTmp = tmpNode.next;
            insertedNode.next = nextTmp;
            nextTmp.prev = insertedNode;
        } 
        prevTmp.next = insertedNode;
        insertedNode.prev = prevTmp;    
    }

    public void delete(int d) {
        if (head == null) {
            System.out.println("The list is empty.");
            return;
        }

        if (head.data == d) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }

        Node tmpNode = head;

        while (tmpNode != null && tmpNode.data != d) {
            tmpNode = tmpNode.next;
        }

        if (tmpNode == null) {
            System.out.println("That node does not exist in the list");
            return;
        }

        if (tmpNode.data == d) {
            tmpNode.prev.next = tmpNode.next;
            if (tmpNode.next != null) {
                tmpNode.next.prev = tmpNode.prev;
            }
        }
    }

    public void print() {
        Node tmpNode = head;

        while (tmpNode != null) {
            System.out.print(tmpNode.data + " -> ");
            tmpNode = tmpNode.next;
        }

        System.out.print("null");
    }
\$\endgroup\$
4
\$\begingroup\$

Can use Generics for Node to provide something for more then just ints.

class Node<T> {
    Node prev;
    Node next;
    T data;

    public Node(T data) {
        this.data = data;
        prev = null;
        next = null;
    }
}

then same for your linked list implementation.

class LinkedList<T> {
    Node<T> head;

    ...

    public void insert(T d) {
        if (head == null) {
            head = new Node<T>(d);
            return;
        }

    ...

Can make T extends Comparable and use comparable interface to compare if they are less/greater than

\$\endgroup\$
2
\$\begingroup\$
  1. Your are creating something similar to java.util.LinkedList, thus it is best practice to use same or similar method names.

  2. Your list is sorted. Whenever you search for an element, change this loop:

    while (tmpNode != null && tmpNode.data != d) {
        tmpNode = tmpNode.next;
    }
    
    if (tmpNode == null) {
        System.out.println("That node does not exist in the list");
        return;
    }
    

    to this:

    while (tmpNode != null && tmpNode.data < d) {
        tmpNode = tmpNode.next;
    }
    
    if (tmpNode == null|| tmpNode.data != d) {
        System.out.println("That node does not exist in the list");
        return;
    }
    

    It stops whenever the element can't be found.

  3. Instead of System.out.println, use a boolean return value to indicate success.

\$\endgroup\$
0
\$\begingroup\$

The code should be simplified since this is a basic example and it should be clear and simple. You have two variables that aren't actually needed:

  • newNode: when inserting smaller than the first.

  • prevTmp: when inserting after while. It can be tmpNode.

Just remove them and not bother newcomers with looking why you used those.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you should elaborate more on your answer, there isn't much here \$\endgroup\$ – Malachi Oct 14 '14 at 22:05

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.