Simple singly linked list in Java

Posted on

Problem

The list is pretty simple, here is my code:
ILinkedList.java

package datastructures;

public interface ILinkedList<T> {
    public enum posForOperation { BEGGINIG,BEFORE ,AFTER ,END }
    public class Node<T>{
        T data;
        Node next;
        public Node(T data){
            this.data = data;
            this.next = null;
        }
    }
    public Node newNode(T data);
    public void add(posForOperation insert_at, T data);
    public void add(posForOperation insert_at, T data, Node node);
    public void delete(posForOperation delete_at);
    public void delete(posForOperation delete_at, Node node);
    public void deleteAtPos(int pos);
    public Node search(T data);
    public void print(); // for debugging
}

LinkedList.java

package datastructures;

public class LinkedList<T> implements ILinkedList<T> {
    private Node head;
    private Node end;
    public LinkedList(T data){
        Node new_node = new Node(data);
        head = new_node;
        end  = new_node;
    }
    @Override
    public Node newNode(T data) {
        return new Node(data);
    }

    @Override
    public void add(ILinkedList.posForOperation insert_at, T data) {
        Node new_node = newNode(data);
        if(insert_at == ILinkedList.posForOperation.BEGGINIG){
            new_node.next = head;
            head = new_node;
        }
        else if(insert_at == ILinkedList.posForOperation.END){
            end.next = new_node;
            end = new_node;
        }
    }

    @Override
    public void add(ILinkedList.posForOperation insert_at, T data, Node node) {
        if(insert_at == ILinkedList.posForOperation.BEFORE){
            Node tmp = head; 
            while(tmp.next != node && tmp.next != null){
                tmp = tmp.next;
            }
            Node new_node = newNode(data);
            new_node.next = node;
            tmp.next = new_node;
        }
        else if(insert_at == ILinkedList.posForOperation.AFTER){
            Node new_node = newNode(data);
            new_node.next = node.next.next;
            node.next = new_node;
        }
        else // in case of misuse
            add(insert_at, data);
    }

    @Override
    public void delete(ILinkedList.posForOperation delete_at) {
        if(delete_at == ILinkedList.posForOperation.BEGGINIG){
            head = head.next;
        }
        if(delete_at == ILinkedList.posForOperation.END){
            Node tmp = head;
            while(tmp.next != end && tmp != end){ // the second condition is in case that head = end
                tmp = tmp.next;
            }
            tmp.next = null;
            end = tmp;
        }
    }

    @Override
    public void delete(ILinkedList.posForOperation delete_at, ILinkedList.Node node) {
        if(node.next == null)
            delete(ILinkedList.posForOperation.END);
        else if(delete_at == ILinkedList.posForOperation.AFTER){
            node.next = node.next.next;
        }
        else if(delete_at == ILinkedList.posForOperation.BEFORE){
            Node tmp = head;
            while(tmp.next != node){
                tmp = tmp.next;
            }
            tmp.next = node.next;
        }
        else //in case of misuse
            delete(delete_at);
    }

    @Override
    public ILinkedList.Node search(T data) {
        Node tmp = head;
        while(tmp.data != data && tmp != null){
            tmp = tmp.next;
        }
        return tmp;
    }

    @Override
    public void deleteAtPos(int pos) {
        Node tmp = head;
        for (int i = 0; i < pos-1 && tmp != null; i++){
            tmp = tmp.next;
        }
        delete(ILinkedList.posForOperation.AFTER, tmp);
    }

    @Override
    public void print() {
        Node tmp = head;
        while(tmp != end){
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }
}

Solution

Initial impressions:

  • public Node newNode(T data) shouldn’t be on the interface, why would anything outside of the list need to construct one?
  • print shouldn’t be on the interface, I know you say it’s for debugging, but a better approach would be to provider an iterator so that something outside the list could iterate the items and print them.
  • I don’t like the fact that Node is visible outside of the list class. It reveals too much of the underlying functionality. What happens if I call ‘newNode’ then pass the contents of it to the delete method?
  • One of your delete methods takes in a ‘delete_at’ parameter, then ignores it in certain conditions and deletes the last member of the list instead…

    public void delete(ILinkedList.posForOperation delete_at, ILinkedList.Node node) {
            if(node.next == null)
                delete(ILinkedList.posForOperation.END);
            else if(delete_at == ILinkedList.posForOperation.AFTER){
    
  • void deleteAtPos(int pos), there’s no way for a caller to really know where in the list an item is (unless they count as they insert them?), so what’s the purpose of this method?

Leave a Reply

Your email address will not be published. Required fields are marked *