연결리스트의 길이를 알아내는 자바스크립트 프로그램

연결된 리스트는 길이가 가변 가능한 선형 데이터 구조입니다. 연결 리스트의 길이는 변경될 수 있습니다. 이는 배열의 배열 길이를 변경할 수 없는 문제입니다. 이 기사에서는 코드를 구현하고 극단적인 경우를 확인하여 주어진 연결 목록의 길이를 알아봅니다. 이번 글에서는 while 루프와 클래스 개념을 사용하겠습니다.

문제 소개

주어진 문제에서는 연결 목록이 주어졌습니다. 먼저 클래스를 사용하여 연결 목록을 만든 다음 주어진 연결 목록의 길이를 구해야 합니다. 연결된 목록의 길이는 변경될 수 있으므로 특정 코드 포인트에서 연결된 목록의 길이를 찾습니다.

두 가지 방법을 사용하겠습니다. 첫 번째는 while 루프를 사용하는 직접 반복 방법이고 다른 하나는 주어진 연결 목록의 길이를 찾는 재귀 방법입니다.

반복 방법

이 방법에서는 먼저 연결 목록에 대한 구조를 제공하는 클래스를 사용하여 연결 목록을 만듭니다. 단순히 헤더와 데이터만 전달하면 연결리스트에 값을 추가할 수 있도록 푸시(Push) 함수 등 일부 함수를 정의하겠습니다.

예

이 과정에서는 while 루프, 연결 목록의 헤드 또는 시작 노드, 연결 목록의 노드 수, 즉 주어진 연결 목록의 길이를 계산하는 변수를 사용합니다. 으아아아

위의 방법에서는 추가 공간을 사용하지 않고 연결 목록을 한 번만 탐색합니다. 따라서 위 방법의 시간복잡도는 O(N)이며, 여기서 N은 연결리스트의 크기이고, 위 방법의 공간복잡도는 O(1)이다.

재귀적 방법

이 방법에서는 위의 방법과 동일한 단계를 수행하여 연결 목록을 만들고, 주요 작업에서는 재귀 방법을 사용합니다.

예

함수 자체와는 다른 매개변수와 특정 기본 조건을 사용하여 동일한 함수를 호출하는 것을 재귀라고 합니다. 이 방법에서는 연결된 목록의 헤드를 사용하여 함수를 호출한 다음 해당 함수에서 함수를 다시 호출하지만 인수를 사용하여 현재 노드의 다음 노드를 호출합니다. 반환 값으로 1 + 재귀 호출의 반환 값을 반환하고 결과는 첫 번째 호출에서 제공됩니다. 코드를 살펴보겠습니다 -

으아아아

시간과 공간의 복잡성

재귀 방법의 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 연결 목록에 존재하는 노드 수입니다. 위 코드의 공간 복잡도는 총 N개의 호출이 있고 각 호출에 대해 현재 노드 스택을 유지해야 하기 때문에 O(N)입니다.

결론

이 튜토리얼에서는 코드를 구현하고 극단적인 경우를 연구하여 주어진 연결 목록의 길이를 찾는 방법을 배웠습니다. 첫 번째 방법에서는 이번 글의 while 루프와 클래스 개념을 사용했고, 두 번째 방법에서는 재귀적 방법을 사용하여 길이를 구했습니다. 두 방법 모두 시간 복잡도는 O(N)입니다. 여기서 N은 연결 목록의 길이이고, 재귀 방법의 공간 복잡도는 스택 크기로 인해 O(N)입니다.

위 내용은 연결리스트의 길이를 알아내는 자바스크립트 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!