일일 코딩 문제: 한 번에 연결 목록에서 k번째 인덱스 제거

한 번에 연결된 목록에서 k번째 인덱스 제거

해결해야 할 또 다른 문제가 있어서 돌아오신 것을 환영합니다! 오늘 우리는 연결된 목록과 해당 요소 제거를 다루고 있습니다. 연결된 목록이 무엇인지에 대해 조금 논의하고, 목록을 만들고, 목록에서 요소를 제거하는 방법을 살펴보겠습니다.

시작하기 전에 일반적인 면책 사항은 다음과 같습니다.

• 이러한 문제는 구독할 수 있는 멋진 뉴스레터 Daily Coding Problem에서 제공됩니다. 여기 . 확인해 보시고, 여러분의 과제도 해결해 보세요!

• 저는 전문 프로그래머가 아닙니다. 단지 자신의 샷을 공유하기를 좋아하는 사람일 뿐입니다! 알고리즘에 대한 더 낫거나 더 빠른 솔루션이 있다면 댓글로 제출해 주세요! 나는 이것에 대해 좀 더 배우고 싶습니다!

  
  

충분히 고민하세요. 문제로 넘어가자!

연결된 목록과 정수 k 주어지면 목록 끝에서 k번째 노드를 제거하고 목록의 선두를 반환합니다.

k 는 목록의 길이보다 작다는 것이 보장됩니다.

이 작업을 한 번에 수행하세요.

그렇다면 여기서 무슨 일이 일어나고 있는지 조금 설명하겠습니다. 연결 목록과 목록에서 제거할 인덱스 요소 k 제공됩니다. 그 다음에는 연결리스트의 헤드를 반환해야 합니다.

마지막으로 이 모든 작업을 단 한 번의 패스로 수행해야 합니다. 즉, 목록을 두 번 이상 반복할 수 없습니다.

또한 인덱스 k 목록에 포함되어 있음 을 보장하므로 목록의 실제 길이를 초과하는지 확인할 필요가 없습니다.

오늘 우리는 Go를 사용하여 알고리즘을 구축할 것입니다. Go의 구문은 이런 종류의 작업에 훌륭하고 동시에 이해하기 매우 간단하기 때문입니다.

처음부터 시작해 보겠습니다. 간단한 연결 목록을 작성해 보겠습니다.

연결리스트

연결된 목록의 개념은 매우 간단합니다. 개체(보통 노드 라고 함)로 구성된 목록이고 각 노드에는 값 (실제로 노드에 포함된 항목)과 다음 노드에 대한 링크 라는 두 가지 속성이 있어야 합니다.

일반적으로 포인터는 한 노드에서 다른 노드로 이동하기 위한 링크로 사용됩니다.

또한 목록의 첫 번째 노드는 일반적으로 목록의 헤드 라고 불리며, 문제에서 반환하도록 요청되는 노드이기도 합니다.

다음은 그래픽 예입니다.

왼쪽의 첫 번째 노드는 목록의 헤드로, 해당 값 v₀와 목록을 다음 노드 n₁로 리디렉션하는 메모리 포인터 P(n₁)를 포함합니다 . 다음 노드 n₁ 에는 해당 값과 다음 노드에 대한 포인터 P(n2)가 포함됩니다.

물론 최종 노드에는 가리킬 것이 없으므로 해당 포인터의 값은 null 이 됩니다.

이를 생성하는 코드를 살펴보겠습니다!

코드는 매우 간단합니다. 두 개의 구조를 생성합니다. 하나는 내부 노드용이고 다른 하나는 연결 목록용입니다.

• 방금 본 것처럼 노드에는 Value 속성과 다음 노드에 대한 포인터로 *Node 유형을 보유하는 Next 속성이라는 두 가지 속성이 있습니다.

• 연결된 목록은 연결된 목록을 "초기화"하는 구조로, 목록의 Head 라는 하나의 속성만 갖습니다.

  
  

그 후, 간단히 메인 함수에서 리스트를 초기화하고 리스트의 헤드에 임의의 값 10을 갖는 노드를 제공합니다.

