[음악 재생] 

DOUG 로이드 : 좋아,에 이렇게 물론이 시점, 우리는 C의 기초를 많이 다루었 우리는 변수, 배열에 대해 많이 알고 포인터, 모든 좋은 물건. 사람들은 모든 종류의 내장되어 있습니다 에는 기본으로 볼 수 그러나 우리는 바로, 더 많은 일을 할 수 있습니까? 우리는 일을 결합 할 수 있습니다 함께 재미있는 방법. 

그래서 시작하자, 그럼 그렇게하자 C가 우리에게주는 무슨에서 분기로, 우리 자신의 데이터를 생성하는 시작 이 건물을 사용하는 구조 함께 블록은 뭔가를 유용, 정말 소중한. 우리는이 작업을 수행 할 수있는 하나의 방법입니다 컬렉션에 대해 이야기합니다. 그래서 지금까지, 우리는 데이터의 종류를 가졌다 컬렉션을 나타내는 구조 의 값과 유사한 값을 좋아한다. 즉, 배열이 될 것이다. 우리는 정수의 집합을 가지고, 또는 그래서 문자의 컬렉션. 

구조는 데이터의 정렬된다 정보를 수집하기위한 구조, 하지만 값처럼 수집하지 않습니다. 그것은 일반적으로 상이한 데이터 유형 믹스 함께 하나의 상자의 내부. 하지만 그 자체는 아니다 함께 체인에 사용 또는 함께 유사한 연결 배열과 같은 항목. 배열은 위해 중대하다 요소는 찾아 볼하지만 리콜 그것은 매우 어려운 일이 배열에 삽입, 우리가 삽입하지 않는 한 그 배열의 맨 끝. 

그리고 가장 좋은 예는 내가 가진 그것을 위해 삽입 정렬입니다. 당신은 우리의 비디오를 기억하는 경우 삽입 정렬에, 많은이 있었다 비용 필요에 참여 요소를 선택하고이를 이동합니다 뭔가에 맞게하는 방법 중 배열의 중간에. 어레이는 또한 다른 고통 문제있는 유연성이다. 우리는 배열을 선언 할 때, 우리는 하나의 기회를 얻을. 우리는 내가 원하는 말하세요 이 많은 요소. (100)이 될 수 있습니다, 그것은 수도 1,000 수, 그것은 수도 X는 사용자가 해당 번호 여기서 X 될 프롬프트에서 또는 명령에서 우리를 준 선. 

그러나 우리는 만에 하나의 기회를 얻을, 우리 실제로, 다음 오 말을하지 않는다 (101)를 필요로하거나, 나는 X 플러스 (20)를 필요로했다. 너무 늦게, 우리가 이미 선언 한 배열, 우리는 101을 얻으려면 X 플러스 20, 우리는 선언해야 완전히 다른 배열, 어레이의 모든 요소를​​ 복사 이상, 그리고, 우리는 충분히 있습니다. 그리고 우리가 다시 잘못된 경우 어떻게, 무엇을 우리가 실제로 (102), 또는 X 플러스 40 필요한 경우, 우리는 다시이 작업을 수행 할 수 있습니다. 그래서 그들은 매우 유연성이있어 우리의 데이터 크기를 조정하기위한, 하지만 우리는 함께 몇 가지 결합하는 경우 우리는 이미했습니다 기초의 포인터와 구조에 대해 배웠습니다, 특히, 동적 메모리를 사용 의 malloc와 할당, 우리 함께 이러한 조각을 넣을 수 있습니다 새로운 데이터 structure--을 만들 수 있습니다 단독 우리가 say-- 수있는 목록을 연결 즉 우리가 성장 할 수 있으며, 값 컬렉션 수축 우리는 낭비되는 공간이 없습니다. 

그래서 다시, 우리는이 아이디어를 호출, 이 개념, 연결리스트. 특히,이 비디오에서 우리는있어 단일 연결리스트에 대해 얘기, 다음 다른 동영상은 우리가 얘기하자 대한 이중 연결리스트, 어떤 여기에 주제에 그냥 변화이다. 그러나 단일 연결리스트 노드로 구성되어, 노드는 단지 추상적 인 term-- 인 그것은 내가 전화 했어 그냥 뭔가 그의 일종이다 구조, 기본적으로, 나는거야? 그냥에게 node--이 전화 것 노드는 두 멤버, 또는 두 개의 필드가 있습니다. 보통 데이터를 가지고 정수, 문자 플로트, 또는 소정의 다른 데이터 유형이 될 수있다 당신은 유형 데프으로 정의했다고. 그리고 그것은에 대한 포인터를 포함합니다 동일한 유형의 다른 노드. 

