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

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

원형 연결 리스트의 개념

• 단순 연결 리스트(Singly Linked List)
  • 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다.
• 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다.
  • 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태
• 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다.

 

원형 연결 리스트의 원리

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

 

노드 구조

• 단순 연결 리스트와 마찬가지로 원형 연결 리스트를 구현하기 위해서는 노드(Node)를 사용해야 한다.

노드의 구조

 

• 원형 연결 리스트도 단순 연결 리스트와 마찬가지로 첫 번째 노드를 가리키는 헤드(head)를 사용한다.
  • 헤드는 원형 연결 리스트의 시작점으로 사용한다.

노드로 구성된 원형 연결 리스트

 

노드(데이터) 삽입

• 1단계 : 삽입할 노드를 생성한다.
• 2단계 : 순서에 맞게 링크를 수정한다.
  • 새 노드의 링크에 이전 노드의 링크를 복사한다.
  • 이전 노드의 링크에 새 노드를 지정한다.

원형 연결 리스트에서 중간 위치에 노드를 삽입하는 과정

 

• 원형 연결 리스트에서 중간 노드를 삽입하는 과정은 단순 연결 리스트의 과정과 방식이 동일하다. 
  • 하지만, 첫 번째 노드 삽입이나 마지막 노드 삽입 등은 다르게 처리된다.

 

노드(데이터) 삭제

• 1단계 : 삭제할 노드의 바로 앞 노드 링크를 수정한다.
  • 삭제할 노드의 링크를 바로 앞 노드의 링크로 복사하여 앞 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
• 2단계 : 삭제할 노드를 삭제한다.

원형 연결 리스트에서 중간 위치의 데이터를 삭제하는 과정

 

• 원형 연결 리스트에서 중간 노드를 삭제하는 과정은 단순 연결 리스트의 과정과 방식이 동일하다. 
  • 하지만, 첫 번째 노드 삭제나 마지막 노드 삭제 등은 다르게 처리된다.

 

원형 연결 리스트의 구현

• 헤드(head) : 첫 번째 노드를 가리킨다.
• 현재(current) : 지금 처리 중인 노드를 가리킨다.
• 이전(pre) : 현재 처리 중인 노드의 바로 앞 노드를 가리킨다.

 

• 처음에는 모두 비어 있으므면 되므로 다음과 같이 초기화한다.

memory = []
head, current, pre = None, None, None

 

① 원형 연결 리스트 생성

노드 생성

• 노드는 클래스(Class)를 사용하여 구현한다.

class Node() :
    def __init__(self):       # 생성자 함수 : 데이터형을 생성할 때 자동으로 실행
        self.data = None
        self.Link = None

• 노드 생성 및 확인

node1 = Node()
node1.data = "Apple"
print(node1.data, end = ' ')
node1.link = node1     # 첫 번째 노드와 마지막 노드가 연결되도록 설정한다.

 

노드 연결

• 첫 번째 노드의 링크에 두 번째 노드 이름(node2)을 넣어 준다.
• 그리고 두 번째 노드의 링크에 첫 번째 노드를 연결해서 원형 구조를 갖게 해준다.

node2 = Node()
node2.data = "Banana"
node1.link = node2      
node2.link = node1

 

노드 초기화

첫 번째 데이터

• 첫 번째 노드이므로 헤드는 첫 번째 노드를 가리키도록 하고, 새 노드의 링크는 헤드가 가리키는 노드로 연결한다.
• 첫 번째 노드이므로 결국 자신이 자신을 가리키는 형태가 된다.

 

node = Node()
node.data = dataArray[0]    # 첫 번째 노드
head = node
node.link = head
memory.append(node)

 

두 번째 이후 데이터

• 새 노드를 기준 노드의 링크에 저장하기 전에 기존 노드를 잠시 저장한 후 생성해야 한다.
• 그리고 새 노드의 링크에 헤드가 가리키는 노드를 연결함으로써 원형 연결 리스트의 구조를 유지해야 한다.

 

pre = node
node = Node()
node.data = data    # 두 번째 이후 노드
pre.link = node
node.link = head
memory.append(node)

 

② 노드 삽입

