Java에서 이중 링크 목록 구현의 효율성

Question

Java에서 노드를 사용하여 이중 연결 목록을 구현했습니다. 노드 및 연결된 목록 클래스에 대한 내 코드는 아래와 같습니다. 작업의 디자인 및/또는 실행 시간을 개선하기위한 제안 사항은 무엇입니까?

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 메소드의 다른 구현이 있습니까?

Answer 1

연결된 목록에 대한 액세스가 O(n) 미만이 될 수 없습니다. 개별 요소에 액세스하려면 배열을 탐색해야합니다. 개별 요소에 액세스하는 더 빠른 방법이 있지만 데이터 구조를 변경해야합니다. 생각할 수있는 가장 쉬운 데이터 구조는 배열입니다. 하지만 insert 및 remove은 O(n)이됩니다.

데이터 구조를 선택하면 insert과 remove 또는 get을 더 많이 처리하게 될 것입니다.