그래서 우리는 내부의 두 가지가 이 노드, 데이터, 포인터 다른 노드로. 그리고 당신은 시각적으로 시작하는 경우 이, 당신은 그것에 대해 생각 할 수 있습니다 노드의 사슬 같은 그 함께 연결되어 있습니다. 우리는 첫 번째 노드가 그것을 데이터, 및 포인터를 포함 포함하는 두 번째 노드에 데이터 및 제 3 노드에 대한 포인터. 그리고 그것은 우리가 그것을 부르는 이유이다 링크리스트는, 그들은 서로 연결하고있다. 

이 특별한 무엇을 노드 구조처럼? 글쎄, 당신은에 우리의 비디오에서 기억 경우 유형 데프와 함께, 사용자 정의 유형을 정의, 우리가 structure--를 정의하고 이 같은 구조를 정의 입력합니다. 구조체 sllist tyepdef, 그리고, 나는 해요 임의로 여기 워드 값을 이용하여 실제로 임의의 데이터 타입을 표시한다. 당신은, 정수 또는 부동에 전달할 수 당신은 당신이 원하는대로 가질 수있다. 그것은 단지에 국한되지 것 정수, 또는 그런 아무것도. 그래서 값은 임의 다음, 데이터 타입, 포인터 동일한 유형의 다른 노드. 

이제 조금 캐치가있다 여기 구조를 정의하는 때 그것은 자기 참조 구조입니다. 나는 임시 있어야 내 구조에 대한 이름을 지정합니다. 하루 I의 끝에 명확하게 호출 할 SLL 노드, 즉 궁극적으로 새로운 내 유형 정의의 일부를 이름, 하지만 난 SLL 노드를 사용할 수 없습니다 이 중간에. 이유이기 때문에, 내가하지 않은 형이라고 SLL 노드를 생성 여기 마지막 점을 칠 때까지. 그 시점까지는, 나는이 있어야 또 다른 방법은 이러한 데이터 타입을 참조한다. 

그리고 이것은 자체입니다 참조 데이터 유형입니다. 또한, 데이터의 종류를이야 데이터를 포함하는 구조, 다른 포인터 동일한 유형의 구조. 그래서 난을 참조 할 수 있어야합니다 이 데이터 유형, 적어도 일시적으로, 그래서 그것을 임시주는 구조체 sllist의 이름 내가 그때 내가 원하는 말을 할 수 있습니다 다른 구조체 sllist의 포인터, 구조체 sllist 스타, 다음 나는 정의를 완료 한 후, 지금은 이러한 유형의 SLL 노드를 호출 할 수 있습니다. 

당신이 거기에 볼 이​​유 그래서입니다 여기에 임시 이름, 그러나 여기에서 영구적 이름. 때때로 당신은 볼 수 있습니다 구조의 정의, 예를 들어, 그 아니다 자기 참조, 그 여기에 지정 이름이 없습니다. 그것은 단지, 형식 정의 구조체를 말할 것입니다 중괄호를 열고 다음을 정의합니다. 당신이 있다면 그러나 구조체 자체입니다 참조,이 하나이기 때문에, 당신은 지정해야합니다 임시 형의 이름입니다. 그러나 궁극적으로, 지금 우리가 이런 짓을했는지, 우리는 단지 참조 할 수 있습니다 이 노드,이 단위, 목적을 위해 SLL 노드로 이 비디오의 나머지. 