연결된 목록을 이해하는 핵심은 이제 Head 노드가 Node 유형이므로 본질적으로 다음 노드를 포함 Head Next 속성을 갖게 된다는 것입니다. 그러면 이 마지막 노드는 다음 노드로 이동하기 위한 Next 속성을 갖게 됩니다.

목록에 일부 노드를 추가하면 모든 것이 더 명확해 지므로 그렇게 해 봅시다! 우리에게는 두 가지 옵션이 있습니다. 수동으로 수행하거나, 매우 지루한 작업이거나, 링크된 목록 클래스에 대한 메서드를 작성하여 노드를 더 추가하는 것입니다. 확인 해보자!

노드 추가: 변장된 변경 가능 목록

프로그래밍 경험이 거의 없더라도 거의 모든 프로그래밍 언어에서 가장 먼저 들어야 할 개념 중 하나는 변경 가능 목록과 불변 목록의 차이입니다.

이름에서 알 수 있듯이 변경 가능한 목록은 요소를 조작하고 추가할 수 있는 목록입니다 . 대신 불변 요소는 고정된 크기를 가지며 새 요소를 추가할 수 없습니다 . 그런데 왜 그럴까?

불변 목록은 메모리에 연속 되어 있습니다. 즉 해당 요소는 메모리에 순차적으로 저장 됩니다. 3개 요소 목록의 경우 첫 번째 요소가 0x00에 저장되면 두 번째 요소는 0x01에 저장되고 마지막 요소는 0x02에 저장됩니다.

CPU가 단순히 메모리 인덱스를 하나씩 호출하기 때문에 Python에서 고정 배열, 불변 목록 또는 튜플을 반복하는 것이 매우 빠른 이유입니다.

반면에 변경 가능한 목록은 처음 초기화될 때만 메모리에서 연속적입니다. 그 시점에서 요소가 추가되면 더 이상 순차적이지 않습니다. 그렇다면 어떻게 루프를 반복할 수 있을까요?

글쎄, 첫 번째 시작의 마지막 요소에는 그 요소가 그 뒤에 추가된 포인터가 있기 때문에 추가된 요소를 가져오는 등의 작업이 수행됩니다. 그렇습니다. 변경 가능한 목록은 위장된 연결 목록인 경우가 많습니다!

이제 코드를 살펴보겠습니다.

연결 목록의 메서드에 AddNode 메서드를 추가했습니다. 노드를 추가하는 프로세스는 다음과 같습니다.

• 먼저 Head 값을 current 라는 변수에 저장합니다.

• 다음으로, 다음 노드가 null이 될 때까지 매번 다음 노드로 current 변수를 업데이트하는 연결된 목록을 반복합니다. 현재 우리가 있는 노드에 널 포인터가 있으면 목록의 마지막 노드에 있다는 것을 알 수 있습니다.

• 마지막으로 이 마지막 노드를 새 노드와 새 값으로 업데이트합니다. (이 새 노드의 Next 포인터는 공백으로 두면 null로 설정됩니다.)

  
  

그래픽적으로 이 프로세스는 다음과 같습니다.

주 함수에서 연결된 목록의 노드 값을 인쇄하여 이 메서드가 올바르게 작동하는지 확인할 수 있습니다.

노드 제거

이제 문제에 대한 마지막 부분과 해결책을 살펴보겠습니다. 올바른 인덱스를 가진 노드를 제거하는 것입니다. 먼저 연결리스트에서 노드를 제거한다는 것은 무엇을 의미합니까? 생각해보면 연결리스트의 노드는 이전 노드와 연결되어 있어야만 존재하는 것이 겠죠?

예를 들어, n-1ᵗʰ에 Next 값을 null로 지정하면 목록에서 nᵗʰ 값의 연결을 끊을 수 있습니다.

제거하려는 요소가 마지막 요소가 아니면 어떻게 되나요? 음, 이전 요소를 다음 요소에 연결하여 요소의 연결을 해제 할 수 있습니다!

