원형 연결 리스트의 일반 구현

 1  원 연결 리스트의 생성

앞서 데이터를 5개로 제한된 리스트로 구현했지만 데이터 개수가 제한적이지 않을 때가 일반적이다.

생성되는 모든 노드를 메모리에 넣는다. 메모리 크기는 무한대고 위치나 순서는 상관없이 링크로 연결된다.

헤드(head)는 첫 번째 노드, 현재(current)는 지금 처리 중인 노드, 이전(pre)은 현재 처리 중인 노드의 바로 앞 노드이다.

사용자가  키보드로 입력하거나 데이터 저장소에서 데이터를 가져와서 대입한다.

첫 번째 노드는 자신을 가리키는 형태가 된다. 그리고 완성된 노드를 메모리에 넣는다.

## 원형 연결 리스트 생성 ##
## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):
    current = start
    if current == 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)

 

 2  노드 삽입

원형 원결 리스트에 노드를 삽입하는 방식은 첫 번째, 중간, 마지막에 삽입하는 경우로 나눌 수 있다.

첫 번째 노드를 삽입하는 과정은 새 노드를 생성하고, 헤드가 가리키는 노드를 링크한다.

마지막 노드를 찾고 새 노드로 링크한다. 마지막으로 헤드 노드를 새 노드로 지정한다.

중간에 노드를 삽입하는 과정은 삽입할 위치를 찾고, 새 노드를 생성한다.

이전 노드의 링크를 새 노드의 링크로 지정하고 이전 노드의 링크를 새 노드로 지정한다.

마지막 노드를 삽입하는 과정은 존재하지 않는 노드 앞에 문별 노드 삽입을 시도하면 끝까지 데이터를 찾지 못한다.

중간 노드 삽입할때 삽입할 위치를 찾는 방식으로 데이터를 찾고 찾지 못했다면 새 노드를 생성한다.

현재 노드의 링크를 새 노드로 지정하고 새 노드의 링크를 헤드가 가리키는 노드로 지정한다.

## 원형 연결 리스트의 노드 삽입 함수 ##
## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):
    current = start
    if current == 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
            pre.link = node
            return
            
    
    node = Node() # 마지막 노드 삽입
    node.data = insertData
    current.link = node
    node.link = head
    
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)
    
    insertNode("다현", "화사")
    printNodes(head)
    
    insertNode("사나", "솔라")
    printNodes(head)
    
    insertNode("재남", "문별")
    printNodes(head)

 

 3  노드 삭제

원형 원결 리스트에 노드를 삭제하는 방식은 맨 앞의 노드를 삭제할 때와 나머지 노드를 삭제할 때로 나눌수 있다.

첫 번째 노드를 삭제하는 과정은 현재 노드를 삭제할 노드인 헤드와 동일하게 만든다.

헤드를 삭제할 노드의 링크가 가리키던 노드로 변경된다. 마지막 노드를 찾고 링크에 헤드가 가리키는 노드를 지정한다.

현재 노드를 메모리에서 제거한다.첫 번째 외 노드를 삭제하는 과정은 헤드에서 시작해서 현재 노드가 삭제할 노드인지 찾고 그 이전 노드를 이전 노드로 저장한다. 삭제할 노드를 찾으면, 이전 노드의 링크를 현재 노드의 링크로 지정한다.

현재 노드를 메모리에서 제거한다.

## 원형 연결 리스트의 노드 삭제 함수 ##
## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != start:
        current = current.link
        print(current.data, end=' ')
    print()
    
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
            
## 전역 변수 선언 부분 ##
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)
    
    deleteNode("다현")
    printNodes(head)
    
    deleteNode("쯔위")
    printNodes(head)

    deleteNode("지효")
    printNodes(head)
    
    deleteNode("재남")
    printNodes(head)

 

 4  노드 검색

완성된 원형 연결 리스트에서 노드를 검색하는 방식을 구현해 보자

현재 노드를 헤드와 동일하게 만들고, 검색할 데이터인지 비교한다.

현재 노드를 다음 노드로 이동하면서 반복하고, 검색할 데이터와 동일하다면 현재 노드를 반환한다.

