우리의 숙제는 자바 LinkedList 구현이 이중 연결이며 단독 연결되지 않았다는 것을 증명하도록 요구합니다. 그러나 요소 추가, 요소 제거 및 요소 찾기와 같은 목록 작업은 두 구현 모두에서 동일한 복잡성을 갖는 것으로 보이므로 성능 인수를 사용하여 Java의 이중 연결 특성을 증명하는 방법이없는 것처럼 보입니다 LinkedList. 누구든지이 둘의 차이점을 설명하는 더 좋은 방법을 알고 있습니까?단일 연결 목록과 이중 연결 목록간에 성능 차이가 있습니까?
"앞뒤"요소 등을 제거하고 앞으로 또는 뒤로 방향으로 반복하십시오.
우리는 결국 마지막 요소를 찾아 보았습니다. 이것은 잘 돌아갔다. 감사! –
단일 노드와 이중 노드를 고려하십시오.
클래스 SingleLinkedNode { E 데이터; SingleLinkedNode next; }
클래스 DoubleLinkedNode { E 데이터; DoubleLinkedNode 이전; DoubleLinkedNode next; }
DoubleLinkedList에서 제거하려면 (노드를 이미 찾았 으면 (매우 다르다)) 우리는 무엇을해야합니까?
우리가 SingleLinkedList에서 제거하려는 경우 (노드를 이미 찾았 으면 매우 다른 것입니다) 어떻게해야합니까?
당신은 그것이 단일 링크 목록에서 두 배보다 더 빠르다는 것을 의미한다고 생각할 것입니다.
그러나 이전 노드에 대한 참조가없는 경우 노드를 삭제하려면 어떻게해야합니까? 우리는 다음에 대한 참조 만 가지고 있습니다. prev를 찾기 위해 목록에서 다른 모든 검색을 수행하지 않아도 될까요? : -O
* "이전에 찾기 위해 목록에서 다른 모든 검색을 수행해야하지 않습니까?"*. 사실 아니. 단일 링크 된 목록을 알맞게 구현하면 그렇게 할 수 없습니다. –
@Stephen 노드의 단일 링크 된 목록에 노드 이전의 참조가 어떻게 있습니까? – corsiKa
노드를 찾으려면 목록을 탐색하는 동안 이전 노드에 대한 참조도 유지해야합니다. 즉 당신이 방금 다음에 부른 사람. 그래서 당신은 다음과 같은 것을가집니다 : Node tmp = head, prev; while (node.data! = findItem) {prev = tmp; tmp = tmp.next; } 이제 after 루프 (목록의 항목 인 경우) tmp는 제거 할 노드이고 prev는 노드이므로 beforev.next = tmp.next; 그리고 사라 졌어요! ;-) –
그것은 매우 쉬운 증거 - 소스 코드를보고 각 노드가 .previous 포인터 : http://www.docjar.com/html/api/java/util/LinkedList.java.html
자바 List 인터페이스는 당신이 할 수있는 방법이없는이 있는지 볼 연결된 목록을 검색하지 않고 항목을 제거합니다. indexed 엔트리를 찾기 위해 목록을 스캔해야하는 remove (int index)가 있으며 목록을 스캔해야하는 remove (Object o)도 있습니다. 연결된 목록 구현은 검색하는 동안 필요한 이전 항목 항목 컨텍스트를 저장할 수 있으므로 제거는 단일 및 이중 링크 목록에 대해 동일한 복잡성을 갖습니다. 이 상태는 반복자에도 저장 될 수 있으므로 Iterator.remove()는이를 변경하지 않습니다. 그래서 나는 당신이 퍼포먼스 제거에서 말할 수 있다고 생각하지 않는다.
제 생각 엔 "올바른"대답은 첫 번째 또는 마지막 개체를 검색 할 때 크기가 다른 여러 목록을 만들고 .indexOf() 및 .lastIndexOf()의 성능을 향상시키는 것입니다. 구현이 이중 연결되어 있다고 가정하고 .indexOf()에 대한 목록의 시작 부분부터 검색하고 끝에 대해 검색합니다.lastIndexOf()는 길이에 따라 또는 길이에 독립적입니다.
궁극적 인 증거는 소스 코드를 읽는 것입니다. 그러나 나는 숙제가 무엇을 요구하는지 의심 스럽다 :-) –
@Stephen +1 - 때로는 무차별 방식이 가장 좋습니다! 유니에서 나는 그의 숙제로 나의 룸메이트를 도왔다. 문제는 그것이 3 자 체이서 암호라고 말했습니다. 나는 '그'라는 단어가 그 안에 들어있는 확률은 얼마 일까? 그리고 17k 가지의 가능성 밖에 없다 ... "그의 교수는 깊은 인상을받지 못했다. 그의 코드는 또한 대부분의 코드보다 훨씬 짧았습니다! – corsiKa