좋아, 그래서 우리는 방법을 알고있다 연결리스트 노드를 작성합니다. 우리는 정의하는 방법을 알고 연결리스트 노드입니다. 이제, 우리는 시작하려고하는 경우 정보를 수집하기 위해 그들을 사용 작업의 몇 가지가있다 우리 이해하고 함께 작동하도록해야합니다. 우리는 만드는 방법을 알 필요가 희박한 연결리스트. 어떤 목록이 이미 존재하지 않는 경우는, 우리는 하나를 시작하고 싶어. 그래서 우리는 할 수 있어야합니다 연결리스트를 만들려면 우리는 아마 검색해야 링크 목록을 우리가 찾고있는 요소를 찾을 수 있습니다. 우리는 삽입 할 수 있어야 목록에 새로운 것을, 우리는 우리의 목록이 성장 할 수 있도록합니다. 그리고 마찬가지로, 우리는 할 수 있도록하려면 우리의 목록에서 사물을 삭제하려면, 우리는 우리의 목록을 축소 할 수 있어야합니다. 그리고 끝에서 우리 프로그램, 특히 당신은 우리가 걸 기억하는 경우 동적 메모리를 할당 일반적으로이 목록을 작성하려면, 우리는 모든 메모리를 해제 할 우리는 그 작업을 수행 할 때. 그래서 우리는 삭제 할 수 있어야합니다 하나의 전체 연결리스트는 급습을 실패합니다. 그럼 통해 가자 이러한 작업의 일부 우리는 그것들을 시각화하는 방법, 특히 의사 코드에서 이야기. 그래서 우리는을 만들려면 목록을 연결, 그래서 아마 우리 함수를 정의 할 이 프로토 타입. SLL 노드 스타, 만들고, 내가 전달 해요 하나의 인수에, 어떤 임의의 데이터 어떤 임의의 데이터 형식, 다시 입력합니다. 하지만이 기능을해야 returning-- 해요 단독으로, 나에게 포인터를 반환 연결리스트 노드입니다. 다시 말하지만, 우리가 만들려고하고 희박한 연결리스트, 그래서 포인터를 필요 나는 끝났어요 그 목록. 

그래서 여기에 관련된 단계는 무엇인가? 글쎄, 내가 먼저 일을 해요 하기 위하여려고하는 것은 동적입니다 새 노드에 대한 공간을 할당합니다. 다시 말하지만, 우리는 얇은에서 그것을 만드는 공기가, 그래서 우리는 그것을 위해 malloc에​​ 공간이 필요합니다. 그리고 물론, 즉시 우리는 malloc을 한 후, 우리는 항상 있는지 확인하십시오 우리의 pointer-- 우리는 다시 널 (null)하지 않았다. 우리가 시도하는 경우 때문에 널 포인터를 복종, 우리는 고통을거야 세그 폴트와 우리는 그것을 원하지 않는다. 

그리고 우리가 현장에 기입 할, 우리는 값 필드를 초기화 할 그리고 다음 필드를 초기화합니다. 그리고 우리는 결국 같은 이러시면 원하는 우리가 원하는 indicates-- 함수 프로토 타입 SLL 노드에 대한 포인터를 반환합니다. 그래서이 시각적처럼 보이게? 음, 우선 동적거야 새로운 SLL 노드에 대한 공간을 할당, 그래서 우리는 그건 malloc-- 시각적 표현 노드의 우리는 단지 만들었습니다. 그리고 우리는 있는지 확인하십시오 또한,이 경우하지 null--있어 사진이 없을 것 이 null의 경우 찾았, 우리는 메모리가 부족했을 것이다 그래서 우리는 거기에 갈 수 있어요. 그래서 지금 우리가 C 단계에있어, 노드 값 필드를 초기화한다. 음,이 기능을 기반으로 , 내가 여기에 사용하고 전화 내가 6에 전달하려는 것처럼 보인다 그래서 값 필드에 6 것이다. 이제, 다음 필드를 초기화합니다. 그럼, 내가 거기에 할 예정이다, 아무것도 바로 옆에 없다, 이 목록에있는 유일한 것입니다. 따라서 목록에있는 다음 일은 무엇입니까? 

그것은 바로, 아무것도 가리 키지한다. 아무 것도 그래서이다, 다른 사람이 없다 우리가 알고있는 개념은 nothing--의 아무것도에 대한 포인터? 그것은 아마 우리가 원하는해야 이 널 포인터를 넣어, 내가 널을 대표합니다 같은 단지 빨간색 상자 포인터 우리는 더 이상 갈 수 없습니다. 우리가 나중에 조금 살펴 보 겠지만, 우리는 결국 사슬을해야합니다 화살표의 연결 함께 이러한 노드, 그러나 당신이 명중 할 때 빨간색 상자, 즉, 널 (null)입니다 우리는 더 이상 갈 수 없어 즉,리스트의 마지막이다. 

그리고 마지막으로, 우리는 단지 원하는 이 노드에 대한 포인터를 반환한다. 그래서 우리는 새로운 호출 할 것이다, 새로운를 반환합니다 그래서이 사용될 수있다 어떤 기능을 만들었습니다. 그래서 거기에 우리가 간다, 우리는 단독으로 만들었습니다 희박한 연결리스트 노드, 이제 우리는 우리가 일을 할 수있는 목록이 있습니다. 

