자료구조(3) 원형 연결리스트 + tail로 머리추가, 꼬리추가 (더미 x)

바로 전에 배운 더미, 머리 연결 리스트의 마지막 노드는 Null을 가르켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 "원형 연결 리스트"가 된다.

 

원본 : (head) 2-3-4-5 (tail)

머리추가 : head->1-2-3-4-5  // 1->2->3->4->5

꼬리추가 : head->2-3-4-5-1 tail // 1->2->3->4->5 // 꼬리부터 1,2,3,4,5로 볼수있다

"두 연결 리스트 모두 5가 저장된 노드는 1이 저장된 새 노드를 가리키고, 1이 저장된 새 노드는 2가 저장된 노드를 가르킨다"

위의 원형 연결 리스트의 특성 때문에 머리와 꼬리의 구분이 없다고 이야기한다. 실제로 두 연결 리스트의(머리,꼬리) 유일한 차이점은 포인터 변수 head가 무엇을 가리키느냐에 있다. 그것을 제외하면 차이가 없다.

 

노드를 꼬리에 추가하는 방법에 대해서 생각해보면 꼬리를 가르키는 포인터 변수 tail이 필요하다는 생각이든다. 그런데 이렇게 되면 원형 연결 리스트의 장점이 반감되어 버린다. 왜냐하면 원형리스트의 장점중 하나는 다음과 같기 때문이다 "단순 연결 리스트처럼 머리와 꼬리를 가르키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다" 그래서 나온게 변형 원형 리스트!

 

원형 연결리스트는 사실 자료구조 서적에서 비중있게 다루는 주제는 아니다. 게다가 단순히 노드의 추가가 아닌, 노드의 추가 위치에 의미를 부여해서 "머리에 추가", "꼬리에 추가"를 동시에 거론하는 경우는 더 드물다.

하지만 이런걸 잘 알고, 이해하면 원형연결리스트의 장점을 잘 이해할 수 있다.

 

head 1-2-3-4-5

head가 가르키는 것은 머리이니, 꼬리에 노드를 추가하기 위해서는 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 하는 상황이다. 하지만 위의 그림을 조금만 변경하면 180도 달라진다.

"하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 합시다!"

 

1-2-3-4-5 tail  // 5는 1이랑 연결되어있다고 가정(그냥 일반적인 원형리스트임)

포인터 변수인 tail이 리스트의 끝을 가리키는 상황이니, 새로운 노드를 리스트의 끝에 추가하는 것은 그리 어렵지 않다. 어디 그뿐인가? tail->next가 가리키는 것이 첫번째 노드이니, 이것을 이용하면 리스트의 머리에도 노드를 쉽게 추가할 수 있다.

 

• 꼬리를 가리키는 포인터 변수는? tail 입니다!
• 머리를 가리키는 포인터 변수는 tail->next 입니다!

즉 tail 변수 하나로 꼬리와 머리를 가리킬수 있다는 뜻이다.

 

이 변형된 원형연결리스트에서 나름 의미를 부여하고 싶은 함수를 묻는다면, 개인적으로 다음 세 함수이다.

• LFirst
• LNext // 무한 반복 호출이 가능하며, 리스트의 끝에 도달할 경우 첫 번째 노드부터 다시 조회가 시작됨
• LRemove

왜냐하면 이들은 변형된 원형연결리스트의 활용가치를 높인 함수들이기 때문이다.

 

원형 연결 리스트의 ADT 설명

• 정렬관련 기능 제외 // 불필요한 부분 최소화
• 데이터를 저장하는 함수 2개 정의 // 머리에, 꼬리체 추가하는 방법, 또다른 특성을 언급하기위한 목적

(머리에 데이터를 추가하고 꼬리를 한칸 앞으로 이동시키면 머리에 추가한 것과 동일해지는 특성)

 

