연결된 목록 구현, 머리에 추가 또는 꼬리에 추가?

필자는 머리글을 추가 할 때마다 머리글 참조를 수정하거나 머리글 참조를 수정하지 않고 꼬리말에 추가 할 때마다 링크드 목록을 추가하는 많은 구현을 보아 왔습니다. 한 대와 다른 대가의 확실한 이점이 있습니까? 어느 것이 바람직한 구현 방법입니까?연결된 목록 구현, 머리에 추가 또는 꼬리에 추가?

출처

2011-05-01 phoenix

하나는 새 노드를 머리에 놓고 다른 하나는 꼬리에 놓는다. 장점이 있는지 여부는 새 노드를 원하는 위치에 따라 다릅니다. –

전혀 이점이 없습니다. 사실 머리를 머리와 꼬리로 만드는 유일한 것은 우리가 머리와 꼬리를 부르는 것입니다. 머리를 꼬리로, 머리를 꼬리로 바꿀 수 있으며, "거꾸로"를 제외하고 똑같은 정확한 목록을 가질 수 있습니다. 연결리스트의

출처

2011-05-02 00:03:28 corsiKa

절대 간단한 구현은 (효율적) 머리에 추가 할 수 있습니다 .. 그것은 좀 물질과 반물질처럼

(이 ... 이중 연결리스트를 가정 않습니다). 꼬리에 추가하려면 현재 마지막 요소를 가리키는 두 번째 포인터가 필요합니다.

사용자는 특정 시간에 목록 길이를 쿼리 할 수있을뿐만 아니라 양쪽 끝에 추가 할 수 있고 꼬리 머리에서 목록을 탐색 할 수 있기를 원합니다 (이중 연결 목록이 필요함). 알맞은 기본 구현은이를 지원해야합니다 (java.util의 경우와 동일).

제한된 기능을 정당화하고 복구 요구 사항을 줄이기 위해 꼬리 공유와 같은 실질적인 혜택을 얻을 수있는 경우 단 링크 목록 만 사용해야합니다. ConcurrentLinkedQueue은 잠금없이 동시 실행이 가능하도록 단일 링크로 표시됩니다. 현재 길이를 알 수 없다는 절충안은 Javadocs에 언급되어 있습니다.

출처

2011-05-02 00:03:36 Thilo

솔직히 프로덕션 라이브러리의 단일 링크 된 목록 구현을 알지 못합니다. – corsiKa

@glowcoder : java.util.concurrent.ConcurrentLinkedQueue가 단독으로 링크 된 것 같습니다. – Thilo

당신은 그것이리스트인지 아닌지 논증 할 수 있습니다 (리스트 인터페이스를 구현하는 것에 대한 명백한 부족을 주목하십시오). FIFO 큐가 이중 링크의 이점을 얻지 못한다는 것은 사실입니다. – corsiKa

java.util.LinkedList는 두 기능을 모두 구현합니다. 그것은 그것을 보편적으로 만든다 - 그것을 큐 (FIFO)와 스택 (LIFO)으로 사용할 수있다.

출처

2011-05-02 00:11:15 Nulldevice

연결된 목록 구현, 머리에 추가 또는 꼬리에 추가?

답변

관련 문제