한 번에 연결된 목록에서 k번째 인덱스 제거  해결해야 할 또 다른 문제가 있어서 돌아오신 것을 환영합니다! 오늘 우리는 연결된 목록과 해당 요소 제거를 다루고 있습니다. 연결된 목록이 무엇인지에 대해 조금 논의하고, 목록을 만들고, 목록에서 요소를 제거하는 방법을 살펴보겠습니다.  시작하기 전에 일반적인 면책 사항은 다음과 같습니다.  이러한 문제는 구독할 수 있는 멋진 뉴스레터 Daily Coding Problem에서 제공됩니다.  . 확인해 보시고, 여러분의 과제도 해결해 보세요!   여기  저는 전문 프로그래머가 아닙니다. 단지 자신의 샷을 공유하기를 좋아하는 사람일 뿐입니다! 알고리즘에 대한 더 낫거나 더 빠른 솔루션이 있다면 댓글로 제출해 주세요! 나는 이것에 대해 좀 더 배우고 싶습니다!  충분히 고민하세요. 문제로 넘어가자!      주어지면 목록 끝에서 k번째 노드를 제거하고 목록의 선두를 반환합니다. 연결된 목록과 정수 k    는 목록의 길이보다 작다는 것이 보장됩니다. k   이 작업을 한 번에 수행하세요.  그렇다면 여기서 무슨 일이 일어나고 있는지 조금 설명하겠습니다. 연결 목록과 목록에서 제거할 인덱스 요소   제공됩니다. 그 다음에는 연결리스트의 헤드를 반환해야 합니다. k  마지막으로 이 모든 작업을 단 한 번의 패스로 수행해야 합니다. 즉, 목록을 두 번 이상 반복할 수 없습니다.  또한 인덱스   목록에   을 보장하므로 목록의 실제 길이를 초과하는지 확인할 필요가 없습니다. k 포함되어 있음  오늘 우리는 Go를 사용하여 알고리즘을 구축할 것입니다. Go의 구문은 이런 종류의 작업에 훌륭하고 동시에 이해하기 매우 간단하기 때문입니다.  처음부터 시작해 보겠습니다. 간단한 연결 목록을 작성해 보겠습니다.  연결리스트  연결된 목록의 개념은 매우 간단합니다. 개체(보통   라고 함)로 구성된 목록이고 각 노드에는   (실제로 노드에 포함된 항목)과 다음 노드에 대한   라는 두 가지 속성이 있어야 합니다. 노드 값 링크  일반적으로   한 노드에서 다른 노드로 이동하기 위한 링크로 사용됩니다. 포인터는  또한 목록의 첫 번째 노드는 일반적으로 목록의   라고 불리며, 문제에서 반환하도록 요청되는 노드이기도 합니다. 헤드  다음은 그래픽 예입니다.   왼쪽의 첫 번째 노드는 목록의 헤드로, 해당 값 v₀와 목록을 다음 노드 n₁로 리디렉션하는 메모리 포인터   포함합니다   다음 노드   에는 해당 값과 다음 노드에 대한 포인터   포함됩니다. P(n₁)를 . n₁ P(n2)가  물론 최종 노드에는 가리킬 것이 없으므로 해당 포인터의 값은   됩니다. null 이  이를 생성하는 코드를 살펴보겠습니다!   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true  코드는 매우 간단합니다. 두 개의 구조를 생성합니다. 하나는 내부 노드용이고 다른 하나는 연결 목록용입니다.  방금 본 것처럼 노드에는   속성과 다음 노드에 대한 포인터로   유형을 보유하는   속성이라는 두 가지 속성이 있습니다. Value *Node Next  연결된 목록은 연결된 목록을 "초기화"하는 구조로, 목록의   라는 하나의 속성만 갖습니다. Head  그 후, 간단히 메인 함수에서 리스트를 초기화하고 리스트의 헤드에 임의의 값 10을 갖는 노드를 제공합니다.  연결된 목록을 이해하는 핵심은 이제   노드가     본질적으로 다음 노드를 포함         것입니다. 그러면 이 마지막 노드는 다음 노드로 이동하기 위한   속성을 갖게 됩니다. Head Node 유형이므로 Head Next 속성을 갖게 된다는 Next  목록에 일부 노드를 추가하면 모든 것이 더 명확해 지므로 그렇게 해 봅시다! 우리에게는 두 가지 옵션이 있습니다. 수동으로 수행하거나,   지루한 작업이거나, 링크된 목록 클래스에 대한 메서드를 작성하여 노드를 더 추가하는 것입니다. 확인 해보자! 매우  노드 추가: 변장된 변경 가능 목록  프로그래밍 경험이 거의 없더라도 거의 모든 프로그래밍 언어에서 가장 먼저 들어야 할 개념 중 하나는   목록과   목록의 차이입니다. 변경 가능 불변  이름에서 알 수 있듯이   . 대신 불변 요소는   . 그런데 왜 그럴까? 변경 가능한 목록은 요소를 조작하고 추가할 수 있는 목록입니다 고정된 크기를 가지며 새 요소를 추가할 수 없습니다  불변 목록은   되어 있습니다. 즉 해당 요소는   됩니다. 3개 요소 목록의 경우 첫 번째 요소가 0x00에 저장되면 두 번째 요소는 0x01에 저장되고 마지막 요소는 0x02에 저장됩니다. 메모리에 연속 메모리에 순차적으로 저장  CPU가 단순히 메모리 인덱스를 하나씩 호출하기 때문에 Python에서 고정 배열, 불변 목록 또는 튜플을 반복하는 것이 매우 빠른 이유입니다.  반면에 변경 가능한 목록은 처음 초기화될 때만 메모리에서 연속적입니다. 그 시점에서 요소가 추가되면 더 이상 순차적이지 않습니다. 그렇다면 어떻게 루프를 반복할 수 있을까요?    요소를 가져오는 등의 작업이 수행됩니다.  글쎄, 첫 번째 시작의 마지막 요소에는 그 요소가 그 뒤에 추가된 포인터가 있기 때문에 추가된 그렇습니다. 변경 가능한 목록은 위장된 연결 목록인 경우가 많습니다!  이제 코드를 살펴보겠습니다.   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true  연결 목록의 메서드에   메서드를 추가했습니다. 노드를 추가하는 프로세스는 다음과 같습니다. AddNode  먼저   값을   라는 변수에 저장합니다. Head current  다음으로, 다음 노드가 null이 될 때까지 매번 다음 노드로   변수를 업데이트하는 연결된 목록을 반복합니다.  current 현재 우리가 있는 노드에 널 포인터가 있으면 목록의 마지막 노드에 있다는 것을 알 수 있습니다.  마지막으로 이 마지막 노드를 새 노드와 새 값으로 업데이트합니다. (이 새 노드의   포인터는 공백으로 두면 null로 설정됩니다.) Next  그래픽적으로 이 프로세스는 다음과 같습니다.   주 함수에서 연결된 목록의 노드 값을 인쇄하여 이 메서드가 올바르게 작동하는지 확인할 수 있습니다.  노드 제거  이제 문제에 대한 마지막 부분과 해결책을 살펴보겠습니다. 올바른 인덱스를 가진 노드를 제거하는 것입니다. 먼저 연결리스트에서 노드를 제거한다는 것은 무엇을 의미합니까? 생각해보면   겠죠? 연결리스트의 노드는 이전 노드와 연결되어 있어야만 존재하는 것이  예를 들어, n-1ᵗʰ에   값을 null로 지정하면 목록에서 nᵗʰ 값의 연결을 끊을 수 있습니다.  Next  제거하려는 요소가 마지막 요소가 아니면 어떻게 되나요? 음,   할 수 있습니다!  이전 요소를 다음 요소에 연결하여 요소의 연결을 해제  따라서 kᵗʰ 요소를 제거하려면 k-1ᵗʰ 요소를 찾아서 k+1ᵗʰ 노드에 연결해야 합니다.   저장해야 합니다. 이전 노드(k-1ᵗʰ)를  분명히   .   과 같은 것을 시도하면 오류가 발생할 뿐입니다. 하지만 이를 감안할 때 목록의 헤드를 인덱스 0으로, 다음 노드를 인덱스 1로 간주할 수 있으며 이전에 했던 것처럼 노드를 반복할 수도 있습니다. 목록을 직접 색인화할 수는 없습니다 linkedlist[n]  그러면 우리가 할 수 있는 일은 우리가 있는 노드를 추적하는   구현하는 것입니다! 카운터를  그럼 코딩해보자.   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true    속성을 받아들이는   함수를 살펴보겠습니다. 그런 다음 세 가지 변수를 초기화합니다. index RemoveNode    - 이전 노드를 보유합니다. previousNode  루프 동안 우리가 있는 노드를 유지하는  current    , 처음에는 0과 동일하며 목록에서 위치를 유지합니다. counter  잠시 동안 첫 번째 if 블록을 건너뛰고 대신 for 루프에 집중하겠습니다.   변수가   보다 엄격하게 작아질 때까지 루프를 시작합니다. 각 루프는  counter index 이전 노드를 현재 노드로 업데이트하고 현재 노드와 카운터를 업데이트합니다.    이는       의 포인터를   현재      루프가 중단되면 원하는 인덱스 바로 앞의 노드에 있다는 의미입니다. 이전 노드 prev.Next 우리가 있는 목록의 다음 노드로 업데이트하면 됩니다. 상태입니다 current.Next . 마지막으로 연결리스트의 헤드를 반환합니다.  이제 제거할 인덱스가 인덱스가 0인 헤드라면 어떻게 될까요? 루프는   및   으로 시작하고 조건은 즉시 false가 되므로 시작되지 않습니다. 상단의 if 블록을 사용하여 이 첫 번째 사례를 관리할 수 있습니다. counter = 0 index = 0  기본적으로 인덱스가 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 를 사용하여 더 멀리 이동해야 .  기본 함수에서는   및   호출과 같은 메서드 호출을 추가하고 노드 0과 노드 2가 누락되는 결과를 확인할 수 있습니다. ll.RemoveNode(0) ll.RemoveNode(2)  결론  우리는 끝까지 해냈습니다!  여기까지 읽으셨다면 제 모든 감사의 마음을 전합니다. 좋아요를 한두 개 남기고 기사를 공유한다면, 그것은 제 하루를 즐겁게 만들고 이 기사를 계속 쓰는 데 도움이 될 것입니다!  다음 기사에서 뵙겠습니다. 언제나처럼 읽어주셔서 감사합니다.   니콜라

Read My Stories

이 오디오는 이야기의 원래 언어로 제작되었습니다!

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

About Author

코멘트

태그 걸기

이 기사는 다음에서 발표되었습니다.

Related Stories

Crypto Growth: 효과적인 사용자 페르소나 만들기

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

포럼에서 피드까지: 소셜 미디어 알고리즘이 디지털 상호작용을 형성하는 방식

Claude Sonnet 3.5 시스템 프롬프트 유출: 법의학적 분석

Crypto Growth: 효과적인 사용자 페르소나 만들기

Floki의 Valhalla가 인도 스리랑카 투어의 보조 후원자로 합류

포럼에서 피드까지: 소셜 미디어 알고리즘이 디지털 상호작용을 형성하는 방식

Claude Sonnet 3.5 시스템 프롬프트 유출: 법의학적 분석

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps