[음악 재생] DOUG 로이드 : 좋아. 그래서 그냥 완료하면 단독으로 연결된 목록 미안 비디오 나는 당신을 중단 클리프 행어의 비트. 그러나 나는 당신이 완료 여기 기뻐요 이중 연결리스트의 이야기. 

당신이에서 기억한다면 그 비디오, 우리는 이야기 단독으로 연결된 방법에 대한 리스트는 우리의 능력에 참석 할 정보를 다루는 여기서, 소자의 개수 또는 상품의 수가 목록 성장 또는 축소 할 수 있습니다. 우리는 지금 처리 할 수 뭐 그런 곳 우리는 배열로 처리 할 수​​ 없습니다. 

그러나 그들은 하나에서 고통 않습니다 중요한 제한하는 단독으로 링크되어 있는지와 목록, 우리는 지금까지 이동할 수 있습니다 목록을 하나의 방향으로. 그리고 유일한 실제 상황 어디에 문제가 될 수있다 때 우리가 노력하고 있었다 단일 요소를 삭제합니다. 그리고 우리는 심지어 그것을 수행하는 방법에 대해 설명하지 않았다 의사에 단독으로 링크 된 목록에서. 그것은, 확실히 행할 수 있지만, 이 번거 로움을 조금 할 수 있습니다. 당신은 자신을 발견 그래서 경우 여기서 상황에서 당신은 삭제하려는 목록에서 하나의 요소 아니면 필요한 것 당신은 삭제 될거야 에서 하나의 요소 목록, 당​​신은 할 수 있습니다 사용을 고려하는 이중 연결 대신 단독으로 링크 된 목록으로 나열합니다. 이중 연결리스트는 당신을 수 있기 때문에 앞뒤로 모두 이동 대신 목록을 단지 앞으로 list-- 통해 단지 하나의 여분의 원소를 첨가하여 우리의 구조 정의에 이중 연결리스트 노드. 

다시 말하지만, 당신은하지 않을거야 경우 단일 요소를 삭제 할 수 list--에서 우리는 추가하고 있기 때문에 우리의 구조에 추가 필드 정의, 노드 자체 이중 연결리스트에 대한 더 큰 것입니다. 그들은 걸릴거야 메모리의 바이트 이상까지. 그리고 만약이 일이 아닙니다 당신은 할 필요 해요 당신은 그것의 결정할 수 있습니다 해제하지 가치 무역 여분을 지출해야합니다 메모리의 바이트가 필요합니다 이중 연결리스트에 대한 당신이하지 않은 경우 갈은 단일 요소를 삭제합니다. 그러나 그들은 또한 멋지다 너무 다른 것들에 대한. 

내가 말했듯이 그래서, 우리는 단지 추가해야 우리의 구조에 대한 하나의 필드 이 개념을 definition-- 이전 포인터. 단독으로 연결된 목록 그래서, 우리 값과 다음 포인터가 그래서 이중 연결리스트는있다 방법뿐만 아니라 뒤로 이동합니다. 

이제 단독으로 링크에 목록 비디오, 우리는 이야기 이들에 대한 다섯이다 당신이 할 필요가 주요 것들 수 연결리스트와 함께 작동하도록 할 수 있습니다. 그리고이 대부분 사실 그것은 이중 연결리스트가 있다고 정말 큰 도약이 아니다. 우리는 여전히 단지로를 통해 검색 할 수 있습니다 처음부터 전진은 종료합니다. 우리는 여전히 중 노드를 만들 수 있습니다 허공, 거의 같은 방법으로. 우리는 꽤 목록을 삭제할 수 있습니다 너무 많은 동일한 방법. 유일한 일이 , 미묘하게 다른 정말, 삽입하는 목록에 새 노드, 우리는 마지막으로 삭제에 대해 이야기 할 것입니다 뿐만 아니라,리스트에서 하나의 요소. 다시 말하지만, 거의 다른 세, 우리가있어 그들에 대해 이야기하지 않을 지금 그들은 단지이기 때문에 아이디어에 아주 사소한 조작 논의 단독으로 연결된 목록 비디오. 

그럼 새 노드를 삽입 할 수 이중 연결리스트로. 우리는이 일에 대해 이야기 뿐만 아니라 목록을 단독으로 연계, 하지만 여분의 몇 가지있다 이중 연결리스트로 잡는다. 우리는 [그래? 통과?]의 머리에 여기에 나열하고 어떤 임의의 값, 우리는 새로운 머리를하고 싶지 이 기능 중 목록. 이 dllnode 스타를 반환하는 이유입니다. 그래서 단계는 무엇인가? 그들은 다시, 매우 유사 목록을 단독으로 연계하는 하나의 여분의 추가와 함께. 우리는 새로운 공간을 할당 할 노드와 체크는 유효입니다 확인합니다. 우리는 그 노드를 채우려 어떤 정보를 우리 그 안에 넣고 싶다. 마지막 것은 우리를 do-- 필요 우리가해야 할 여분의 것, rather-- 이전 포인터를 수정하는 것입니다 목록의 이전 머리. 기억 때문에 의 이중 연결리스트, 우리는 앞으로 나아갈 수 있습니다 및 backwards--하는 각 노드가 실제로 가리키는 것을 의미한다 두 개의 다른 노드 대신 한 것이다. 그래서 우리는 수정해야 목록의 이전 머리 의 새로운 머리 뒤로 가리 뭔가이었다 연결리스트, 우리는 전에 할 필요가 없었다. 그리고 이전과 같이, 우리는 단지를 반환 목록의 새로운 헤드 포인터. 

