[C언어] 이중원형연결리스트

이중연결리스트

- 이중연결리스트는 각 노드가 앞 노드를 가리킬 수 있도록 한다.

- 단순 연결리스트의 각 노드에 두 개의 노드 포인터를 두어서 하나를 앞쪽 노드, 하나는 뒤쪽 노드를 가리키도록 한다.

- 어느 방향으로나 탐색이 가능한 형태다.

 

 

이중원형연결리스트

- 이중 연결리스트와 원형 연결리스트의 개념을 합한 것이다.

- 왼쪽 끝 노드의 L.Link는 오른쪽 끝 노드를, 오른쪽 끝 노드의 R.Link는 왼쪽 끝 노드를 가리킨다.

 

 

헤드노드를 가진 이중원형연결리스트

 

- 이중 원형 연결리스트는 연산이 매우 복잡하기 때문에, 연산 알고리즘을 간단하게 하기 위해서 헤드 노드를 가진다.

- 헤드 노드는 다른 노드와 형태가 같지만, 데이터 값을 가지지는 않는다.

 

 

 

 

이중원형연결리스트의 삽입

1. temp는 삽입할 노드를 가리키고, ptr은 삽입할 위치의 앞 노드를 가리킨다.

2. temp->Llink = ptr; 

3. temp->Rlink = ptr->Llink;

4. ptr->Rlink->Llink = temp;

5. ptr->Rlink = temp;

 

진짜 어렵다. 복잡하고 직관적이지 않다. 익숙해지는 수 밖에. 실력이 늘었는지 확인하려면 나중에 여기로 돌아와서 어떻게 이해되는 지를 확인해볼 것.

 

 

이중원형리스트의 삭제

1. temp가 삭제할 노드를 가리킴

2. temp->Llink->Rlink = temp->Rlink;

 

=> A노드->Rlink = C노드

 

3. temp->Rlink->Llink = temp->Llink;

 

=> C노드->Llink = A노드

 

4. B노드 메모리 반환