이제, 이미 우리를 가정 해 봅시다 큰 체인을 가지고, 우리는 그것에서 무언가를 찾고 싶어요. 그리고 우리는 무슨 기능을 원하는 , true 또는 false를 반환 따라하기 값이이 목록에 있는지 여부에. 함수 프로토 타입, 또는 그 함수에 대한 선언, 이 항아리가 발견 BOOL 같이하고 있습니다 우리는 두 개의 인수를 전달하고 싶다. 

첫 번째는, 포인터이다 연결리스트의 첫 번째 요소. 이것은 당신이거야 실제로 뭔가 항상 추적을 유지하려면, 실제로 뭔가있을 그 당신은 글로벌 변수에 넣어. 당신이 목록을 작성하면, 항상 항상, 매우 추적 할 목록의 첫 번째 요소. 당신은 다른 모든 참조 할 수 있습니다 그 방법 단지 체인을 수행하여 요소, 포인터를 유지하지 않고 모든 단일 요소에 그대로. 에만 제 추적해야 하나 그들은 모두 서로 연결하는 경우. 

그리고 두 번째 것은 우리는 다시 전달하고 임의로 한적하다 어떤 데이터 유형 우리가있어 이 통행의 내부 희망 목록에있는 노드 중 하나. 그래서 단계는 무엇인가? 그럼, 우리가 먼저입니다 우리는 횡단 포인터를 만들 목록 헤드를 가리키는. 그럼, 왜, 우리는 이미 우리합니까 목록 헤드에 대한 포인터를 가지고, 왜 우리는 단지 주변에 하나를 이동하지? 글쎄, 난 그냥 말한 것처럼, 그것은 우리에게 정말 중요합니다 항상 추적 할 목록의 첫 번째 요소입니다. 그리고 실제로 더 나은 그것의 복사본을 만들려면 그래서 우리에게 결코 이동할 것이 없습니다 것을 사용 실수로 멀리 이동하거나 항상 우리 일부 지점에서 포인터가 오른쪽 목록의 첫 번째 요소에. 그래서를 작성하는 것이 좋습니다 우리가 이동하는 데 사용할 두 번째. 

그런 다음 우리는 단지 여부를 비교 그 노드에서의 값 필드 그것은 만약 우리가 찾고, 그리고있는 무슨이다 아니, 우리는 단지 다음 노드로 이동합니다. 그리고 우리는 일을 계속 이상, 이상, 이상, 우리 중 하나가 찾을 때까지 요소, 또는 우리는 히트 null-- 우리는 마지막에 도달했습니다 및 목록은 없다. 이 잘하면 벨을한다 당신처럼 선형 검색, 우리는 단지 그것을 복제하고 단일 연결리스트 구조 대신 할 배열을 사용. 

그래서 여기의 예 단일 연결리스트. 이것은 하나의 구성 다섯 노드, 우리는이 의 헤드 포인터 목록 호출 목록. 우리가해야 할 첫 번째 일이다 다시, 그 탐색 포인터를 만들 수 있습니다. 그래서 우리는 지금 두 개의 포인터가 같은 일에 그 시점. 

지금, 여기 통지 나는하지 않았다 TRAV에 대한 공간을 malloc을해야합니다. 나는 TRAV가 malloc에​​ 동일 말하지 않았다 뭔가, 그 노드는 이미 존재 메모리에 그 공간은 이미 존재합니다. 그래서 내가 실제로하고있어 모든입니다 그것은 또 다른 포인터를 생성. 나는 추가를 mallocing 아니에요 공간, 지금 두 개의 포인터가 같은 일을 가리키는. 

그래서 2는 내가 찾고 무엇입니까? 아니, 글쎄, 그래서 대신 내가 해요 다음 단계로 이동하는 것. 그러니까 기본적으로 나는 말할 것 TRAV 다음 TRAV 같습니다. 내가 아니, 무엇을 찾고 있어요 3입니다. 그래서 내가 가서 계속 을 통해, 결국 때까지 내가 무엇을 찾고 있어요 인 6에 도착 함수 호출에 기반을위한 나는 상단에있는 거기에, 그래서 나는 끝났어요. 

이제, 요소 내가 뭘 해요 경우 찾는 것은, 목록에없는 그것은 여전히​​ 작동하는거야? 음, 목록 통지 여기에, 미묘하게 다르다 이것은의 또 다른 한가지는 연결리스트와 중요한, 당신은 보존 할 필요가 없습니다 그 특정 순서. 당신이 원한다면 당신은 할 수 있지만, 이미 눈치 챘을 것이다 우리는 추적을 유지하지 않을 것을 우리는 무엇을 수 요소에 있습니다. 

