java - java中双向链表实现的效率

Question

我使用 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 方法是唯一的选择吗？此外，是否还有其他 get 方法的实现时间少于 O(n) 时间？

Answer 1

访问链表的时间不可能少于O(n)。您将需要遍历数组才能访问各个元素。有更快的方法来访问各个元素，但这需要更改您的数据结构。我能想到的最简单的数据结构是数组。但是你的插入和删除将是O(n)。

因此，在选择数据结构时，问题就变成了您将更多地进行插入和删除，还是获取？