그래서 여기에 목록입니다. 우리는이 목록에 (12)를 삽입 할. 그림은 알 수 약간 다릅니다. 각 노드는 세 fields--을 포함 데이터 및 빨간색 다음 포인터, 과 파란색에 이전 포인터. 아무것도, 15 노드 앞에 온다 그래서 그 이전 포인터는 널 (null)입니다. 이리스트의 시작이다. 그 전에 아무것도 없습니다. 그리고 아무것도, 10 노드 다음에 온다 및 그래서 다음 포인터뿐만 아니라 널입니다. 

그럼이 목록에 (12)를 추가 할 수 있습니다. 우리는 노드 [들림] 공간이 필요합니다. 우리는의 (12) 내부를 넣어. 그리고 다시, 우리가 정말해야 주의 체인을 깰 수 없습니다. 우리는 다시 정렬 할 올바른 순서로 포인터. 그리고 때로는 그 그런게 있습니다 우리는 특히 볼 수 있습니다로 delete--으로 우리는 몇 가지를 않는 중복 포인터,하지만 괜찮아요. 

그래서 우리는 먼저 무엇을 원하는가? 내가 추천 할 것 일 당신은 아마해야 하지 (12)의 포인터를 채우도록 아르 노드 당신은 사람이 다른 만지기 전에. 그래서 12 다음에 가리려고? 15. 무슨 일이 (12) 앞에 오는? 아무것도. 이제 우리가 작성 한 12 추가 정보 그래서 이전, 다음, 가치가있다. 

이제 우리는 할 수 있습니다 15--이 여분을 우리가 비슷해 얘기했다 단계 다시 12 ~ 15 점을 가질 수 있습니다. 그리고 지금 우리의 머리를 이동할 수 있습니다 연결리스트는 12합니다. 그래서 꽤 비슷한 우리 단독으로 연결된리스트로 일을했다, 추가 단계를 제외하고 목록의 이전 머리를 연결 목록의 새로운 머리에 백업합니다. 

이제 마지막으로 삭제하자 연결리스트에서 노드. 그래서 우리가 있다고 가정 해 봅시다 다른 기능이 우리가 삭제하려는 노드를 찾는 것입니다 정확히 우리에게 포인터를 부여하고있다 우리가 삭제하려는 노드입니다. 우리는 심지어 말을 분명히 ..하지 않습니다 머리는 여전히 전 세계적으로 선언된다. 우리는 여기에 머리를 필요가 없습니다. 이 모든 기능을하고있는 우리가했습니다입니다 정확히 우리 노드에 대한 포인터를 발견 없애합니다. 의 그것을 없애 보자. 그것은 함께 많은 쉽게 목록을 이중 연결. 실제로의 First-- 단지 몇 가지. 우리는 단지 주변을 수정해야 노드의 포인터가 건너 뛸 수 있도록 노드 우리는 삭제할. 그리고 우리는 그 노드를 삭제할 수 있습니다. 그래서 다시, 우리는 여기를 통해 것입니다. 우리는 분명히 결정했다 우리는 노드 X를 삭제하려면 그리고 또, 내가 뭘 해요 way--에 의해 here-- 일 에 대한 일반적인 경우이다 중간에 노드입니다. 몇 가지 있습니다 추가주의 사항 당신 삭제를 할 때 고려해야 할 목록의 시작 또는 목록의 맨 끝. 특별한 몇 가지가있다 코너의 경우도 처리합니다. 

그래서이 모든 노드를 삭제하는 작업 list-- 하나의 중간에 그 앞으로 합법적 인 포인터를 가지고 뒤로 합법적 인 포인터, 합법적 이전 및 다음 포인터. 다시 당신이 작업하는 경우 끝으로, 당신 그것들을 처리 할 필요 약간 다르게, 우리는하지 않을거야 지금 이야기. 하지만 당신은 아마 수 필요한 것을 파악 이 비디오를 시청하는 것만으로 수행 할 수 있습니다. 