그리고 그 한 무역의 일종이다 그 우리 배열 구절 링크 목록을 가지고, 그것은 우리가하지 않아도된다 더 이상 랜덤 액세스. 우리는 단지 내가 원하는, 말할 수 없다 0 번째 요소로 이동합니다, 또는 내 배열의 6 요소, 이는 내가 배열 할 수 있습니다. 내가 가고 싶은 말할 수 없다 0 번째의 요소, 또는 제 6 요소, 또는 내 연결리스트의 25 요소, 그들과 관련된 인덱스가 없습니다. 그리고 그것은 정말 문제가되지 않습니다 우리는 위해 우리의 목록을 유지합니다. 당신은 당신이 원하는 경우 확실히 할 수 있지만, 거기에 그들이 할 필요가없는 이유 없다 임의의 순서로 보존 될 수있다. 그래서 다시,의 시도하자 이 목록에 6을 찾을 수 있습니다. 음, 우리는 시작 시작, 우리는 (6)을 찾을 수 없습니다 그리고, 우리는 발견하지 계속 6, 우리는 결국 여기에 도달 할 때까지. 노드 그래서 지금 TRAV 점 (8)을 포함, 6은 거기에 있지 않습니다. 

그래서 다음 단계는 것 다음 포인터로 이동합니다, 그래서 TRAV 다음 TRAV 동일 말한다. 음, TRAV은 다음에 의해 표시 거기에 빨간색 상자는, null입니다. 그래서 곳이있다 이 시점에서 그렇게 가고, 우리는 우리가 도달 한 결론 수 있습니다 링크 된리스트의 끝에, 6 거기에 있지 않습니다. 그리고 그것은 반환 될 것입니다 이 경우 거짓. 

좋아, 우리가 어떻게 새로운 삽입 할 연결리스트에 노드? 그래서 우리는 만들 수있었습니다 갑자기 밖으로 연결리스트, 그러나 우리는 아마 원하는 체인을 구축하지 별개의 목록의 무리를 만듭니다. 우리는 하나의 목록을 갖고 싶어 그 , 그것의 노드 무리가 있습니다 하나의 노드 목록이 아니 무리입니다. 그래서 우리는 단지 만들기를 계속 사용 할 수 없습니다 기능을 우리는 지금, 이전에 정의 된 우리 에 삽입 할 이미 존재하는 목록입니다. 

이 경우 그래서, 우리는거야 두 개의 인수를 전달하기 위해, 그 헤드 포인터 우리가 추가 할 목록을 연결. 그렇게 왜 다시 말하지만, 그건 중요한 항상 우리가 때문 추적 정말 유일한 방법은 우리의 전체 목록은 참조해야 다만 첫 번째 요소에 대한 포인터에 의해. 그래서 우리는 전달하고자하는 그 첫 번째 요소에 대한 포인터 그리고 어떤 값 우리를 목록에 추가 할. 그리고 결국이 기능 포인터를 반환하는 것입니다 연결리스트의 새로운 머리. 

여기에 포함 된 단계는 무엇인가? 음, 그냥 만들 수와 같은, 우리는 동적으로 할당해야 새 노드를위한 공간, 그리고 확인하십시오 확실히 우리는 메모리가 부족하지 않는, 다시, 우리의 malloc을 사용하고 있기 때문이다. 그 다음 우리는 채우려 그리고, 노드를 삽입 그래서 숫자를 넣어, 어떤 발은 노드에있다. 우리는에 노드를 삽입 할 연결리스트의 시작. 

이유가 그 나는 이 작업을 수행 할 수 있으며 두 번째를 복용 가치가있을 수도 있습니다 여기에 비디오를 일시 중지하려면 내가 원하는 이유에 대해 생각 링크의 시작 부분에 삽입 목록. 다시 말하지만, 나는 앞서 언급 한 정말하지 않습니다 우리가 어떤에서 그것을 유지하는 경우 문제가 순서는, 그래서 아마 그 단서입니다. 그리고 당신은 우리가 경우에 무슨 일이 일어날 지보고 원 이러시면하거나 제에서 전 때 우리가 가고 있었다 검색을 통해 당신 무엇을 할 수 볼 수 있습니다 우리가하려고했던 일이 일어날 리스트의 끝에서 삽입. 우리는이 없기 때문에 리스트의 끝 포인터. 

