Microsoft Student (2023)728x90
728x90
원형 연결 리스트(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
728x90
728x90
'Computer Science > 자료구조' 카테고리의 다른 글
| [C] 원형 연결 리스트(Circular Linked List) (0) | 2022.07.12 |
|---|---|
| [C] 단순 연결 리스트(Singly Linked List) (0) | 2022.07.12 |
| [Python] 큐(Queue) (0) | 2022.07.01 |
| [Python] 스택(Stack) (0) | 2022.07.01 |
| [Python] 이진 탐색(Binary Search) (0) | 2022.06.29 |
| [Python] 순차 탐색(Sequential Search) (0) | 2022.06.29 |
| [Python] 단순 연결 리스트(Singly Linked List) (0) | 2022.06.22 |
| [Python] 선형 연결 리스트(Linear Linked List) (0) | 2022.06.22 |