Double Linked List

 

[1] 더블 링크드리스트

: 개념

 

파일 이름	people.c

 

struct people, 즉 people의 맴버를 보면 

즉 무언가를 가리키는 포인터변수가 2개 선언.

 

 

 

[2] 더블 링크드리스트

: 더미 노드 (dummy node)

 

파일 이름	people.c

 

 

 

 

 

끝은 항상 막아 놓는다 했어요. 딴 값으로 새버리면 안 되니까요. 

우리는 이 두 특별한 노드를 더미노드라고 할게요.

왜 더미노드를 써야 되는지는 추가, 삭제 부분 보면 자연스럽게 터득하게 될 거예요.

  

[3] 더블 링크드리스트

: 추가

 

ⓐ : 탐색부분        ⓑ : 추가코드
파일 이름	people.c

 

원소가 하나도 없을 때 추가를 할 때랑

원소가 한 개 이상 있을 때 추가를 할 때 상황이 조금 달라요.

 

 

 

자. 그 상황을 볼까요? 이 프로그램은 이름을 사전순대로

정렬을 해서 출력을 하는 프로그램이예요. 즉, 사전순대로 엮어서 저장이 된다.

 

아무것도 없을 때에는 자, 두 더미노드 사이에

추가가 되야 겠네요. 즉, head가 가리키는 놈이 가리키는 원소와

tail이 가리키는 놈이 가리키는 원소 사이에 말이지요.

 

만약에 원소가 1개 이상 있다면?

탐방해 봅시다. 우리는 눈으로 금방 볼 테니 컴이 판단하는 과정만 보자고요.

 

일단 chokahee와 kartrider를 사전 순으로 비교합니다.

kartrider가 더 뒤에 있죠?

 

 

이제 maplestory와 kartrider를 비교해 볼까요?

kartrider가 더 앞에 있네요. kartrider는 temp고 maplestory는 p->name이네요.

조건을 만족시키니까 for문을 빠져나와 버리죠?

 

결국 p는 maplestory가 있는 놈을,

t는 그 이전 원소인 chokahee를 가리키네요.

이제 추가를 한 번 해 봅시다.

Step by step!!

 

일단 t가 가리키는 next맴버 값을 바꿔야 겠다!

뭘로? 970으로!! 즉 할당받은 놈의 주소를!!

 

 

그리고 할당받은 놈이 가리키는 녀석의 next 맴버는 무슨 값이 되야 될까요?

710이 되야 maplestory가 들어있는 원소를 가리키겠다! 그죠?

즉 ptr->next=p;

 

 

자. 그 다음에 p의 prev 맴버는 970이 되서

kartrider가 들어있는 원소를 가리켜야 겠다. 우와!!

마지막의 ?에 들어갈 값은 뭐가 될 지 여러분들이 생각해 보시길.

아하!! p->prev=ptr;

 

어렵다고요? 여러분. 선릉에서 수서까지 분당선이 개통되었을 때

구룡역이 나중에 개통되었죠? 그거랑 같다고 생각하시면 되요^^

Q. 더미노드를 선언하지 말고 추가함수를 구현해 봅시다.

 

 

[3] 더블 링크드리스트

: 삭제

 

파일 이름	people.c

 

삭제부분은 추가보다 더 쉽습니다.

p는 삭제할 놈을, t는 그 이전의 놈을 가리키고 있습니다.

여기까지는 추가함수가 p,t 찾을 때 까지 하는 짓과 동일합니다.

코드는 여러분이 잘 분석해 보세요^^

 

내가 다 분석해 드리지 않습니다.

어? 근데 왜 경우수가 1가지지? 라고 생각하시는 분들을 위해서!

 

여러분. 첫 원소를 삭제한다고 해도

우리는 정말 처음 원소와 정말 끝 원소, 즉 더미노드들은 삭제를 못 하지요?

즉, 중간 원소를 삭제하는 경우

1가지로 압축이 되는 거예요. 아하~

 

그러면 삭제할 때 뭐만 확인하면 된다? 만약에 더미가 없다면?

어잌후^^ 경우의 수가 또 3가지가 되겠지 뭘 그래^^

 

삭제할 위치가 더미 원소인가?

더미원소이면 삭제하면 안되잖아요^^

이 경우엔 안 되지요?

 

자. 방금 추가한 kartrider를 삭제해 보기로 합시다.

p->next는 710이지요? 즉 710이라는 놈이

maplestory가 들어있는 원소를 가리키고 있죠?

 

오호! 즉 p->next의 값을 t->next에 집어 넣어주면 되겠다!

이렇게 말이죠. 그렇죠? 그 다음엔?

 

빨간 화살표 주목!!

p의  next 맴버는 710이다! 그죠?

그놈이 가리키는 원소의 prev 맴버니까

(p->next)->prev 이렇게 쓸 수 있겠다! 이 놈이 650이 되야 겠다!

그렇죠? 어렵지 않죠? 650은 t가 가지고 있는 값이기도 하죠.

그거이면서 chokahee가 들어있는 원소의 주소값이기도 하겠다..

 

따라서 p->next->prev=t;

 

이제 kartrider가 들어있는 구조체 포인터 맴버들이

아무것도 안 가리키게 한 다음에

없애버리면 되겠다. 어떻게?

free(p);로!!

Q. 더미노드를 선언하지 말고 삭제하는 함수를 구현해 봅시다.

 

 

[3] 더블 링크드리스트

: 탐색

 

파일 이름	people.c

 

사실 탐색이라고 해봤자 별 거 아니예요.

전체를 출력하던지, 아니면 조건에 맞춰서 출력하던지!!

 

어디서부터 어디까지 탐색한다?

정말 처음 원소인 더미 노드의 다음 원소부터!!

중요하죠?

 

끝 더미원소가 나올 때 까지!! 자. 이건 어떻게 판단할까요?

잠깐 끝 더미 주변 원소들을 확대해 볼까요?

 

아하하; 그렇죠! yangjae가 들어있는 원소 탐방 후에는

p가 다음 그림과 같이 *tail이 가리키는 놈을 똑같이 가리키겠죠?

 

 

출처 : http://cky5122.blog.me/80149935892