따라서 kᵗʰ 요소를 제거하려면 k-1ᵗʰ 요소를 찾아서 k+1ᵗʰ 노드에 연결해야 합니다. 이전 노드(k-1ᵗʰ)를 저장해야 합니다.

분명히 목록을 직접 색인화할 수는 없습니다 . linkedlist[n] 과 같은 것을 시도하면 오류가 발생할 뿐입니다. 하지만 이를 감안할 때 목록의 헤드를 인덱스 0으로, 다음 노드를 인덱스 1로 간주할 수 있으며 이전에 했던 것처럼 노드를 반복할 수도 있습니다.

그러면 우리가 할 수 있는 일은 우리가 있는 노드를 추적하는 카운터를 구현하는 것입니다!

그럼 코딩해보자.

index 속성을 받아들이는 RemoveNode 함수를 살펴보겠습니다. 그런 다음 세 가지 변수를 초기화합니다.

• previousNode - 이전 노드를 보유합니다.

• 루프 동안 우리가 있는 노드를 유지하는 current

• counter , 처음에는 0과 동일하며 목록에서 위치를 유지합니다.

  
  

잠시 동안 첫 번째 if 블록을 건너뛰고 대신 for 루프에 집중하겠습니다. counter 변수가 index 보다 엄격하게 작아질 때까지 루프를 시작합니다. 각 루프는 이전 노드를 현재 노드로 업데이트하고 현재 노드와 카운터를 업데이트합니다.

루프가 중단되면 이는 원하는 인덱스 바로 앞의 노드에 있다는 의미입니다. 이전 노드 prev.Next 의 포인터를 우리가 있는 목록의 다음 노드로 업데이트하면 됩니다. 현재 상태입니다 current.Next . 마지막으로 연결리스트의 헤드를 반환합니다.

이제 제거할 인덱스가 인덱스가 0인 헤드라면 어떻게 될까요? 루프는 counter = 0 및 index = 0 으로 시작하고 조건은 즉시 false가 되므로 시작되지 않습니다. 상단의 if 블록을 사용하여 이 첫 번째 사례를 관리할 수 있습니다.

기본적으로 인덱스가 0이면 링크드 리스트의 헤드를 옆에 있는 노드로 직접 업데이트하고 반환할 수 있습니다. 특히 31행에 주의를 기울이고 싶습니다. 다른 많은 언어와 마찬가지로 Go는 값으로 속성을 함수에 전달합니다 . 즉, 함수는 전달하는 실제 객체가 아닌 전달된 객체 의 복사본을 유지한다는 의미입니다. .

이 개념은 다음 예에서 명확하게 나타납니다.

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

속성으로 전달된 값의 메모리 주소를 인쇄하는 함수를 만듭니다. 그런 다음 메인 함수에서 변수 a를 생성하고 해당 메모리 주소를 출력합니다. 그런 다음 동일한 변수를 함수에 전달하고 해당 변수의 메모리 주소를 인쇄합니다.

보시다시피, 시도하면 결과가 달라집니다. 이는 속성이 함수에 값으로 전달되기 때문입니다. 즉, 함수에 전달할 목적으로 a 의 복사본이 생성된다는 의미입니다.

연결 리스트로 돌아가서, 위의 동일한 문제에 대한 실제 헤드를 얻으려면 포인터를 사용해야 합니다. 따라서 "실제" ll.Node 에 도달하려면 포인터인 *ll.Node 기억 하고 *ll.Node = *ll.Node.Next 를 사용하여 더 멀리 이동해야 합니다 .

기본 함수에서는 ll.RemoveNode(0) 및 ll.RemoveNode(2) 호출과 같은 메서드 호출을 추가하고 노드 0과 노드 2가 누락되는 결과를 확인할 수 있습니다.

결론

우리는 끝까지 해냈습니다!

여기까지 읽으셨다면 제 모든 감사의 마음을 전합니다. 좋아요를 한두 개 남기고 기사를 공유한다면, 그것은 제 하루를 즐겁게 만들고 이 기사를 계속 쓰는 데 도움이 될 것입니다!

다음 기사에서 뵙겠습니다. 언제나처럼 읽어주셔서 감사합니다.

니콜라