연결리스트에 노드를 삽입하는 JavaScript 프로그램

연결된 목록은 길이가 다른 데이터 구조이므로 모든 노드를 연결 목록에 삭제하거나 추가할 수 있습니다. 이 튜토리얼에서는 공간 및 시간 복잡도가 있는 연결 리스트에 노드를 삽입하기 위한 완전한 프로그램을 구현합니다. 먼저 문제 설명을 이해해 보겠습니다.

문제 소개

주어진 질문에는 연결리스트가 주어지고 연결리스트에 노드를 추가하거나 제거하여 연결리스트의 크기를 변경할 수 있으므로 연결리스트에 노드를 추가하거나 삽입하겠습니다.

연결된 목록에서는 세 가지 다른 위치(앞, 마지막 노드 뒤, 목록 중간)에 새 노드를 추가할 수 있습니다. 예를 들어 주어진 연결리스트는 -

1 -> 2 -> 3 -> 4 -> 5 -> null, 값이 9인 임의의 노드를 추가해야 합니다. 따라서 -

와 같이 노드를 추가해야 하는 경우가 많습니다.

• 처음에 노드 추가 - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

• 중간에 노드 추가 - 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

• 끝에 노드 추가 - 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null

다음 작업을 달성하는 방법을 살펴보겠습니다. -

연결된 목록의 시작 부분에 노드를 추가하세요

예

연결된 목록의 시작 부분에 노드를 추가하려면 새 노드를 만들고 연결 목록의 헤드를 새 노드에 다음 노드로 전달한 다음 헤드를 새 노드로 이동하고 새 노드를 추가해야 합니다. 연결리스트의 시작 부분에 노드를 추가합니다.

으아악

위 코드의 시간 복잡도는 O(1)입니다. 포인터만 이동하면 되고 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)이 됩니다.

링크드 리스트 중간에 노드 추가

예

연결된 목록 중간에 노드를 추가하려면 새 노드를 만들고 해당 노드를 전달해야 연결 목록의 새 노드를 새 노드의 다음 노드로 추가할 수 있습니다. 이렇게 하면 새 노드가 추가됩니다. 중간에 연결된 리스트에 노드를 추가합니다.

으아악

새 노드를 추가해야 하는 노드로 이동해야 하기 때문에 위 코드의 시간 복잡도는 O(N)입니다. 위 프로세스의 공간 복잡도는 추가 공간을 사용하지 않으므로 O(1)입니다.

링크드 리스트 끝에 노드를 추가하세요

예

연결된 목록의 끝에 노드를 추가하려면 새 노드를 만들고 해당 노드를 꼬리 노드 뒤에 추가하고 꼬리 노드를 다음 노드로 이동해야 합니다.

으아악

위 코드의 시간 복잡도는 O(1)입니다. 포인터만 이동하면 되고 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)이 됩니다.

결론

위 튜토리얼에서는 세 가지 가능한 방법으로 기존 연결 목록에 새 노드를 추가하는 방법을 배웠습니다. 우리는 설명과 시간 및 공간 복잡성이 포함된 올바른 코드를 보았습니다. 연결된 목록의 중간에 노드를 추가하는 데는 O(N) 시간이 걸리는 반면, 다른 두 경우의 시간 복잡도는 O(1)이고 세 가지 가능성 모두에 대한 공간 복잡도는 O(1)입니다.

위 내용은 연결리스트에 노드를 삽입하는 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!