[Powered by Google Translate] 프로그래밍에서, 우리는 종종 값의 목록을 나타냅니다 할 필요가 이러한 섹션에 학생들의 이름과 같은 최신 퀴즈 나 자신의 점수. 

C 언어에서 배열을 사용할 수 있습니다 선언 목록을 저장할 수 있습니다. 이 목록의 요소를 열거 쉽게 배열에 저장하면 액세스해야하는 경우 또는 i 번째 목록 요소를 수정 어떤 임의의 색인에 대한 I, 그는 일정한 시간에 수행 할 수 있습니다 하지만 배열도 단점이 있습니다. 

우리가 그것들을 선언 할 때, 우리는 말을해야하고 그들이 얼마나 큰 앞, 그게 저들이 저장할 수있는 얼마나 많은 요소입니다 얼마나 큰 이러한 요소이며, 자신의 유형에 의해 결정된다. 예를 들어, INT 도착지 (10) 10 개의 항목을 저장할 수 있습니다 그 정수의 크기입니다. 

우리는 선언 후 배열의 크기를 변경할 수 없습니다. 우리가 더 많은 요소를 저장하려는 경우 우리는 새로운 배열을 만들 수 있습니다. 이러한 제한이 존재하는 이유는 우리의 프로그램은 전체 배열을 저장 메모리의 연속 된 덩어리로. 이 우리 배열에 저장되어있는 버퍼이라고 말을합니다. 다른 변수가있을 수 있습니다 배열 바로 옆에 위치 메모리에, 그래서 우리는 수 없습니다 그냥 배열 더합니다. 

때때로 우리는 배열의 빠른 데이터 액세스 속도를 교환하고 싶습니다 좀 더 유연성. 연결리스트, 다른 기본 데이터 구조를 입력합니다 여러분은 다음과 같은 익숙한되지 않을 수 있습니다. 높은 수준에서, 연결리스트는 노드의 순서대로 데이터를 저장 그는 링크로 서로 연결되어 따라서 이름이 '연결 목록입니다.' 디자인에 우리가 보게 될이 차이 다른 장점과 단점에 이르게 배열보다. 

다음은 정수의 매우 간단한 연결리스트에 대한 몇 가지 C 코드입니다. 당신은 우리가 각 노드를 대표 한 것을 알 수 있습니다 2 가지를 포함하는 구조체와 같은 목록에서, '발'이라고 저장하는 정수 목록에있는 다음 노드와 링크 우리는 불리는 포인터로 대표되는 '옆에.' 이렇게, 우리는 전체 목록을 추적 할 수 1 노드에 단지 하나의 포인터로, 그리고 우리는 다음 포인터를 추적 할 수 2 노드까지, 3 노드까지, 4 노드까지, 등, 우리는 목록의 끝에 얻을 때까지. 

당신이이 한 이점을 볼 수 있습니다 정적 배열 구조 이상 - 연결리스트와 함께 우리는 모두 메모리의 큰 덩어리 필요하지 않습니다. 목록의 첫번째 노드는 메모리에 이런 곳에서 살 수 과 2 노드는 여기까지가 될 수 있습니다. 메모리에 그게 어디 우리는 모든 노드에 상관없이받을 수 없습니다 때문에 각 노드의 다음 포인터는 1 노드에서 시작 정확히 옆에 가서 우리에게 알려줍니다. 

또한, 우리는 전방을 말 할 필요가 없습니다 얼마나 큰 연결 목록은 우리가 정적 배열과 방법이 될 것입니다 우리는 목록에 노드를 추가 유지할 수 있기 때문에 오래 공간이 새로운 노드의 메모리에 어딘가가 있습니다. 따라서 링크 된 목록은 동적으로 크기를 조절하기 쉽습니다. 나중에 프로그램에서 우리가 더 많은 노드를 추가 할 필요가, 말 목록에. 즉석에서 목록에 새 노드를 삽입하기 위해, 우리가해야 할 일은, 그 노드에 대한 메모리를 할당 is 데이터 값에 털썩, 우리가 적절한 포인터를 조정하여 원하는 위치 다음 넣습니다. 

