데이터 교환 없이 연결 리스트의 노드를 교환하는 JavaScript 프로그램-JS 튜토리얼-php.cn

데이터 교환 없이 연결 리스트의 노드를 교환하는 JavaScript 프로그램

WBOY

풀어 주다： 2023-08-24 20:05:02

앞으로

819명이 탐색했습니다.

用于在不交换数据的情况下交换链表中的节点的 JavaScript 程序

데이터 교환 없이 연결된 목록의 노드를 바꾸는 JavaScript 프로그램은 연결된 목록의 노드 순서를 재정렬하는 것과 관련된 웹 개발의 일반적인 문제입니다. 연결된 목록은 노드로 구성된 데이터 구조이며, 각 노드에는 데이터 조각과 목록의 다음 노드에 대한 참조가 포함됩니다.

이 기사에서는 JavaScript를 사용하여 데이터를 교환하지 않고 연결 목록의 노드를 교환하는 방법에 대한 전체 튜토리얼을 배웁니다. 먼저 교환 노드를 정의한 다음 튜토리얼을 계속 진행하겠습니다. 그러니 계속 배워보세요!

교환 노드

연결된 목록에서 노드를 바꾸는 것은 두 노드의 위치를 바꾸는 것을 의미합니다. 연결리스트의 노드를 교환하는 방법에는 여러 가지가 있습니다. 한 가지 접근 방식은 노드 간에 데이터를 교환하는 것이지만, 이는 대량의 데이터를 처리할 때 비효율적일 수 있습니다. 또 다른 접근 방식은 포인터를 노드로 바꾸는 것입니다. 데이터를 복사할 필요가 없기 때문에 이는 더 효율적입니다.

예를 통해 교환 노드를 이해해 봅시다

예

아래와 같은 연결 리스트가 있다고 가정해보세요 -

1 -> 2 -> 3 -> 4 -> 5

우리는 두 번째와 네 번째 노드를 교환하여 다음을 얻고 싶습니다.

1 -> 4 -> 3 -> 2 -> 5

노드에서 데이터를 교환하지 않고 이를 수행하려면 노드 간의 링크를 수정해야 합니다. 결과 연결 목록은 원래 연결 목록과 동일한 데이터를 가져야 하지만 노드 순서가 변경되었습니다.

그래서 먼저 교체할 두 노드(노드 2와 노드 4)를 식별합니다. 또한 목록에서 이러한 노드 전후의 노드를 추적해야 합니다.

이 예에서 노드 2 앞과 뒤의 노드는 각각 1과 3입니다. 노드 4 앞과 뒤의 노드는 각각 3과 5입니다.

다음으로 노드 간 링크를 업데이트해야 합니다. 먼저 노드 2 이전 노드의 다음 포인터를 노드 4로 설정합니다. 그런 다음 노드 2의 다음 포인터를 노드 5로 설정합니다(노드 4가 이제 노드 2 뒤에 있으므로). 마지막으로 노드 4의 다음 포인터를 노드 3으로 설정합니다(노드 2가 이제 노드 4 뒤에 있으므로).

생성된 링크 목록은 다음과 같습니다 -

1 -> 4 -> 3 -> 2 -> 5

Note - 각 노드의 데이터는 변경되지 않고 노드 순서만 변경됩니다.

이제 데이터 교환 없이 연결 리스트의 노드를 교환하는 데 사용할 알고리즘을 살펴보겠습니다.

알고리즘

STEP1: 교환해야 하는 두 노드를 식별

첫 번째 단계는 교체해야 하는 두 노드를 식별하는 것입니다. 노드 A와 노드 B를 교환한다고 가정합니다.

2단계: 교환할 두 노드 중 이전 노드를 찾습니다

연결리스트에서 노드 A와 B보다 먼저 노드를 찾아야 합니다. 우리는 이 노드를 각각 PrevA와 PrevB라고 부릅니다.

3단계: 다른 노드를 가리키도록 이전 노드의 다음 포인터를 업데이트합니다

이제 올바른 노드를 가리키도록 PrevA 및 PrevB의 다음 포인터를 업데이트해야 합니다. 여기에는 PrevA의 다음 포인터가 노드 B를 가리키도록 업데이트하고 PrevB의 다음 포인터가 노드 A를 가리키도록 업데이트하는 작업이 포함됩니다.

4단계: 올바른 노드를 가리키도록 교체할 노드의 다음 포인터를 업데이트합니다

다음으로, 올바른 노드를 가리키도록 노드 A와 B의 다음 포인터를 업데이트해야 합니다. 여기에는 노드 B 옆의 노드를 가리키도록 노드 A의 다음 포인터를 업데이트하고, 노드 A 옆의 노드를 가리키도록 노드 B의 다음 포인터를 업데이트하는 작업이 포함됩니다.

5단계: 교체해야 하는 다른 노드에 대해 위 단계를 반복하세요

두 개 이상의 노드를 교체해야 하는 경우 교체해야 하는 각 노드 쌍에 대해 위 단계를 반복할 수 있습니다.

이 단계를 완료하면 연결 목록의 노드가 교체되지만 해당 노드의 데이터는 교체되지 않습니다. 이제 위의 알고리즘을 Javascript를 사용하여 구현하는 예를 통해 이해해 보겠습니다.

예

이 프로그램에서는 먼저 연결리스트의 노드를 생성하기 위한 "Node" 클래스를 정의하고, 연결리스트를 생성하고 운용하기 위한 "LinkedList" 클래스를 정의합니다. "LinkedList" 클래스의 "swapNodes" 함수는 이전에 설명한 스왑 알고리즘을 구현합니다.

으아악