변형된 원형연결리스트에서 첫번째 노드가 리스트에 추가되면, tail은 새 노드를 가리켜야하고, 새 노드도 자기자신을 가리켜야 한다. 왜냐하면 처음 추가된 노드는 그자체로 머리이자 꼬리이기 때문이다. Linsert 함수의 호출 결과도 동시에 머리에 추가하는 LInsertFonrt 함수의 호출 결과도 동일하다.

 

원본 : 1 - 2 tail // 3을 추가할 예정

머리추가 : (3) - 1 - 2 <-tail  

꼬리추가 : 1 - 2 - (3) <-tail       // 동일 동일 동일

머리추가후 tail 이동!

1)머리추가 :         (3) - 1 - 2 <-tail 

2)tail이동   : tail-> (3) - 1 - 2 -    // 동일 동일 동일

머리추가 -> tail 한칸 이동은 꼬리에 추가한 결과랑 완전히 동일하다.

즉 데이터를 머리에 추가하고 싶으면 그냥 머리에 추가하고 꼬리에 추가하고싶으면 데이터를 머리에 추가하고 tail을 한칸 앞으로 이동!

 

노드를 꼬리에 추가했을때, 머리에 추가했을 때의 유일한 차이점은 tail이 가리키는 노드가 다르다는것뿐!

 

새 노드를 머리에 추가한 상태에서 연결 방향을 따라 tail만 한 번 이동시키면, 그 결과가 새 노드를 꼬리에 추가한 결과와 똑같다!!!!!!!

 

변형된 원형연결리스트 구조체 멤버 cur와 before의 역할은 단순 연결 리스트의 경우와 동일하다. 즉, before는 cur보다 하나 앞선 노드를 가리켜야한다. Lfirst 함수가 호출되면 before는 tail, cur는 tail->next를 가리킨다.

 

cur -> 1 - 2 - 3 - 4 - 5 <-tail, before

 

LNest 함수에는 리스트의 끝을 검사하는 코드가 존재하지 않는다. 때문에 무한으로 반복해서 호출이 가능하며, 대상이 되는 원형연결리스트는 머리와 꼬리가 연결된 관계로 리스트의 마직까지 조회가 이뤄졌다면, 다시 첫 번째 노드에서부터 조회가 시작된다.

 

삭제

삭제는 대부분의 경우 상대적으로 복잡한 편이다. 하지만 머리와 꼬리가 연결되어 있다는 점만 제외하면, 원형연결리스트와 단순연결리스트는 그 구조가 동일하기 때문에 삭제방법도 유사하다(핵심연산 동일) 물론 완전히 똑같지는 않은데 그 이유는 다음과 같다. "변형된 원형연결리스트에는 더미 노드가 존재하지 않는다!"

• 핵심연산 1. 삭제할 노드의 이전 노드가, 삭제할 노드의 다음 노드를 가리키게 한다.(U자 형성)
• 핵심연산 2. 포인터 변수 cur를 한 칸 뒤로 이동시킨다(before는 위치조정필요없는거 알지?)

어쩌면 꼬리와 머리가 연결되어 있는 것을 완전하지 않은 이유로 생각했을지 모르겠다. 하지만 이는 삭제의 과정에 영향을 미치지않는다.

 

변형된 원형연결리스트에는 더미 노드가 존재하지 않기때문에, 삭제에 있어서 다음 두 가지 예외적인 상황을 구분해야 한다.

• 예외적인 상황 1. 삭제할 노드를 tail이 가르키는 경우 // tail은 전으로 이동됨
• 예외적인 상황 2. 삭제할 노드가 리스트에 홀로 남은 경우 // tail은 Null을 가르킴

 

질문: 그럼 변형된 원형연결리스트에도 더미를 붙혀주면, 삭제함수가 조금은 간단해지지 않을까요?

답 : 물론이다. 더미노드를 붙여주면 삭제함수 뿐만 아니라, 노드의 추가와 관련된 두 함수의 구현이 간단해진다. 다만 데이터를 순환 참조하는 Lnext 함수의 구현에 있어서 더미 노드를 처리를 위한 코드를 추가로 삽입해야 한다는 단점도 더불어 생긴다.