찾지 못했다면 None을 반환한다.

## 원형 연결 리스트의 노드 검색 함수 ##
## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != start:
        current = current.link
        print(current.data, end=' ')
    print()
    
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
    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)
    
    fNode = findNode("다현")
    print(fNode.data)
    
    fNode = findNode("쯔위")
    print(fNode.data)

    fNode = findNode("재남")
    print(fNode.data)

 

위 코드를 수정해서 데이터를 찾은 경우와 찾지 못한 경우를 출력하도록 했다.

class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != start:
        current = current.link
        print(current.data, end=' ')
    print()
    
def findNode(findData) :
    global memory, head, current, pre
    
    current = head
    if current.data == findData :
        print(" # 첫 노드에서 찾음 #")
        return current
    
    while current.link != head :
        current = current.link
        if current.data == findData :
            print("# 중간 노드에서 찾음 #")
            return current
    print("# 찾는 노드가 없음 #")
    return Node()
            

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)
    
    fNode = findNode("다현")
    print(fNode.data)
    
    fNode = findNode("쯔위")
    print(fNode.data)

    fNode = findNode("재남")
    print(fNode.data)

 

 5  원형 연결 리스트의 응용

원형 연결 리스트를 응용하여 랜덤 하게 숫자 7개를 뽑은 후 순서대로 원형 연결 리스트로 구성한다.

그리고 원형 리스트를 돌면서 홀수와 짝수의 개수를 센다. 연속해서 다시 한 바퀴를 돌아 홀수 또는 짝수 중 많은 것을 모두 음수로 변경한다.

## 원형 연결 리스트를 활용한 홀수와 짝수 구분 프로그램 ##
import random

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

def printNodes(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != start:
        current = current.link
        print(current.data, end=' ')

def countOddEven() :
    global memory, head, current, pre
    
    odd,even = 0, 0
    if head == None :           
        return False
            
    current = head
    while  True :
        if current.data % 2 == 0 :
            even += 1
        else :
            odd += 1
        if current.link == head :
            break;
        current = current.link
            
    return odd,even

def makeZeroNumber(odd, even) :
    if odd > even :
        reminder = 1
    else :
        reminder = 0
        
    current = head
    while True :
        if current.data % 2 == reminder :
            current.data *= -1
        if current.link == head :
            break;
        current = current.link
        
memory = []
head, current, pre = None, None, None
                
if __name__ == "__main__" :
    
    dataArray = []
    for _ in range(7) :
        dataArray.append(random.randint(1, 100))
        
    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)
    
    oddCount, evenCount = countOddEven()
    print(oddCount, evenCount)
    print('홀수 -->', oddCount, '\t', '짝수 -->', evenCount)
    
    makeZeroNumber(oddCount, evenCount)
    printNodes(head)

 

이번엔 -100에서 100까지 숫자 7개를 뽑고 개수를 세고 양수는 음수로, 음수는 양수로 변경한다.

import random

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

def printNodes(start):
    current = start
    if current == None:
        return
    print(current.data, end=' ')
    while current.link != start:
        current = current.link
        print(current.data, end=' ')

def countPlusMinus() :
    global memory, head, current, pre
    
    plus, minus = 0, 0
    if head == None :           
        return False
            
    current = head
    while  True :
        if current.data > 0 :
            plus += 1
        else :
            minus += 1
        if current.link == head :
            break;
        current = current.link
            
    return plus, minus

def makeChangeNumber(plus,minus) :   
    current = head
    while True :
        if current.data != 0 :
            current.data *= -1
        if current.link == head :
            break;
        current = current.link
        
memory = []
head, current, pre = None, None, None
                
if __name__ == "__main__" :
    
    dataArray = []
    for _ in range(7) :
        dataArray.append(random.randint(-100, 100))
        
    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)
    
    plusCount, minusCount = countPlusMinus()
    print(plusCount, minusCount)
    print('양수 -->', plusCount, '\t', '음수 -->', minusCount)
    
    makeChangeNumber(plusCount, minusCount)
    printNodes(head)