[자료구조 기초] 원형 연결리스트, Queue, 이중원형 연결리스트

 

 

앞에 큐장에서 표류 현상으로 인해 원형 리스트를 쓰는 것을 해결책으로 하는 방법을 잠깐 소개했었다

앞 글이 궁금하신 분들은 아래 링크를 클릭

[자료구조] - [자료구조 기초] queue , 큐

[자료구조 기초] queue , 큐

 

이에 이어서 이번 포스팅에서는 원형 연결 리스트, 이중원형연결리스트에 대해 더 자세히 알아보도록 하자

---

원형연결리스트

리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키도록 연결함

리스트 포인터가 마지막 노드를 가리키도록 하면 Rear-> Next는 Front를 의미하므로 쉽게 탐색이 가능하다

원형 연결 리스트에 노드의 삽입

① 새로 생성한 노드 ('Z'를 데이터로 가진 노드)를 임시 포인터 temp가 가리킨다

② 새로 생성한 노드의 포인터가 Rear가 가리키는 노드의 다음을 가리킨다. 즉, 원래 리스트에서 맨 앞의 노드를 가리키는 것과 같음

③ Rear 가 가리키고 있는 노드('C'를 데이터로 가진 노드)의 포인터(링크)가 새로 생성한 노드를 가리킨다.

④ Rear는 새로 생성한 노드를 가리킨다.

 

---

원형 연결 리스트에 노드의 삭제

① 임시 포인터 temp가 Rear-> next노드를 가리킨다. (즉, Front를 가리킴)

② Rear-> next 가 삭제할 노드의 다음 노드 (temp->next)를 가리킨다

③ temp 가 가리키는 노드를 해제하고, 노드의 값을 호출한 프로그램에 반환한다. free(temp)

 

---

이중 연결 리스트

연결 리스트의 각 노드가 앞 노드를 가리킬 수 있도록 함

단순 연결 리스트의 각 노드에 두 개의 노드 포인터를 두어서 하나는 앞 노드를 가리키고 하나는 뒤 노드를 가리키도록 함

어느 방향으로 탐색이 가능하다는 장점이 있음

---

이중원형 연결 리스트

이중 연결 리스트와 원형연 결 리스트가 장점을 합한 것

왼쪽 끝 노드 LLink는 오른쪽 끝 노드 즉, Front를  오른쪽 끝 노드 RLink는 왼쪽 끝 노드 즉, Rear를 가리킴

---

Head를 가진 이중 원형 연결 리스트

https://images.app.goo.gl/5wBhgKy3VoUHgDZcA

 

이중 원형 연결 리스트는 연산이 복잡하기 때문에 연산 알고리즘을 간단하게 하기 위해 헤드 노드를 가짐

헤드 노드는 데이터 값을 갖지는 않음

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

① temp는 삽입할 노드를, ptr은 삽입 할 노드의 앞 노드를 가리킴

② temp ->Llink = ptr; 삽입할 노드의 Llink 가 ptr 노드를 가리킴

③ temp ->Rlink = ptr -> Rlink ; 삽입할 노드의 Rlink는 ptr 다음 노드를 가리킴

④ ptr -> Rlink -> Llink = temp; ptr 다음 노드의 Llink는 삽입할 노드를 가리킴 (ptr -> Rlink = 'C' 노드)

⑤ ptr -> Rlink  = temp; ptr의 Rlink는 삽입할 노드를 가리킴

---

이중원형 연결 리스트의 삭제

① temp는 삽입할 노드를, ptr은 삭제할 노드의 앞 노드를 가리킴

② 삭제할 노드의 앞 노드가 삭제할 노드의 뒤 노드를 가리킴

temp-> Llink ->Rlink = temp->Rlink; (temp-> Llink = 'A' 노드)   (temp->Rlink = 'C' 노드)

③ 삭제할 노드의 뒤 노드가 삭제할 노드의 앞 노드를 가리킴

temp-> Rlink ->Llink = temp->Llink;