원형 연결 리스트

개념

1) 단순 연결 리스트: 끝까지 방문 하면 더 이상 방문할 곳이 없어 종료된다.
--> head부터 재시작해야함.
2) 원형 연결 리스트: 마지막 노드의 링크가 첫 번째 노드를 가르킨 원의 형태
--> 연속 방문이 가능하다.
단순 연결 리스트와 같이 오버헤드가 발생하지 않는다!!

원리

--> 단순 연결 리스트와 많은 부분이 비슷하다.

노드 구조

--> 단순 연결 리스트와 동일하게 데이터와 링크가 존재
--> 차이점은, 마지막 노드의 링크가 첫 번째 노드를 가리킨다.

노드 삽입

  새 노드 생성 -> 링크 수정

노드 삭제

  링크 수정 -> 노드 삭제

간단 구현

1. 노드 생성

--> 단순 연결 리스트와 동일
--> But, 첫 번째 노드와 마지막 노드가 연결

class Node():
    def __init__(self):
        self.data = None
        self.link = None
node1 = Node()
node1.data = '다현'
node1.link = node1 # 노드가 하나이므로, 자기 자신을 가르킨다.

2. 노드 연결

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

데이터가 5개인 원형 연결 리스트 생성

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. 노드 삽입

  새 노드 생성 -> 데이터 입력 -> 링크 변경

newNode = Node()
newNode.data = '재남'
newNode.link = node3
node2.link = newNode

4. 노드 삭제

  링크 변경 -> 노드 삭제

node2.link = node3.link
del(node3)

일반 구현

1. 원형 연결 리스트의 일반 형태

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

2. 배열에 저장된 데이터 입력 과정

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()
## 메인 코드 부분 ##
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)

3. 노드 삽입

--> 첫 번째, 중간, 마지막 삽입으로 나눌 수 있다.

def insertNode(findData, insertData):
    global memory, head, current, pre
    if head.data == findData: # 첫 번째 위치세 삽입
        node = Node()
        node.data = insertData
        node.link = head
        last = head # head 노드를 last로 지정
        while last.link != head: # 마지막 노드까지 탐색
            last = last.link # 앞으로 한 칸씩 이동
        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
             pre.link = node
             return
      node = Node() # 마지막 노드 삽입
      node.data = insertData
      current.link = node
      node.link = head

4. 노드 삭제

--> 첫 번째 삭제와, 그 외의 삭제로 나눌 수 있다.

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.link = 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

5. 노드 검색

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()