[자료구조] 원형 연결 리스트(Circular Linked List)

📌 현재 게시글의 개념과 코드는 이 책을 참고하여 정리하였습니다.

원형 연결 리스트(Circular Linked List)

원형 연결 리스트의 큰 특징은 처음과 끝이 연결되어 있다는 점입니다.

구조는 단순 연결 리스트와 유사합니다. 노드 구조를 갖고 있기 때문인데요.

하지만 처음과 끝이 연결되어 있다면? 원형 연결 리스트에는 헤드가 없고 마지막 노드의 링크는 비어있게 됩니다.

마지막 노드의 링크(포인터)를 처음으로 연결만 시켜주면 됩니다.

이런 구조가 필요한 곳은 어딜까요? cycle이 있는 구조겠죠?

바로 원형 연결 리스트를 구현해보는 것으로 가보겠습니다.

원형 연결 리스트(Circular Linked List) 구현

1. 노드 생성

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):                      # 시작 노드 전달 받음
    current = start                         # 현재 노드로 지정
    if current.link == None:                # 노드에 데이터가 하나도 없는 연결 리스트인 경우
        return                              # 반환한다
    print(current.data, end=' ')            # 현재 노드 출력
    while current.link != start:            # 현재 노드의 링크가 전달 받은 노드(=첫 번째 노드)가 아닐 때까지 반복
        current = current.link              # 현재 노드의 링크가 첫 번째 노드라면 원형 연결 리스트에서는 마지막 노드를 의미함
        print(current.data, end=' ')
    print()

## 전역 변수 선언 부분 ##
memory = []
head, current, pre = None, None, None
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]
    head = node
    memory.append(node)

    for data in dataArray[1:]:
        pre = node
        node = Node()
        node.data = data
        pre.link = node
        node.link = head
        memory.append(node)

    printNodes(head)

앞에서 head가 없다고 얘기했지만 head가 들어가 있습니다.

왜냐하면 원형 리스트 구조를 구현하기 위해서인데요.

여기서 주의점은 마지막 노드의 링크가 헤드를 가리킨다는 점입니다.

node.link = head

그러면 원형 구조가 만들어집니다!

Out:

다현 정연 쯔위 사나 지효 

2. 데이터 삽입

이번 게시글부터는 중복되는 코드는 지우고 주요한 코드만 남겨두겠습니다.

def insertNode(findData, insertData):       # 첫 번째 노드 삽입
    global memory, head, current, pre      

    if head.data == findData:
        node = Node()
        node.data = insertData
        node.link = head
        last = head                         # 마지막 노드를 첫 번째 노드로 우선 지정
        while last.link != head:            # 마지막 노드의 링크가 head가 아닐 때 -> 마지막 노드를 찾으면 반복 종료
            last = last.link                # last를 다음 노드로 변경
        last.link = node                    # 마지막 노드의 링크에서 새 노드 지정
        head = node
        return

    current = head
    while current.link != head:             # 중간 노드 삽입
        pre = current
        current = current.link
        if current.link == findData:
            node = Node()
            node.data = insertData
            node.link = current
            pre.link = node
            return
        
    node = Node()                           # 마지막 노드 삽입 -> 찾을 데이터가 없는 경우(while문이 종료되고)
    node.data = insertData
    current.link = node                     # 새 노드 생성 후 현재(current) 노드 링크를 새 노드로 지정
    node.link = head                        # 새 노드의 링크를 head로 지정(새 노드가 마지막 노드가 됨!)

## 코드가 잘 실행되는지 확인 ##

    insertNode('다현', '화사')
    printNodes(head)

    insertNode('사나', '솔라')
    printNodes(head)

    insertNode('수연', '문별')
    printNodes(head)

아까 위에서 마지막 노드가 head로 지정이 되었기 때문에, head가 아닐 때까지 반복되도록 해줍니다.

head = 마지막 노드를 찾으면 종료되는 것이죠.

그렇게 데이터를 삽입해줍니다.

Out:

다현 정연 쯔위 사나 지효 
화사 다현 정연 쯔위 사나 지효 
화사 다현 정연 쯔위 사나 지효 솔라
화사 다현 정연 쯔위 사나 지효 솔라 문별

3. 데이터 삭제

def deleteNode(deleteData):
    global memory, head, current, pre

    if head.data == deleteData:             # 삭제할 노드가 첫 번째 노드일 때
        current = head                      # 현재 노드를 헤드 노드와 동일하게 만들기
        head = head.link                    # head 노드를 다음 노드로 변경
        last = head                        
        while last.link != current:         # 마지막 노드를 찾으면 반복 종료 
            last = last.link                # last를 다음 노드로 변경
        last.link = head                    # 마지막 노드의 링크에 head가 가리키는 노드 지정
        del(current)
        return

    current = head                          # 첫 번째 외 노드 삭제
    while current.link != head:
        pre = current
        current = current.link
        if current.data == deleteData:      # 중간 노드를 찾았을 때
            pre.link = current.link
            del(current)
            return

## 코드 실행해서 확인하기 ##
    deleteNode('다현')
    printNodes(head)

    deleteNode('쯔위')
    printNodes(head)

    deleteNode('지효')
    printNodes(head)

    deleteNode('재남')
    printNodes(head)

삭제할 노드가 첫 번째 노드인지를 먼저 확인하고, 그게 아니라면 다음 노드로 넘어가면서 삭제할 데이터의 위치를 탐색합니다.

삭제할 데이터를 찾게 되면 데이터가 삭제됩니다.

만약 없는 데이터의 삭제를 요청하면 그대로 return 하게 합니다.

Out:

다현 정연 쯔위 사나 지효 
정연 쯔위 사나 지효 
정연 사나 지효
정연 사나
정연 사나

4. 데이터 검색

def findNode(findData):                     # 노드를 검색하는 함수
    global memory, head, current, pre       # 전역 변수 가져오기

    current = head                          # 현재 노드를 head로 지정
    if current.data == findData:            # 현재 노드의 데이터가 찾는 데이터라면
        return current                      # current 반환
    while current.link != head:             # 노드가 끝날 때까지 반복
        current = current.link              # 현재 노드에서 다음 노드로 이동
        if current.data == findData:        # 현재 노드의 데이터가 찾는 데이터라면
            return current                  # current 반환
    return Node()                           # 빈 노드 반환

## 코드 실행 확인 ##

    fNode = findNode('다현')
    print(fNode.data)

    fNode = findNode('쯔위')
    print(fNode.data)

    fNode = findNode('수연')
    print(fNode.data)

노드를 검색하는 함수입니다.

현재 노드를 head로 임의 지정한 다음에 찾는 데이터가 맞는지 확인합니다.

아니라면 다음 노드로 이동하고 찾는 데이터가 맞으면 현재 상태를 출력합니다.

만약 찾는 데이터가 없다면 None 값을 return합니다.

Out:

다현 정연 쯔위 사나 지효 
다현
쯔위
None

여기까지 선형 리스트, 단순 연결 리스트, 원형 연결 리스트까지 살펴보았습니다!