>> [음악 재생]
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입니다.