원형 연결 리스트 복습

원형 선형 리스트의 개념

 

단순 연결 리스트와 비슷

원형 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가르키도록 설정되어 리스트 형태가 원 형태로 구성

 

단순 연결 리스트의 구조

#노드 생성
class Node() :               #노드 데이터 만들기
    def __init__ (self) :    #데이터를 생성할 때 자동으로 생성되는 부분
        self.data = None
        self.link - None

node1 = Node()
node.data = '다현'

node1.link = node1           #원형

 

#노드 연결
class Node() :               #노드 데이터 만들기
    def __init__ (self) :    #데이터를 생성할 때 자동으로 생성되는 부분
        self.data = None
        self.link - None

node1 = Node()
node.data = '다현'

node1.link = node1

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 = ' ')

다현 정연 쯔위 사나 지효

 

#노드 삽입 ('다현', '정연', '쯔위', '사나', '지효') 정연과 쯔위 사이
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 = ' ')

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

 

#노드 삭제 ('다현', '정연', '쯔위', '사나', '지효') 중에서 쯔위 삭제
             #1      #2     #3      #4      #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

node2.link = node3.link               #노드의 링크 복사
del(node3)                            #노드 삭제

current = node1                       #첫번째 노드를 현재 노드로 지정
print(current.data, end = ' ')        #현재 노드의 데이터 출력
while current.link != node1 :         #현재 노드에 연결된 노드가 첫번째 노드가 아닐 동안 반복 즉, 한바퀴 모두 방문하는 동안 반복
    current = current.link
    print(current.data, end = ' ')

다현 정연 사나 지효

 

#원현 연결 리스트 일반 구현(첫 번째 데이터)
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)    #노드를 메모리에 넣음

 

##원형 연결 리스트 생성##

##클래스와 함수 선언 부분##
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                 #첫 번째 노드를 헤드로 지정
    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)

다현 정연 쯔위 사나 지효

 

#원형 연결 리스트에 첫 번째 노드 삽입 과정
node = Node()             #새 노드 생성
node.data = '화사'  
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 == '사나' :
        node = Node()
        node.data = '솔라'
        node.link = current
        pre.link = node

 

#마지막 노드 삽입
current = head
while 마지막 노드까지 :
    pre = current
    current = current.link
    if current.data != '사나' :
        node = Node()
        node.data = '문별'
        current.link = node
        node.link = head

 

#노드 삽입 함수 

#클래스와 선언 부분
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
            pre.link = node
            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.link = head
del(current)
##메인 코드 부분
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)

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

 

#첫 번째 노드 삭제
current = head
head = head.link
last = head
while last.link = current :
    last = last.link
last.link = head
del(current)

 

#첫 번째 외 노드 삭제
current = head
while current.link != head :
    pre = current
    current = current.link
    if currentData == '쯔위' :
        pre.link = current.link 
        del(current)

 

#노드 삭제 함수

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

##전역 변수 선언 부분##
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)

    deleteNode('다현')
    printNodes(head)

    deleteNode('쯔위')
    printNodes(head)

    deleteNode('지효')
    printNodes(head)

    deleteNode('재남')
    printNodes(head)

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

 

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

def findNode(findData) :
    current = head
    if current.data == findData :
        return
    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)

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

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

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