그래서 그 이유는 내가 원하는 것 시작 부분에 삽입하려면 나는 바로 그것을 할 수 있기 때문이다. I는 시작 부분에 대한 포인터를 가지고, 우리는 두 번째로 시각이 표시됩니다. 하지만 마지막에 삽입 할 경우, 나는 처음부터 시작해야 모든 방법을 횡단 끝 및 다음 압정. 그래서 그런 의미 리스트의 끝에서 삽입 N의 O 될 것 작업이 다시 진행 우리의 토론에 계산 복잡도. 그것은 N 작업의 O가 될 것 목록이 더 큰, 더 큰 가지고로, 더 큰, 더 될 것입니다 및 뭔가를 압정하기가 더 어렵 말에. 그러나 그것은 항상 정말 쉽게 시작 부분에 뭔가를 압정, 당신은 처음부터 항상있어. 

그리고 우리는 다시이의 시각을 볼 수 있습니다. 그리고 우리가 한 번 완료되면 우리는 새로운 노드를 삽입 한, 우리는 우리의 포인터를 반환 할 연결리스트의 새로운 머리, 어떤 우리는에 삽입하고 있기 때문에 시작, 실제로 할 것이다 우리가 방금 만든 노드에 대한 포인터. ,이 해 시각화하자 때문에 나는 그것이 도움이됩니다 생각합니다. 

그래서 여기에 우리의 목록입니다, 그것은 구성 네 개의 요소는, 노드 (15)를 포함 어떤 노드를 가리키는 9 포함하는 13을 함유하는 노드를 가리키는, 이는이 포함 된 노드를 가리키는 널 (null)이 10, 그 다음 포인터 포인터 그래서리스트의 마지막이다. 그래서 우리는을 삽입 할 값 (12)에 새로운 노드 이것의 시작 목록, 우리는 무엇을해야합니까? 그럼, 먼저 우리는 공간의 malloc 노드, 그리고, 우리는 거기에 12을 넣어. 

그래서 지금 우리가 도달했습니다 결정 포인트, 오른쪽? 우리는 몇가 포인터 우리가 할 수 우리는 먼저 어느 이동해야 이동? 우리는 12 지점을 만들어야합니다 list--의 새로운 머리 또는 실례합니다, 우리는 12해야한다 목록의 이전 머리를 가리? 아니면 우리는 말한다 목록은 지금 (12)에서 시작한다. 차이가있다 거기에, 우리는 볼 것이다 와 두 번째에 어떤 일이 일어나는지. 

그러나 이것은 리드 사이드에 좋은 주제, 이는의 하나입니다 연결리스트와 까다로운 것들 포인터를 배열하는 것입니다 올바른 순서. 당신은 순서가 물건을 이동하는 경우, 실수로 끝날 수 있습니다 리스트의 나머지를 orphaning. 그리고 여기에 그 예입니다. 그럼 아이디어로 가자 동행입니다 물론, 우리는 단지 12을 만들었습니다. 우리는 12이 될 것입니다 알고 목록의 새로운 헤드 그리고 왜 우리는 단지 이동하지 않습니다 목록 포인터가 가리 키도록. 

좋아, 그럼 그 좋은입니다. 그래서 지금 어디에 (12) 다음 포인트는 무엇입니까? 나는 시각적으로 우리가 볼 수있는, 의미 그것은 15를 가리 것으로, 인간으로 우리에게 정말 분명하다. 어떻게 컴퓨터가 알고 있나요? 우리는 아무것도 없어 더 이상 (15)을 가리키는, 오른쪽? 

우리는 15을 참조 할 수있는 능력을 잃었습니다. 우리는 새로운 화살표 옆에 등호를 말할 수 없다 뭔가가 아무것도 없다. 사실, 우리는 고아했습니다 나머지 목록 그렇게함으로써, 우리는했습니다 실수로 체인을 깨진. 그리고 우리는 확실히 그렇게하고 싶지 않아요. 

그럼 돌아가서 다시 시도 할 수 있습니다. 어쩌면 옳은 일을해야 할 일 (12)의 다음 포인터를 설정하는 것입니다 첫 번째 목록의 이전 머리에, 우리는 목록을 통해 이동할 수 있습니다. 사실, 즉 올바른 순서로 우리가 우리가있을 때 수행해야 단일 연결리스트로 작업. 우리는 항상을 연결하려면 목록에 새로운 요소, 우리는 그런 종류의 촬영하기 전에 변화의 중요한 단계 여기서, 연결 목록의 헤드가된다. 다시, 그 같은 기본적인 일이다, 우리는 추적을 잃고 싶지 않아. 

