[파이썬 자료구조와 알고리즘] Chapter 05. 원형 연결 리스트

학습목표

• 원형 연결 리스트의 개념 파악
• 원형 연결 리스트와 단순 연결 리스트의 차이 이해
• 원형 연결 리스트의 데이터 삽입/삭제 원리 이해
• 파이썬으로 원형 연결 리스트를 조작하는 코드 작성

 

Secton00. 생활 속 자료구조와 알고리즘

'해랑': 서울에서 출발해서 전국을 돌고 다시 서울로 돌아오는 일정

원형 연결 리스트=시작 위치와 다음 위치가 계속 이어진 후 마지막에 다시 돌아오는 형태

 

 

Section01. 원형 연결 리스트의 기본

1. 원형 연결 리스트의 개념

-단순 연결 리스트: 배열에 데이터를 차례대로 저장하므로 데이터의 실제 위치 순서로 데이터가 구성, 시작부터 끝까지 차례대로 방문 가능

끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 함

 

-원형 연결리스트(Circular Linked List): 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정됨

리스트 형태가 원으로 구성됨, 회전 연속 방문 가능

 

2. 원형 연결 리스트의 원리

🤎노드 구조

-단순 연결 리스트와 원형 연결 리스트 공통: 데이터+링크

첫 번째 노드를 가리키는 헤드(head)사용, 원형 연결리스트의 시작점으로 사용

 

🤎노드 삽입

1단계: 새 노드 생성

2단계: 링크 수정(이전 노드 링크 새 노드한테 붙임, 이전 노드 링크는 새 노드로 변경)

 

🤎노드 삭제

1단계: 링크 수정

2단계: 노드 삭제

이전 노드 링크 뒤에 노드로 연결

삭제할 애 삭제하기

 

 

Section02. 원형 연결 리스트의 간단 구현

1. 노드의 생성과 연결 구현

🤎노드 생성

Node 데이터형 생성

원형 연결리스니까 첫 번째 노드와 마지막 노드가 연결되는 구조를 가져야 함

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

두 번째 노드를 생성한 후 첫 번째 노드의 링크에 두 번째 노드를 연결하고, 두 번째 노드의 링크에는 첫 번째 노드를 연결해서 원형 구조를 갖게 하기

 

 

2. 데이터가 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=' ')

🤎노드 삽입

새 노드 생성하고 데이터 입력

새노드의 링크에 앞의 노드의 링크 복사

그러면 새노드의 링크랑 앞의 노드 링크랑 같은 곳을 가리킴

앞의 노드 링크를 새 노드의 링크로 지정

 

원형 연결 리스트의 중간 노드 삽입

newNode=Node()
newNode.data="재남"
newNode.link=node2.link
node2.link=newNode

🤎노드 삭제

삭제할 노드의 링크를 바로 앞 노드의 링크로 복사

삭제하기~

node2.link=node3.link
del(node3)

current=node1
print(current.data, end=' ')
while current.link != node1:
	current=current.link
    print(current.data, end=' ')

 

 

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

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

-헤드(head): 첫 번째 노드

-현재(current): 지금 처리 중인 노드

-이전(pre): 현재 처리 중인 노드의 바로 앞 노드

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

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

사용자가 입력하거나 배열에서 데이터를 추출한 후 값을 계속 단순 연결 리스트로 만드는 코드 작성

🤎데이터 입력 과정

빈 노드 생성

사용자가 직접 첫 번째 데이터를 입력하거나 저장소에서 데이터 가져와서 대입

헤드는 첫 번째 노드를 가리키도록 하고 새 노드의 링크는 헤드가 가리키는 노드로 연결

그러면 자기 자신을 가리키는 형태가 됨

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

 

3. 노드 삽입

🤎첫 번째 노드 삽입

새 노드 생성

새노드의 링크로 헤드가 가리키는 노드 지정

헤드가 가리키는 노드에서 시작해서 last를 다시 다음 노드로 변경하며 마지막 노드를 찾는다

마지막 노드의 링크에 새 노드를 지정

