연결된 목록에서 N번째 노드를 가져오는 함수를 작성하기 위한 JavaScript 프로그램

링크드 리스트는 모든 노드가 다음 노드의 주소를 저장하여 서로 연결되는 선형 데이터 구조입니다. 연결 리스트에서 n번째 노드를 찾는다는 것은 주어진 연결 리스트에서 n번째 노드의 값을 얻는 것을 의미하며, 이는 반복 방법과 재귀 방법을 통해 수행할 수 있습니다.

예

으아악

출력

으아악

설명: 세 번째 노드의 값은 3입니다.

반복 방법

이 방법에서는 마지막 노드나 원하는 노드에 도달할 때까지 while 루프를 사용하여 연결 리스트를 직접 순회합니다.

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 연결 목록의 크기입니다. 여기에 주어진 숫자는 주어진 연결 목록의 크기보다 작을 수 있지만 최악의 경우 연결 목록의 길이만큼만 탐색하게 됩니다.

여기서는 추가 공간을 사용하지 않습니다. 이는 위 코드의 시간 복잡도가 O(1)임을 의미합니다.

재귀적 방법

이 방법에서는 while 루프 대신 재귀 호출을 사용하여 연결된 목록을 순회하고 이전 논리를 구현합니다.

예

으아악

출력

으아악

시간과 공간의 복잡성

위 코드의 시간 및 공간 복잡도는 동일하며 둘 다 O(N)입니다. 여기서 N은 주어진 연결 목록의 노드 수입니다. 여기 공간은 재귀 호출로 인해 발생합니다.

결론

이 튜토리얼에서는 주어진 연결 목록에서 n번째 노드를 찾는 JavaScript 프로그램을 구현했습니다. n번째 노드가 존재하지 않으면 존재하지 않는다고 인쇄하고, 그렇지 않으면 해당 노드에 존재하는 값을 인쇄합니다. 우리는 두 가지 방법을 구현했는데, 하나는 while 루프를 사용하여 반복하는 방법이고 다른 하나는 재귀적인 방법입니다. 둘 다의 시간 복잡도는 O(N)이지만 추가 공간이 필요하지 않으므로 반복이 더 좋습니다.

위 내용은 연결된 목록에서 N번째 노드를 가져오는 함수를 작성하기 위한 JavaScript 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!