1

Java のノードを使用して二重リンク リストを実装しました。Node クラスとリンク リスト クラスのコードは次のとおりです。操作の設計および/または実行時間を改善するための提案はありますか?

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;
}
}

たとえば、ドット (.) 表記を使用して Node クラスの要素に直接アクセスします。getter メソッドと setter メソッドは唯一の代替手段ですか? さらに、O(n) 時間よりも短い get メソッドの他の実装はありますか?

4

1 に答える 1

0

リンクされたリストへのアクセスにかかる時間は よりも短くはありませんO(n)。個々の要素にアクセスするには、配列をトラバースする必要があります。個々の要素にアクセスするより高速な方法がありますが、それにはデータ構造を変更する必要があります。私が考えることができる最も簡単なデータ構造は配列です。しかし、あなたのinsertandremoveは になりますO(n)。

したがって、データ構造を選択する際の質問は、さらにinsertand remove、またはget?をどうするかということになります。

于 2014-11-06T21:16:15.593 に答える