그래서 우리는이 있는지 확인하려면 모든 것이 서로 연결되어 우리는 그 포인터를 이동하기 전에. 그리고이 올바른 순서가 될 것이다, 이는 목록 (12)에 연결하고, 다음 목록은 (12)을 시작 말한다. 우리는 목록 12에서 시작 상기 경우 그리고,리스트 (12)를 연결하려고 우리는 이미 무슨 보았다. 우리는 실수로 목록을 잃게됩니다. 

좋아, 그럼 한 가지 더 이야기합니다. 우리가 제거하려는 경우 전체가 한 번에 목록을 연결? 다시 말하지만, 우리는 mallocing있어 이 모든 공간, 그래서 우리는 우리가 완료되면이를 해제해야합니다. 그래서 지금 우리는 삭제할 전체 연결리스트. 음, 우리는 무엇을할까요? 

우리가 널 포인터에 도달 한 경우, 우리 그렇지 않으면, 그냥 삭제, 중지하려면 다음 목록의 휴식과 저를 무료로 제공됩니다. 목록의 나머지 부분을 삭제, 다음, 현재 노드를 해제. 같은 소리 무엇을, 어떤 기술이 우리가 얘기해야 에 대해 이전에 같은 소리를합니까? 다음, 다른 사람 삭제 다시 와서 나를 삭제합니다. 

즉 재귀의, 우리가 만들어 놓은 조금 작은 문제, 우리는 모두 삭제 말을하는지 또, 당신은 저를 삭제할 수 있습니다. 그리고 더 길 아래에 해당 노드 다른 사람들을 삭제 말할 것이다. 하지만 결국 우리는에 도착합니다 리스트가 null 점, 그것은 우리의 기본 케이스입니다. 

그래서이 살펴 보자, 이 작동하는 방법. 그래서 여기에 우리의 목록이다, 동일한이다 우리는 단지에 대해 얘기했다 목록 그리고 단계가있다. 많은 텍스트가 여기에있다하지만 희망을 시각화하는 데 도움이됩니다. 

그래서 우리는 잔 마셔요 나는 또한 뽑아 우리의 스택 프레임 그림까지 호출 스택에 우리의 비디오에서, 희망이 모든 함께 무슨 일이 일어나고 있는지를 보여줍니다. 그래서 여기에 우리의 의사 코드이다. 우리는 널 (null)에 도달하는 경우 포인터는, 그렇지 않으면 중지 리스트의 나머지를 삭제 다음은 현재 노드를 무료로 제공됩니다. 그래서 지금, list-- 우리가있어 포인터 에 통과하면 12 점을 파괴. (12)는 널 포인터가 아니다, 그래서 우리는있어 리스트의 나머지를 삭제하는 것. 

무엇을 삭제한다 우리의 나머지는 참여? 글쎄, 그것은을 의미 말, 파괴하는 전화 15 그의 시작입니다 우리가 파괴 할 목록의 나머지. 그리고 통화가 파괴 12 보류 가지입니다. 그것은 기다리고,이 얼 그 작업을 완료, 15를 파괴하는 전화. 

음, (15)는 널 포인터가 아니고, 그래서 말 것, 모든 권리, 물론,리스트의 나머지 부분을 삭제합니다. 목록의 나머지가 시작됩니다 9시, 그리고 우리는거야 당신이 모두 삭제 될 때까지 기다려야하는 물건, 다시 와서 나를 삭제합니다. 그럼 9 잘 말 것, 난, 널 포인터가 아니에요 그래서 여기에서 나머지에게 목록을 삭제합니다. 그리고 시도하고 13을 파괴한다. 13, 내가 널 포인터 아니에요 말한다 같은 일이, 그것은 책임을 전달합니다. 10, 10 널 포인터가 아니다 널 포인터를 포함, 하지만 10은 그 자체입니다 널 지금 포인터, 그래서 너무 벅을 전달합니다. 

그리고 지금, 거기 포인트를 나열 정말 한적을 가리 킵니다 것 나는 이미지에 더 많은 공간이 있다면, 그것은 어떤 임의의 공간을 가리 것 우리는 그것이 무엇인지 모르는. 그것은 비록 널 포인터의 목록 말 그대로 지금은 null 값의 설정됩니다. 그것은 바로 그 빨간 상자 안에 가리키는입니다. 우리는 그래서, 널 포인터에 도달 우리는 중지 할 수 있습니다, 우리는 완료. 

