원형 연결 리스트의 기본과 간단 구현

 1  원형 연결 리스트의 개념

원형 연결 리스트는 단순 연결 리스트와 구조나 코드가 상당히 유사하다.

원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키게 설정한다.

그러면 리스트의 형태가 원(Circle) 형태로 구성되어 계속 회전하면서 연속 방문이 가능하다.

원형 리스트의 장점은 단순 연결 리스트와 마찬가지로 오버헤드가 발생하지 않는다.

 

 2  원형 연결 리스트의 원리

원형 연결 리스트의 원리도 단순 연결 리스트와 많은 부분 비슷하다.

원형 연결 리스트를 단순 연결 리스트와 같이 구현하려면 '노드'를 사용해야 한다. 

단순 연결 리스트 노드와의 차이점은 노드의 마지막 링크가 첫 번째 노드와 연결되어있다는 것이다.

 

원형 연결 리스트의 노드 구조는 단순 연결 리스트에서 사용했던 것과 동일하다.

## 원형 리스트 생성 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"
node1.link = node1 # 자기 자신과 연결

node2 = Node()
node2.data = "정연"
node1.link = node2
node2.link = node1

node3 = Node()
node3.data = "쯔위"
node2.link = node3
node3.link = node1

node4 = Node()
node4.data = "사나"
node3.link = node4
node4.link = node1

node5 = Node()
node5.data = "지효"
node4.link = node5
node5.link = node1

current = node1
print(current.data, end = ' ')
while current.link !=node1 :
    current = current.link
    print(current.data, end = ' ')

 

 3  노드 삽입

단순 연결 리스트에서와 똑같이 삽입할 노드를 생성하고, 순서에 맞게 링크를 수정한다.

하지만 단순 연결 리스트는 모든 노드가 연결되어있기 때문에 첫번째와 마지막 노드 삽입 등은 다르게 처리된다.

삽입할 때 마지막과 첫 번째를 이어주어야 한다는 것이 차이점이다.

## 원형 연결 리스트의 중간 노드 삽입 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"
node1.link = node1

node2 = Node()
node2.data = "정연"
node1.link = node2
node2.link = node1

node3 = Node()
node3.data = "쯔위"
node2.link = node3
node3.link = node1

node4 = Node()
node4.data = "사나"
node3.link = node4
node4.link = node1

node5 = Node()
node5.data = "지효"
node4.link = node5
node5.link = node1

newNode = Node()
newNode.data = "재남"
newNode.link = node2.link
node2.link = newNode

current = node1
print(current.data, end = ' ')
while current.link !=node1 :
    current = current.link
    print(current.data, end = ' ')

 

 4  노드 삭제

단순 연결 리스트에서와 똑같이 삭제할 바로 앞 노드의 링크를 수정하고,

삭제할 노드의 링크를 바로 앞 노드의 링크로 복사한다. 그리고 남겨진 삭제할 노드를 삭제한다.

하지만 단순 연결 리스트는 모든 노드가 연결되어있기 때문에 첫 번째와 마지막 노드 삭제 등은 다르게 처리된다.

## 원형 연결 리스트의 중간 노드 삭제 ##
class Node() :
    def __init__ (self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "다현"
node1.link = node1

node2 = Node()
node2.data = "정연"
node1.link = node2
node2.link = node1

node3 = Node()
node3.data = "쯔위"
node2.link = node3
node3.link = node1

node4 = Node()
node4.data = "사나"
node3.link = node4
node4.link = node1

node5 = Node()
node5.data = "지효"
node4.link = node5
node5.link = node1

node2.link = node3.link
del(node3)

current = node1
print(current.data, end = ' ')
while current.link !=node1 :
    current = current.link
    print(current.data, end = ' ')