링크드리스트에 대한 위키피디아 기사에 따르면 링크드리스트 중간에 삽입하는 것은 O (1)로 간주됩니다. 나는 그것이 O (n)이라고 생각할 것입니다. 목록의 끝 부분에있을 수있는 노드를 찾을 필요가 없습니까?
이 분석은 노드 작업의 발견 (필수적이지만)과 삽입 자체를 설명하지 않습니까?
수정 :
연결된 목록은 배열에 비해 몇 가지 장점이 있습니다. 목록의 특정 지점에 요소를 삽입하는 것은 일정한 시간 작업이지만 배열에 삽입하려면 요소의 절반 이상을 이동해야 할 수 있습니다.
위의 진술은 나에게 약간 오해의 소지가 있습니다. 내가 틀렸다면 정정하지만 결론은 다음과 같아야한다고 생각합니다.
어레이 :
- 삽입 / 삭제 지점 찾기 O (1)
- 삽입 / 삭제 수행 O (n)
연결된 목록 :
- 삽입 / 삭제 지점 찾기 O (n)
- 삽입 / 삭제 수행 O (1)
나는 당신이 위치를 찾을 필요가 없을 것이라고 생각한다 (어떤 경우에는 머리와 꼬리처럼) 당신이 그것에 대한 일종의 포인터를 유지하는 것입니다. 따라서 연결 목록이 항상 삽입 / 삭제 옵션에 대해 배열을 능가한다고 단호하게 말할 수는 없습니다.
답변
이 기사는 “인덱싱”을 별도의 작업으로 간주합니다. 따라서 삽입 자체는 O (1)이지만 중간 노드에 도달하는 것은 O (n)입니다.
답변
삽입 자체는 O (1)입니다. 노드 찾기는 O (n)입니다.
답변
아니요, 삽입하기로 결정하면 이미 목록을 반복하는 중이라고 가정합니다.
연결된 목록에 대한 작업은 일반적으로 일반적인 “목록”이 아니라 노드 모음으로 처리되는 방식으로 수행되는 경우가 많습니다. 노드 자체를 주 루프의 반복자로 생각하십시오. 따라서 목록을 살펴보면서 비즈니스 로직의 일부로 새 노드를 추가 (또는 이전 노드를 삭제)해야한다는 사실을 알게되고 그렇게합니다. 한 번의 반복으로 50 개의 노드를 추가 할 수 있으며 각 노드는 인접한 두 노드의 연결을 해제하고 새 노드를 삽입 할 시간이 O (1)입니다.
편집 : 이봐, 당신은 첫 번째 응답자가 아닌 두 번째 단락을 입력하고 갑자기 첫 번째 4와 같은 것을 말하는 5 번째입니다!
답변
차트가 보여주는 배열과 비교하기 위해 새 노드 이후에 모든 항목을 이동할 필요가 없기 때문에 O (1)입니다.
예, 그들은 당신이 이미 그 노드에 대한 포인터를 가지고 있거나 포인터를 얻는 것이 사소하다고 가정하고 있습니다. 즉, 문제는 ” X에 주어진 노드 ,이 노드 뒤에 삽입 할 코드는 무엇입니까?” 삽입 지점에서 시작합니다.
답변
연결 목록에 삽입하는 것은 전체를 반복하는 것과 다릅니다. 항목을 찾는 것이 아니라 포인터를 재설정하여 항목을 거기에 넣습니다. 앞쪽 끝이나 끝 근처에 삽입할지 여부는 중요하지 않지만 삽입에는 여전히 포인터가 다시 할당됩니다. 물론 구현 방법에 따라 다르지만 이것이 목록의 강점입니다. 쉽게 삽입 할 수 있습니다. 인덱스를 통해 액세스하는 것은 배열이 빛나는 곳입니다. 그러나 목록의 경우 일반적으로 n 번째 항목을 찾는 것은 O (n)입니다. 적어도 그것이 학교에서 기억하는 것입니다.
답변
루핑을 포함하지 않기 때문입니다.
삽입은 다음과 같습니다.
- 요소 삽입
- 이전 링크
- 다음 링크
- 끝난
이것은 어떤 경우에도 일정한 시간입니다.
따라서 n 개의 요소를 차례로 삽입하는 것은 O (n)입니다.
답변
이 분석은 노드 작업의 발견 (필수적이지만)과 삽입 자체를 설명하지 않습니까?
맞아요. 지정된 지점에 삽입하면 다음에 삽입하려는 항목에 대한 포인터가 이미 있다고 가정합니다.
InsertItem(item * newItem, item * afterItem)
