Efficiency of Doubly linked list implementation in java

Question

I implemented doubly linked lists using nodes in Java. My code for the Node and linked list classes are below. Any suggestions for improving the design and/or running times of the operations?

public class Node implements Comparable<Node>{
Node next;
Node previous;
Object element;
int index;

public Node(Object element){
    this.element = element;
    this.next = null;
    this.previous = null;
}

public Node(Object element, Node next, Node previous){
    this.element = element;
    this.next = next;
    this.previous = previous;
}

public Node(Object element, Node next, Node previous, int index){
    this.element = element;
    this.next = next;
    this.previous = previous;
    this.index = index;
}

//Getter Method
public Node get_next(){
    return this.next;
}

//For comparable class
public int compareTo(Node x){
    if (this.element.equals(x.element)){
        return 0;
    }
    else
        return 1;
}

public boolean compare_index(int index){
    if (this.index == index){
        return true;
    }
    else
        return false;
}

}

public class Mylinkedlists{
Node first_node;
Node last_node;
int size = 0;

//Constructors
public Mylinkedlists(Object element){
    Node temp = new Node(element, last_node,first_node,0);
    first_node = new Node (null,temp,null);
    last_node = new Node(null,null,temp);
    size+=1;
}

public Mylinkedlists(){
    first_node = new Node (null,last_node,null);
    last_node = new Node(null,null,first_node);

}

//Returns size of Node
public int size(){
    return size;
}


//Adds element to end of linked list
public void add(Object element){        
    Node to_add = new Node(element);
    Node temp = last_node.previous;
    size+=1;

    //Pointer changes
    last_node.previous.next = to_add;
    last_node.previous = to_add;
    to_add.previous = temp;
    to_add.next = last_node;
    to_add.index = size-1;
}

//Inserts Element after node
public void insert(Object add_after, Object element_to_add) throws NotFoundException{
    Node current = first_node.next;
    Node insert_after = new Node(add_after);
    Node to_add = new Node(element_to_add); 

    //find the node
    while (current.compareTo(insert_after) != 0){
        current = current.next;
    }

    //Inserts element after node
    if (current.compareTo(insert_after) == 0){
        Node temp = current.next;
        current.next.previous = to_add;
        to_add.next = temp;
        current.next = to_add;
        to_add.previous = current; 
        size+=1;
    }
    else
        throw new NotFoundException("Element not in list");
}

//Removes element from linked list
public void remove(Object element) throws NotFoundException{
    boolean stop = false;
    Node search_for = new Node(element);
    Node current = first_node.next;

    for (int i = 0; i < size && !stop; i ++){
        //Compares nodes
        if (current.compareTo(search_for) == 1){
            current.next.previous = current.previous;
            current.previous.next = current.next;
            current.next = null;
            current.previous = null;
            size-=1;
            stop = true;
        }
        else 
            current = current.next;
    }

    //If element not in list
    if (stop == false && current.next == null)
        throw new NotFoundException("Element not in list");
}

//Removes element from end of linked list
public void remove_From_End(){
    last_node.previous.next = null;
    Node temp = last_node.previous.previous;
    last_node.previous.previous = null;
    last_node.previous = temp;
    last_node.previous.next = last_node;

    size -= 1;
}

//Returns true if list contains element, else false
public boolean contains(Object element){
    boolean contains = false;
    Node current = first_node.next;
    Node with_element = new Node(element);

    while (current.next != null){
        if (current.compareTo(with_element) == 0)
            return true;
        else
            current = current.next;
    }
    return contains;
}

public Object get(int index) throws NotFoundException{
    if (index < 0 ||  index > (size-1))
        throw new NotFoundException("Index out of range");

    Node current = first_node;
    for (int i = 0; i <= index; i++){
        current = current.next;
    }

    return current.element;
}


public String toString(){
    String temp = "";
    Node temp2 = first_node;
    for (int i = 0 ; i < size; i++){
        temp2 = temp2.next;
        temp += String.valueOf(temp2.element) + " ";
    }

    return temp;
}
}

For example, I access the elements of the Node class directly using dot(.) notation. Are getter and setter methods the only alternative? Moreover, is there any other implementation of the get method that would take less than O(n) time?

Answer 1

It is impossible for access to a linked list to take less than O(n). You will need to traverse through the array to access indivividual elements. There are faster ways to access individual elements, but that would require changing your data structure. The easiest data structure that I can think of would be an array. But then your insert and remove would be O(n).

So, in choosing your data structure, the question becomes what will you be doing more of insert and remove, or get?