헤드 노드를 새 노드로 지정

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=Noe()
        node.data="솔라"
        node.link=current
        pre.link=node

🤎마지막 노드 삽입

존재하지 않는 데이터 앞에 새로운 데이터 노드 삽입 을 시도하면 끝까지 존재하지 않는 데이터는 찾지 못한다. 결국 마지막 노드에 새로운 데이터를 삽입한다.

#마지막 노드까지 "재남"을 찾지 못한 후
node=Node()
node.data="문별"
current.link=node
node.link=head

🤎노드 삽입 함수의 완성

class Node():
	def __init__ (self):
    	self.data=Node
        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.link=node
    head=node
    return
    
    current=head
    while current.link!=head: #중간 노드 삽입
    	pre=current
        current=current.link
        if current.data==findData:
        	node=Node()
            node.datainsertData
            node.link=current
            pre.link=node
            return
            
    node=Node() #마짐가 노드 삽입
    node.data=insertData
    current.link=node
    node.link=head
    
#메인 코드 부분
if __name__=="__main__":
#생략

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

 

4. 노드 삭제

🤎첫 번째 노드 삭제

현재 노드를 삭제할 노드인 헤드와 동일하게 만든다.

헤드를 삭제할 노드의 링크가 가리키는 노드로 변경한다.

헤드에서 시작해서 마지막 노드를 찾는다.

마지막 노드의 링크에 헤드가 가리키는 노드를 지정한다.

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

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 current.data=="쯔위":
    	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)
            reuturn
            
 #전역변수 선언 부분
 #생략
 
 #메인 코드 부분
 if __name__=="__main__":
 
 #생략
 
 deleteNode("다현")
 printNodees(head)

 

 

5. 노드 검색

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

검색할 데이터의 노드를 반환하는 방식으로 처리

 

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

검색할 데이터와 동일하다면 현재 노드를 반환한다.

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

③앞의 2단계를 끝까지 진행하고, 검색할 데이터를 찾지 못했다면 None을 반환한다.

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 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()
        
#메인 코드 부분
if __name__=="__main__":
#생략

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

 

Section04. 원형 연결 리스트의 응용

1~100 숫자 중 7개(중복 허용) 뽑은 다음에 원형 연결 리스트로 구성

헤드부터 한 바퀴 방문하면서 홀짝 중 더 많은 수를 음수로 변경

①입력할 데이터를 랜덤하게 7개 발생시켜 dataArray 배열에 저장

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()
    ode.data=data
    pre.link=node
    node.link=head
    memory.append(node)

③원형 연결 리스트 전체를 1회 방문하면서 홀수와 짝수의 개수를 센다.

current=head
while True:
	if current.data가 짝수면:
    	짝수개수+=1
    else:
    	홀수개수+=1
   	if current.link==head:
    	break;
    current=current.link

④짝수 또는 홀수의 개수 중 많은 쪽 숫자를 음수로 만든다.

if 홀수개수>짝수개수:
	나머지값=1
else:
	나머지값=0
    
current=head
while True:
	if current.data%2==나머지값:
    		current.data*=-1
    	if current.link==head:
    		break;
	current=current.link

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

import random

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 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;
        curent=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))
        
    oddCount, evencount = countOddEven()
    print('홀수-->', oddCount, '\t', '짝수-->', evenCount)
    
    makeZeroNumber(oddCount, evenCount)
    printNodes(head)

 

<연습문제>

1. 원형 연결 리스트의 특징과 거리가 먼 것

정답) 3, 4

바른말-단순 연결 리스트와 유사하지만 처음과 끝이 이어져 있다. 노드 구조다.

틀린말-헤ㄷ는 필요 없다. 마짐가 노드의 링크는 비어 있다.

 

2. 정답) node1.link=node1

 

3. 정답)

node2, node3

node3

 

4. 정답)

원형 연결 리스트의 마지막 노드가 참이 되는 조건

current.link==head

 

5. 정답)

current=head

last=last.link

last.link=head

 

6. 정답)

return current

current.link!=head

current=current.link