LinkedList 반전

Question

그래서 O (N) 시간/공간의 링크 된 목록을 역전해야합니다.

이 구현은 자바 표준 라이브러리 (노드 자체에 대한 액세스 권한을 부여하지 않음)의 LinkedList 클래스 만 사용하여 구현 한 것입니다.

Answer 1

아니요, 그렇지 않습니다. input.get(idx);은 그 자체가 O(idx)이므로 구현이 2 차로 시간적으로 이루어집니다.

이터레이터를 사용하시는 것이 좋습니다 (또는 더 나은 것은 아직 listIterator).

편집 : 또한 쉽게 재배치하여 holdPopped를 제거 할 수 있습니다.

holdPopped.add 크기를 전달하여 공간 (O (n))을 미리 할당하므로 시간과 공간 모두에서 O (1)이됩니다.

IIRC, holdLL.add은 시공간적으로 O (1)로 상각됩니다. 때로는 더 많거나 때로는 적지 만 전체 공간은 n이므로 O (n)까지 평균화해야합니다. holdLL.ensureCapacity을 사용하여 분석을 단순화 할 수 있습니다.

Answer 2

은 "더 좋은 방법은"당신은 자바 LinkedList 클래스는 방법

• addFirst
• addLast
• removeFirst
• removeLast

의 각을 가지고 있다는 사실을 악용 할 수 있습니다 부탁 이들은 O (1)입니다.

몇 가지 방법으로 O (n) 시간 및 공간 동작을 얻을 수 있습니다. 그러한 방법은 다음과 같습니다

LinkedList<E> b = new LinkedList<E>(); 
while (!a.isEmpty()) { 
    b.addFirst(a.removeFirst()); 
} 
a.addAll(b); 

이 "제자리에"반전을한다 (즉, 변수 a 참조 항상 동일한 개체). 임시 저장소로 스택을 사용하는 것과 같습니다 (b이 "스택"입니다).

추한 복사에도 불구하고 O (n) 시간 및 O (n) 공간입니다.

Answer 3

Java API에는 O (n) : Collections.reverse(List<?> list)으로 완료되는이 방법이 있습니다. 이것이 숙제라고 가정 할 때 직접 구현해야하지만 실생활에서는 라이브러리 함수를 사용합니다.

또는 반전 O (1)을 만드는 역 장식을 만들 수 있습니다. 개념의 예는 다음과 같습니다.

public class ReversedLinkedList<T> extends LinkedList<T> { 

    private final LinkedList<T> list; 

    public ReversedLinkedList(LinkedList<T> list) { 
    this.list = list; 
    } 

    public Iterator<T> descendingIterator() { 
    return list.iterator(); 
    } 

    public Iterator<T> iterator() { 
    return list.descendingIterator(); 
    } 

    public T get(int index) { 
    int actualIndex = list.size() - index - 1; 
    list.get(actualIndex); 
    } 

    // Etc. 
} 

데코레이터가 구체적인 클래스를 확장하는 것은 일반적으로 (항상?) 나쁜 형식이라는 점에 유의하십시오. 이상적으로는 공용 인터페이스를 구현하고 공용 인터페이스의 인스턴스로 생성자 매개 변수를 받아 들여야합니다. LinkedList가 많은 인터페이스 (예 : Dequeue, List 등)를 구현하기 때문에 위의 예는 설명을위한 것입니다.

또한 여기에 일반적인 "시기 상조 최적화가 잘못되었습니다"라는 설명을 삽입하십시오. 실제로 목록에 병목 현상이있는 경우이 역방향 dequeue 클래스를 실생활에서 만들면됩니다.

Answer 4

당신은 항상 아파치 평민를 확인해야합니다, 그들은 LinkedList의 및 컬렉션 일반적으로 더 나은 및 더 유연한 구현이있다; 당신이 목록을 되돌리고 싶은 경우 당신이 이중 연결리스트를 사용하는

https://commons.apache.org

그리고 둘째로, 그것은 더 쉬울 것이다.