그래서 우리는 격리 한 X에서 X는 노드 우리는 목록에서 삭제할. 우리는 무엇을해야합니까? 첫째, 우리는 다시 정렬 할 필요가 외부 포인터. 우리는 다시 정렬 할 필요가 9의 다음 13 스킵 그리고 포인트는 10--있는 우리가 무슨 짓을했는지입니다. 그리고 우리는 또한 필요 (10)의 이전을 재 배열 대신 13을 가리키는 9를 가리 키도록. 

그래서 다시,이 있었다 시작하는 도면이다. 이것은 우리의 체인이었다. 우리는 (13)를 통해 이동해야합니다 그러나 우리는 또한 보존 할 필요가 리스트의 무결성. 우리는 어떤을 잃고 싶지 않아 어느 한 방향으로 정보를 제공합니다. 그래서 우리는 다시 정렬 할 필요가 포인터 신중하게 그래서 우리는 모든 체인을 중단하지 않습니다. 

그래서 우리는 9의 다음 포인터를 말할 수있다 같은 장소를 가리키는 그 열세의 다음 포인터는 지금 지적한다. 우리가 결국이기 때문에 (13)를 통해 이동 할 것. 그래서 어디든지 13 점 다음, 당신을 구 대신이 지적하고 싶어요. 그래서 그입니다. 그리고 어디든지 13 점 다시 에, 13 앞에 오는대로, 우리는 가리 (10)를 원하는 그 대신 13. 당신이 따르는 경우에 지금, 알 화살표, 우리는 (13)를 제거 할 수 있습니다 실제로 임의의 정보 손실없이. 우리는리스트의 무결성을 유지 한 전방 및 후방 모두를 이동. 그리고 우리는 단지 정렬 할 수 있습니다 조금 그것을 청소 함께 목록을 당겨. 그래서 우리는 재 배열 양쪽에 포인터. 그리고 우리는 X를 해제 (13)를 포함 노드, 우리는 체인을 중단하지 않았다. 그래서 우리는 좋은했다. 

여기에 링크 된 목록에 대한 최종 참고. 그래서 singly- 모두와 이중 연결 목록, 우리가 보았 듯이, 지원 정말 효율적으로 삽입 및 요소의 삭제. 당신은 꽤 많이 할 수 일정한 시간에. 우리는 무엇을 삭제해야 할 않았다 요소 전에 잠깐? 우리는 하나의 포인터를 이동했다. 우리는 다른 포인터를 이동했다. 우리는 X-- 세 가지 작업을했다 해제. 항상 세 가지 작업에 소요 노드를 무료로 그 node--을 삭제합니다. 

우리는 어떻게 삽입합니까? 글쎄, 우리는 항상있어 처음에 시침 우리가 효율적으로 삽입하는 경우. 그래서 우리는 rearrange-- 필요 그건 경우에 따라 singly- 또는 이중 연결 목록, 우리는 세 가지 작업을 수행해야 할 수 있습니다 또는 4 개의 조작의 최대. 그러나 다시, 항상 서너이다. 그것은 얼마나 많은 문제가되지 않습니다 요소는 우리의 목록에 항상 서너 operations--있어 그냥 삭제가 항상 같은 서너 작업. 그것은 일정한 시간이다. 그래서 정말 좋아요. 

배열과 함께, 우리는하고 있었다 삽입 정렬과 같은. 당신은 아마 삽입 리콜 종류는 일정 시간 알고리즘이 아니다. 사실은 꽤 비싸다. 그래서이 삽입 훨씬 더 있습니다. 하지만 난에서 언급 한 바와 같이 리스트를 단독 비디오 연동, 우리는 여기에 단점을 가지고 너무 오른쪽거야? 우리는 능력을 잃었습니다 랜덤 요소에 액세스 할 수 있습니다. 우리는 내가 요소 4 번을 원 말할 수 없다 연결리스트의 또는 요소 번호 (10) 같은 방식으로 우리가 할 수있는 배열을 그렇게 또는 우리는 단지 직접 인덱스 수 우리의 배열의 요소에. 

그래서를 찾으려고 노력 링크 list--의 요소 검색은 important-- 경우 지금 선형 시간이 걸릴 수 있습니다. 목록이 길어지면, 그것은 하나의 추가 조치를 취할 수 있습니다 리스트에있는 모든 단일 요소에 대한 순서는 우리가 원하는 것을 찾을 수 있습니다. 그래서 무역 오프를있다. 프로의 비트가있다 여기 죄수 요소입니다. 

그리고 이중 연결리스트는되지 있습니다 데이터 구조의 조합의 종류 마지막 우리가 얘기하자 그 모든 기본적인 건물을 복용 C 블록은 함께 넣어. 사실, 우리가 할 수 있기 때문에 심지어 이것보다 더 잘 할 데이터 구조를 만드는 것을 당신은을 통해 검색 할 수 있습니다 일정 시간이 너무. 그러나 다른 비디오에서 해당에 대한 자세한. 

나는 더그 로이드입니다. 이 CS50입니다.