예를 들어, 우리는 사이에 노드를 배치하고자 할 경우 목록의 2 층과 3 노드,  우리 모두에서 2 층 또는 3 노드를 이동 할 필요가 없습니다 것입니다. 우리가이 빨간색 노드를 삽입하는 말. 우리가해야할 일은이 새 노드의 다음 포인터를 설정 3 노드를 가리 키도록 그리고 2 노드의 다음 포인터를 해킹 새로운 노드를 가리 키도록. 그래서, 우리는 우리가 즉시에 우리의 목록을 크기를 조절할 수 있습니다 우리의 컴퓨터가 색인 생성에 의존하지 않기 때문에 것은 오히려으로 저장하기 위해 포인터를 사용하여 연결 있습니다. 

그러나,의 단점은 연결 목록 즉, 정적 배열과는 달리, 컴퓨터는 목록의 중간에 점프 할 수 없습니다. 컴퓨터가 연결리스트의 각 노드를 방문 가지고 있기 때문에 다음 단계로 나가려면, 그것은 특정 노드를 찾으려면 좀 걸릴 거예요 이 배열에서와보다. 전체 목록 비례 시간이 걸립니다 통과하는 목록의 길이, 또는 O (n)이 점근 표기법 인치 평균적으로 모든 노드에 도달 또한 시간은 N에 비례 소요됩니다. 

자, 실제로 몇 가지 코드를 작성하게 그 연결리스트와 함께 작동합니다. 우리가 그 정수의 연결 목록을 원하는 말한다. 우리는 다시 우리의 목록에서 노드를 나타낼 수 이 필드 구조체로, '발'이라는 정수 값 하고 목록의 다음 노드에 다음 포인터. 음, 아주 간단 것 같습니다. 

우리가 그 함수를 작성하려는 말 어떤 탐색에서 목록과 지문을 값 목록의 마지막 노드에 저장됩니다. 음, 우리가 목록에서 모든 노드를 통과해야합니다 의미 마지막 하나를 찾을 수 있지만, 우리는 추가하지 때문에 또는 아무 것도 삭제, 우리는 변경하지 않으 목록에있는 다음 포인터의 내부 구조. 

그래서, 우리는 우리가 탐색을 위해 특별히 포인터가 필요합니다 있는 우리는 '크롤러'을 클릭합니다. 전화 할게요 이 목록의 모든 요소를​​ 크롤링합니다 다음 포인터의 사슬을 따라. 우리가 저장 한 모든은 1 노드에 대한 포인터입니다 목록의 또는 '머리'. 1 노드로 향을 가리 킵니다. 이 유형의 포인터 - 투 - 노드의입니다. 

목록에서 실제 첫번째 노드를 나가려면, 우리는 역 참조에이 포인터를 가지고 우리는 그것을 역 참조하기 전에 그러나, 우리는 확인해야합니다 포인터 먼저 널 (null) 인 경우. 가 널 (null)이라면, 목록은 비어 있습니다 그리고 우리는 목록이 비어 있기 때문에, 메시지를 출력한다 마지막 노드가 없습니다. 그러나, 우선은 목록이 비어 있지 말한다. 그렇지 않을 경우, 우리는 전체 목록을 크롤링해야 우리는 목록의 마지막 노드에 도착 할 때까지, 우리는 목록의 마지막 노드를 찾고 있다면 어떻게 우리가 알 수 있습니까? 

음, 노드의 다음 포인터가 널 (null) 인 경우는, 우리는 말에 걸 알아 마지막으로 다음 포인터를 가리 키도록 목록에 다음 노드가 없을 것이다 때문입니다. 항상 null로 초기화 마지막 노드의 다음 포인터를 유지하는 것이 좋습니다입니다 우리는 목록의 끝에 도달했을 때 우리에게 알려주는 표준화 된 속성이 할 수 있습니다. 