그리고 그 보라색 프레임에서들을 당장입니다 활성 프레임의 stack-- 위에, 하지만이 이루어집니다. 우리가 널 포인터에 도달 한 경우, 중지합니다. 우리는 아무것도하지 않는 우리 널 포인터를 해제 할 수 없습니다, 우리는 어떤을 malloc을하지 않았다 공간은, 그래서 우리는 완료. 그 기능 프레임 그래서 파괴, 그리고 우리입니다 우리가 한 부분 resume-- 우리가 데리러 다음으로 높은 하나와 떨어져있는 여기에이 어두운 파란색 프레임입니다. 그래서 우리는 우리가 떨어져 왼쪽에서 오른쪽을 선택합니다. 우리의 나머지를 삭제 목록 이미, 그래서 지금 우리는있어 현재 노드를 확보 할 것. 그래서 지금 우리는 지금이 노드를 확보하고 있습니다 우리는 함수의 끝에 도달했다. 그리고 그 기능 프레임은, 파괴 우리는 밝은 파란색 하나에서 픽업. 

그래서 나는 이미 done-- 한 말했죠 리스트의 나머지를 삭제하므로 현재 노드를 무료로 제공됩니다. 그리고 지금 노란색 프레임입니다 다시 스택의 상단에. 보시다시피 그래서, 우리는 지금이야 오른쪽에서 목록을 파괴하는 것은 왼쪽으로. 

무엇하지만, 일어 났을 것 우리는 일을 잘못된 방법으로 일을했다면? 그냥 우리가 시도 할 때처럼 요소를 추가 할 수 있습니다. 우리는 경우 체인을 엉망 경우 우리는 포인터를 연결하지 않은 올바른 순서로, 우리의 경우 단지 첫 번째 요소를 해제, 우리가 해방 된 경우 목록의 머리, 지금 우리는 를 참조 할 수있는 방법이 없습니다 리스트의 나머지. 그래서 우리는 것 고아 다, 우리는 무엇을했을 것이다 메모리 누수라고합니다. 당신은 우리의 비디오에서 기억하는 경우 동적 메모리 할당에, 그것은 매우 좋은 일이 아니다. 

같은 그래서 내가 거기 말했다 여러 작업은 우리가 작업하는 데 사용할 필요가 효과적으로 목록을 연결. 그리고 당신은, 내가 하나를 생략 눈치 챘을 것이다 링크에서 단일 요소를 삭제 목록. 내가 그 한 이유 실제로 종류의 것입니다 삭제하는 방법에 대해 생각하는 까다로운 단독에서 하나의 요소 연결리스트. 우리는 스킵 할 수 있어야합니다 목록에 뭔가있는 우리는 point-- 우리에 도착 의미 이 node--을 삭제하려면 하지만 순서대로하면 우리는 그것을 그렇게 만들려면 정보를 잃지 말고, 우리는이 연결해야 여기에 여기에 노드. 

그래서 아마 그 잘못을했다 시각적 관점에서. 그래서 우리의 시작 부분에있어 우리의 목록, 우리는을 통해 진행하고 우리는이 노드를 삭제할. 우리는 단지 그것을 삭제하는 경우 우리는 사슬을 파괴했습니다. 바로 여기에이 노드 다른 모든 것들을 의미한다, 그것은 여기에에서 체인이 포함되어 있습니다. 

그래서 우리가 실제로 무엇을해야하는지 우리는이 지점에 도착 후, 우리가 하나를 다시 진행해야하고, 이 노드에이 노드를 통해 연결, 그래서 우리는 다음 삭제할 수 있습니다 중간에 하나. 그러나 단일 연결리스트는하지 않습니다 우리가 뒤로 갈 수있는 방법을 제공한다. 그래서 우리는 하나 계속해야 두 개의 포인터, 그들을 이동 오프 단계의 종류, 뒤에 하나 다른 우리가 간다, 또는 지점에 도착으로 다음을 통해 또 다른 포인터를 보낼 수 있습니다. 그리고 당신은 그것을 볼 수 있습니다 좀 지저분를 얻을 수 있습니다. 다행히도, 우리가 또 다른 방법은 그 문제를 해결하려면 때 우리는 이중 연결리스트에 대해 이야기. 

내가 더그 로이드 해요,이 CS50입니다.