• 노드를 원형 연결 리스트의 맨 앞, 중간, 마지막에 삽입하는 경우로 나누어 생각해 볼 수 있다.

 

첫 번째 노드 삽입

 

node = Node()
node.data = "item"
node.link = head           
last = head                # 마지막 노드를 첫 번째 노드로 우선 지정
while 마지막 노드까지 :       # 마지막 노드를 찾으면 반복 종료
    last = last.link       # last를 다음 노드로 변경
last.link = node           # 마지막 노드의 링크에 새 노드 지정
head = node

 

중간 노드 삽입

 

current = head
while 마지막 노드까지 :
    pre = current
    current = current.link
    if current.data == origin_data :
        node = Node()
        node.data = new_data
        node.link = current
    pre.link = node

 

마지막 노드 삽입

 

# 마지막 노드까지 new_data 를 찾지 못한 후
node = Node()
node.data = new_data
current.link = node
node.link = head

 

함수 완성

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:        # 마지막 노드를 찾으면 반복 종료
            last = last.link            # last를 다음 노드로 지정
        last.link = node                # 마지막 노드의 링크에 새 노드 지정
        head = node
        return

    current = head
    while current.link != head:     # 중간 노드 삽입
        pre = current
        current = current.link
        if current.data == findData:
            node = Node()
            node.data = insertData
            node.link = current
            return
    
    node = Node()       # 마지막 노드 삽입
    node.data = insertData
    current.link = node
    node.link = head

 

③ 노드 삭제

첫 번째 노드 삭제

 

current = head
head = head.link
last = head
while last.link != current :     # 마지막 노드를 찾으면 반복 종료
    last = last.link             # last를 다음 노드로 변경
last.link = head                 # 마지막 노드의 링크에 head가 기리키는 노드 지정
del(current)

 

첫 번째 외 노드 삭제

 

current = head
while current.link != head :
    pre = current
    current = current.link
    if current.data == finding_data :
        pre.link = current.link
    del(current)

 

함수 완성

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

    if head.data == deleteData :    # 첫 번째 노드 삭제
        current = head
        head = head.link
        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

 

④ 노드 검색

• 검색할 데이터의 노드를 반환하는 방식으로 구현해본다.

 

함수 완성

def findNode(findData) :
    global memory, head, current, pre

    current = head
    if current.data == findData :
        return current
    while current.link != head :
        current = current.link
        if current.data == findData :
            return current
    return Node()    # 빈 노드 반환

 

원형 연결 리스트의 완성

# 원형 연결 리스트의 구현

## 클래스와 함수 선언 부분 ##
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()

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:        # 마지막 노드를 찾으면 반복 종료
            last = last.link            # last를 다음 노드로 지정
        last.link = node                # 마지막 노드의 링크에 새 노드 지정
        head = node
        return

    current = head
    while current.link != head:     # 중간 노드 삽입
        pre = current
        current = current.link
        if current.data == findData:
            node = Node()
            node.data = insertData
            node.link = current
            return
    
    node = Node()       # 마지막 노드 삽입
    node.data = insertData
    current.link = node
    node.link = head

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

    if head.data == deleteData :    # 첫 번째 노드 삭제
        current = head
        head = head.link
        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

def findNode(findData) :
    global memory, head, current, pre

    current = head
    if current.data == findData :
        return current
    while current.link != head :
        current = current.link
        if current.data == findData :
            return current
    return Node()    # 빈 노드 반환

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

## 메인 코드 부분 ##
if __name__ == "__main__":
    node = Node()
    node.data = dataArray[0]    # 첫 번째 노드
    head = node
    node.link = head
    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)

    # 삽입 예
    insertNode("다현", "화사")
    printNodes(head)

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

    insertNode("지민", "문별")
    printNodes(head)

    # 삭제 예
    deleteNode("다현")
    printNodes(head)

    deleteNode("쯔위")
    printNodes(head)

    deleteNode("지효")
    printNodes(head)

    deleteNode("지민")
    printNodes(head)

    # 검색 예
    fNode = findNode("다현")
    print(fNode.data)

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

    fNode = findNode("지민")
    print(fNode.data)

 

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