따라서 크롤러 → 다음이 null 인 경우는, 화살표 구문은 dereferencing에 대한 바로 가기입니다 기억 구조체에 대한 포인터가 다음 액세스 어색한에 해당 그 다음 필드 : (* 크롤러). 다음. 일단 우리가 마지막 노드를 발견했습니다 우리는 크롤러 → 발을 인쇄 할 현재 노드의 값 어떤 우리가 알고있는 것은 마지막 하나입니다. 그렇지 않으면, 우리는 목록의 마지막 노드에 아직없는 경우, 우리는 목록에있는 다음 노드로 이동해야 그게 마지막이야면 확인합니다. 이 작업을 수행하려면, 우리는 우리의 크롤러 포인터를 설정 현재 노드의 다음 값을 가리 키도록하면, 즉, 목록에있는 다음 노드입니다. 이것은 설정하면됩니다 크롤러 = 크롤러 → 다음. 그런 다음 우리는 예를 들어 루프와 함께,이 과정을 반복 우리는 마지막 노드를 찾을 때까지. 따라서 예를 들어, 크롤러가 머리로 연결 한 경우, 우리는 크롤러 → 다음을 가리 키도록 크롤러를 설정 이는 1 노드의 다음 필드와 동일합니다. 자, 이제 우리 크롤러는 2 노드를 가리키는 그리고, 다시, 우리는 루프와 함께이 작업을 반복 우리가 마지막 노드를 찾을 때까지, 즉, 어디 노드의 다음 포인터가 null로 가리키고 있습니다. 그리고 우리는 가지고 우리가 목록의 마지막 노드를 발견하고, 그 값을 인쇄하려면 우리는 크롤러 → 발을 사용합니다. 

가로 지르는 그렇게 나쁘지 않습니다,하지만 삽입은 어때? 할 수 있습니다 우리는 4 위치로 정수를 삽입 할 말 정수 명단에 없어요. 그것은 현재의 3 층과 4 노드 사이입니다. 다시 말하지만, 우리가 할 수있는 목록을 통과해야 3 요소, 우리는 이후에 삽입하는 하나 얻을. 그래서, 우리는 목록을 순회 다시 크롤러 포인터를 만들 우리 헤드 포인터가 null이면 확인 그렇지 않을 경우, 머리 노드에서 크롤러 포인터를 지정하십시오. 그래서, 우리는 우리가 1 요소에있다. 우리는 우리가 삽입 할 수 있습니다 전에이 더 많은 요소를 앞으로 가야 그래서 우리는 루프에 대해 사용할 수 있습니다 INT I = 1; 전 <3; 전 + + 그리고 루프의 각 반복에서, 한 노드에 의해 진행 크롤러 포인터를 전진 현재 노드의 다음 필드가 null 인 경우 선택하여, 그렇지 않은 경우와 다음 노드에 우리의 크롤러 포인터를 이동 현재 노드의 다음 포인터에게 같 설정하여. 그럼, 우리를위한 루프 그렇게는하지 말부터 두 번, 우리는 제 3 노드에 도달했습니다 한 번 크롤러 포인터가 후 노드에 도달 있는 우리는 새로운 정수를 삽입 할 어떻게 실제로 삽입하지? 

음, 새로운 정수가 목록에 삽입 할 수 있습니다 자신의 노드 구조체의 일환으로, 이게 정말 노드의 순서이기 때문이다. 자,이 노드에 새로운 포인터를 만들어 먹자 'new_node,'라고 하고 설정 우리가 할당하는 메모리를 가리 키도록 노드 자체에 대한 힙에, 우리가 할당하는 방법을 많은 메모리를 필요합니까? 음, 노드의 크기, 우리는 우리가 삽입 할 정수하기 위해 발 필드를 설정하고 싶습니다. 자, 6, 말한다. 이제 노드의 정수 값이 포함되어 있습니다. 이 새로운 노드의 다음 필드를 초기화하는 것도 좋은 방법입니다 null로 지정하는 것은, 하지만 지금은 뭐? 

우리는 목록의 내부 구조를 변경해야 그리고 다음 포인터가 목록의 기존에 포함 된 3 층 및 4 노드. 다음 포인터가 목록의 순서를 결정하기 때문에 우리는 새로운 노드를 삽입하고 있기 때문에 오른쪽 목록의 중간에, 그건 좀 까다로운 수 있습니다. 기억하기 때문에 우리 컴퓨터입니다 만 목록에서 노드의 위치를​​ 알고 이전 노드에 저장된 다음 포인터 때문에. 그래서, 우리는 우리가 이제까지 이러한 위치의 추적을 잃은 경우 목록에서 다음 포인터 중 하나를 변경하여 말 예를 들어, 우리가 변경 말 3 노드의 다음 필드 여기 좀 노드를 가리 킵니다합니다. 우리가하지 않기 때문에 우리는 운이있을 어디 목록의 나머지 부분을 찾을 수 있는지가 그리고 분명히 정말별로. 그래서, 우리는 우리가 주문에 대한 정말 조심해야 우리는 삽입하는 동안 우리의 다음 포인터를 조작하는 인치 

