고정 헤더 영역
상세 컨텐츠
본문
A. 원형 연결 리스트(Circlar Linked List) 개념
1) 단순 연결 리스트(Linked List)에서 마지막 노드가 헤더 노드로 링크 되어 있는 형태
2) 마지막 노드.link → 헤더 노드
B. 원형 연결 리스트(Circlar Linked List) 특징
1) 단순 연결 리스트(Linked List)의 구조, 구현 방식이 상당히 유사함
2) 리스트 형태가 원으로 구성되어 있음
3) 오버헤드가 발생하지 않음
※ 오버헤드: 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말함
C. 원형 연결 리스트(Circlar Linked List) 구조
D. 원형 연결 리스트(Circlar Linked List) 구현
1) 원형 연결 리스트(Circlar Linked List) 기본
i. Node Class를 생성한 후, __init__() 메서드를 생성해 초기화하는 과정을 거친다.
ii. node 변수를 생성해 새로운 노드를 생성한다.
iii. node 변수에 'Head_Node'라는 데이터 값을 삽입한다.
iv. 위 방법을 반복해 단순 연결 리스트(Linked List) 형태로 만든다.
v. 마지막 노드의 Link를 헤더 노드로 연결한다.
class Node() :
def __init__(self) :
self.data = None
self.link = None
node_1 = Node()
node_1.data = 'Head_Node'
node_2 = Node()
node_2.data = 'Node_2'
node_1.link = node_2
node_3 = Node()
node_3.data = 'Node_3'
node_2.link = node_3
# 마지막 노드의 Link를 헤더 노드에 연결
node_3.link = node_1
print(node_1.data, end = '\t\t')
print(node_1.link.data, end = '\t\t')
print(node_1.link.link.data, end = '\t\t')
print(node_1.link.link.link.data, end = '\t\t')
# 출력 예시) Head_Node Node_2 Node_3 Head_Node
1-1) 원형 연결 리스트(Circlar Linked List) 편하게 생성하기
i. node 변수를 생성해 새로운 노드를 생성한다.
ii. 노드의 Data를 삽입한다.
iii. head 변수에 node 변수를 삽입해 Head Node를 구분 짓는다.
iv. node의 Link를 head 변수로 연결한다.
v. current 변수를 생성해 node를 삽입한다.
vi. for 문을 사용해 새로운 노드를 삽입하며 Link를 연결하는 것을 반복한다.
# Class는 위 코드와 동일한 Class를 생성한다.
dataArray = ['Node_1', 'Node_2', 'Node_3', 'Node_4']
node = Node()
node.data = dataArray[0] # 'Node_1' 데이터 삽입
head = node
node.link = head
current = node
for data in dataArray[1:] :
node = Node()
node.data = data
current.link = node
node.link = head
current = node
print(head.data, end = '\t\t')
print(head.link.data, end = '\t\t')
print(head.link.link.data, end = '\t\t')
print(head.link.link.link.data, end = '\t\t')
print(head.link.link.link.link.data, end = '\t\t')
# 출력 예시) Node_1 Node_2 Node_3 Node_4 Node_1
2) 원형 연결 리스트(Circlar Linked List) 중간에 노드를 삽입
i. node 변수를 생성해 새로운 노드를 생성한다.
ii. 노드의 Data를 삽입한다.
iii. while문을 사용하여 원하는 위치의 노드를 찾는다.
iv. 위치를 찾았다면 새로운 노드를 생성해 데이터 값을 삽입한다.
v. 새로운 노드의 Link를 current 변수에 연결한다.
vi. pre 변수의 Link를 새로운 노드로 연결한다.
# Class는 위 코드와 동일하다
# 위 코드의 결과 값을 그대로 사용한다.
pre = head
current = head
while current.link != head :
pre = current
current = current.link
if current.data == 'Node_3' :
node = Node()
node.data = 'Node_2.5'
node.link = current
pre.link = node
break
print(head.data, end = '\t\t')
print(head.link.data, end = '\t\t')
print(head.link.link.data, end = '\t\t')
print(head.link.link.link.data, end = '\t\t')
print(head.link.link.link.link.data, end = '\t\t')
print(head.link.link.link.link.link.data, end = '\t\t')
print(head.link.link.link.link.link.link.data, end = '\t\t')
# 출력 예시) Node_1 Node_2 Node_2.5 Node_3 Node_4 Node_1
3) 원형 연결 리스트(Circlar Linked List) 첫 번째 노드 삭제
i. 삭제할 노드를 지정한다.
ii. 헤더 노드를 수정한다. (삭제할 노드 다음 노드로 설정한다)
iii. 마지막 노드를 찾는다.
iv. 마지막 노드의 Link를 수정한 헤더 노드로 바꾼다.
v. 분리해 둔 노드를 삭제한다.
# Class는 위 코드와 동일하게 사용한다.
# 데이터 값은 위 코드의 데이터 값을 사용한다.
current = head
head = head.link
last = head
while last.link != current :
last = last.link
last.link = head
del(current)
print(head.data, end = '\t\t')
print(head.link.data, end = '\t\t')
print(head.link.link.data, end = '\t\t')
print(head.link.link.link.data, end = '\t\t')
print(head.link.link.link.link.data, end = '\t\t')
# 출력 예시) Node_2 Node_2.5 Node_3 Node_4 Node_2
4) 원형 연결 리스트(Circlar Linked List) 원하는 위치의 노드 삭제
i. while문을 삭제할 노드를 찾는다.
ii. 삭제할 노드의 이전 노드에 Link를 삭제할 노드의 다음 노드로 연결한다.
iii. 분리한 노드를 삭제한다.
# Class는 위 코드와 동일하다.
# 데이터 값은 위 코드에 데이터 값을 사용한다.
pre = head
current = head
while current.link != head :
pre = current
current = current.link
if current.data == 'Node_2.5' :
pre.link = current.link
del(current)
break
print(head.data, end = '\t\t')
print(head.link.data, end = '\t\t')
print(head.link.link.data, end = '\t\t')
print(head.link.link.link.data, end = '\t\t')
# 출력 예시) Node_2 Node_3 Node_4 Node_2
