5
\$\begingroup\$

I am new to studying data structures although I have been programming in Java/Android since October. I feel it's time to advance, so I am starting data structures / algorithms this month. Since linked lists are a big topic in interviews and I knew nothing about them (I spent the past 3 days learning about it), hopefully my code is mostly correct, but please let me know if I am missing anything or not catching something, or if there's any way to improve it.

public class MyLinkedList<T> {

    private LinkNode<T> head;
    private int size;

    public MyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    public void display() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            LinkNode<T> current = head;
            while (current != null) {
                System.out.println(current.toString());
                current = current.getNext();
            }
        }

    }

    public void addEnd(T data) {
        if (head == null) {
            head = new LinkNode<T>(data, head);
        } else {
            LinkNode<T> current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            LinkNode<T> newNode = new LinkNode<T>(data, null);
            current.setNext(newNode);
            size++;
        }
    }

    public void addFront(T data) {
        head = new LinkNode<T>(data, head);
        size++;
    }

    public void removeEnd() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            LinkNode<T> current = head;
            LinkNode<T> previous = head;
            while (current.getNext() != null) {
                previous = current;
                current = current.getNext();
            }
            previous.setNext(null);
            size--;
        }
    }

    public void removeFront() {
        if (head == null) {
            System.out.println("empty list");
        } else {
            head = head.getNext();
        }
        size--;
    }

    public void removeNode(T data) {
        if (head == null) {
            System.out.println("empty list");

        } else {
            LinkNode<T> current = head;
            LinkNode<T> previous = head;
            while (current.getData() != data) {
                previous = current;
                current = current.getNext();
            }
            if (current == head) {
                head = head.getNext();
            }
            previous.setNext(current.getNext());
        }
        size--;
    }

    public LinkNode<T> getNode(T data) {
        LinkNode<T> current = head;
        if (head == null) {
            System.out.println("empty list");
            return null;
        } else {
            while (current.getData() != data) {
                if (current.getNext() == null) {
                    System.out.println("not found");
                    return null;
                }
            }
        }
        return current;
    }

    private static class LinkNode<T> {
        T data;
        LinkNode<T> next;

        private LinkNode(T data, LinkNode<T> next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public LinkNode<T> getNext() {
            return next;
        }

        public void setNext(LinkNode<T> node) {
            this.next = node;
        }

        public String toString() {
            return ("\nData: " + data);

        }

    }

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<String>();
        list.addEnd("a");
        list.addEnd("aaa");
        list.addEnd("aaaaaa");
        list.removeNode("aaa");
        list.display();
    }

}

My main concern is how differently every one writes these implementations.

\$\endgroup\$
3
\$\begingroup\$

This is a great first attempt with a consistent coding style and good variable names. Bravo!

  • Consider implementing the java.util.List interface so you could use it with existing methods. You already have most of the methods and would just need to change some names. For example, addEnd becomes append, getNode becomes indexOf (with some changes), etc. It defines quite a few more methods entailing more work, but it would make for a great exercise.

  • You can remove the constructor since it has no effect. Unlike C, Java initializes all local variables and fields to default values determined by their types, unless the declaration provides a value. References are initialized to null, numeric types to 0, booleans to false, etc.

  • Never expose private inner classes publicly. Instead of returning a LinkNode, getNode should return the index of the found node. If you want to allow clients to change the data held by a node, provide set(int index, T data) and optionally replaceFirst(T data, T replacement) to avoid seeking the node twice.

  • Instead of passing null for next to the LinkNode constructor, create a second constructor that accepts just the data value. Optionally, the existing constructor may pass data to this new constructor so all fields are initialized it at most one place.

    private LinkNode(T data) {
        this.data = data;
    }
    
    private LinkNode(T data, LinkNode next) {
        this(data);
        this.next = next;
    }
    

Finally, you're treating LinkNode as a pure data-holder a la C structs which gives the list class two responsibilities. While this centralizes the logic maintaining the structure in the list, it makes the full list responsible for managing both the list itself (the head) and each node's internal state. Classes that have a single responsibility are much easier to understand, write, and test.

Moving the node-specific logic from the list to the node class would simplify many of the methods, increase DRY, and make each class responsible for one thing. I'll provide one example for addEnd to demonstrate the technique.

public void addEnd(T data) {
    if (head == null) {
        head = new LinkNode(data);
    } else {
        head.addEnd(data);
    }
}

private static class LinkNode<T> {
    ...
    void addEnd(T data) {
        if (next == null) {
            next = new LinkNode(data);
        } else {
            next.addEnd(data);
        }
    }
}

One thing to note is that this turns many of the algorithms into recursive methods which requires more stack space (memory) since Java doesn't have tail recursion.

\$\endgroup\$
  • \$\begingroup\$ Thanks for all the feedback and help. I am wondering about what would I have the MyLinkedList class do if I move all the node methods to the LinkedNode class. Does it just hold a pointer to head and print the list? \$\endgroup\$ – gallly Jan 29 '14 at 4:13
  • 1
    \$\begingroup\$ @CatznDogz The list class would have one responsibility: manage the head reference. Anything that touches data or next would move to the node class. Note that this option may not be better for many reasons; the higher memory usage is one example. I would recommend rewriting it this way as an exercise only after you're happy with your list since your primary goal is learning about linked lists. \$\endgroup\$ – David Harkness Jan 29 '14 at 4:44
  • 1
    \$\begingroup\$ I'd suggest using the AbstractSequentialList as a base class, you only need to implement size() and a ListIterator \$\endgroup\$ – ratchet freak Jan 29 '14 at 9:16
  • \$\begingroup\$ @ratchetfreak If the point was to implement a linked list with minimal effort, I'd agree. But in this case the OP wants to learn how to implement one on their own. \$\endgroup\$ – David Harkness Jan 29 '14 at 18:51
  • \$\begingroup\$ @DavidHarkness I would use this(data, null) in the LinkNode constructor rather than the other way around so all data assignation is in the same place. \$\endgroup\$ – njzk2 Jan 29 '14 at 22:04
4
\$\begingroup\$

Here are a few comments I would make:

  • You can keep a permanent reference to the tail, which makes appending at the end o(1) operation rather than o(n)
  • You can make a double-link list, by keeping reference to next and previous links. Deletion of the last link becomes o(1) instead of o(n)
  • Your removeNode methods crashes if the node is not in the list

Apart from that, I think David Harkness said it all.

\$\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.