그래서,이를 단순화시키기 위해, 보자 그 우리의 처음 4 노드 포인터의 사슬을 나타내는 화살표와 함께, A, B, C, 및 D라고합니다 노드를 연결하는. 그래서, 우리는 우리가 새로운 노드를 삽입 할 필요가 노드 C와 D. 사이에 이것은 정확한 순서에 할 중요하다, 그리고 왜 내가 당신을 보여 드리죠. 

가 먼저해야 할 잘못된 방법으로 살펴 보도록하겠습니다. 이봐 요, 우리가 새로운 노드가 C 후에 바로 올 수 없다는 걸 알아, 그러니 C의 다음 포인터를 설정할 수 new_node을 가리 키도록. 좋아, 좋아 보이네요, 우리는이 지금 완료해야 D에 새 노드의 다음 포인터 지점을 만드는 하지만 대기, 어떻게 그렇게 우리 할 수​​ 있습니까? D가 어디 우리에게 말해 줄 수있는 건, 다음 포인터가 이전에, C에 저장되었습니다 그러나 우리는 그 포인터를 했고요 새 노드를 가리 키도록하면, 그래서 우리는 더 이상 D가 메모리에 존재하는 어떤 단서가 없다 우리는 목록의 나머지 부분을 잃었습니다. 큰일 났네. 

따라서, 우리는이 권리를 어떻게해야합니까? 첫째, D.에 새 노드의 다음 포인터를 가리 이제 모두 새로운 노드의와 C의 다음 포인터 동일한 노드 D를 가리키고 있으며, 하지만 괜찮아. 이제 우리는 새 노드에서 C의 다음 포인터를 가리킬 수 있습니다. 그래서, 우리는 우리가 데이터의 손실없이 이런 짓을했습니다. 코드에서 C는 현재 노드입니다 순회 포인터 크롤러는,를 가리키고 있다는 와 D는 현재 노드의 다음 필드로 점을 지적 노드로 표시됩니다 또는 크롤러 → 다음. 그래서, 우리는 우리가 먼저 새 노드의 다음 포인터를 설정 크롤러 → 다음을 가리 키도록하면, 우리가 new_node의 다음 포인터가해야했다 같은 방법 그림에서 D로 연결. 그런 다음, 우리는 현재 노드의 다음 포인터를 설정할 수 있습니다 우리의 새로운 노드로, 우리가 도면에 new_node하기 위해 C를 가리 키도록 기다려야했다대로. 지금은 모든것을 위해, 그리고 우리는 잃지 않았어요 모든 데이터를 추적하고, 우리가 할 수 있었다 목록의 중간에 새로운 노드를 꽂다 모든 일을 재건하거나 어떤 요소를 이동하지 않고 방법은 우리는 고정 길이 배열로했을 거에요. 

따라서 링크 된 목록은 기본하지만, 중요한 것은, 동적 데이터 구조 아르 이는 장점과 단점을 모두 가지고 배열과 다른 데이터 구조에 비해, 그리고 종종 컴퓨터 과학에있는 경우입니다 그것은 각 도구를 사용하는 경우 알고하는 것이 중요합니다 그래서 당신은 오른쪽 작업에 적합한 도구를 선택할 수 있습니다. 

더 많은 연습으로 기능을 쓰고 연결된 목록에서 노드를 삭제 - 당신은 정렬 순서에 대한주의를 기억 귀하의 목록의 덩어리를 잃게되지 않도록하기 위해 다음 포인터 - 또는 연결된 목록에서 노드를 계산하는 함수 연결리스트의 노드의 모든 순서를 반대로하거나 재미 하나. 

내 이름은 잭슨 Steinkamp,​​ 이쪽은 CS50입니다.