우리 주변에는 끝이 없이 반복되는 구조가 많습니다.
Many structures in daily life repeat endlessly.
None이 아니라 첫 번째 노드를 가리키는 연결 리스트입니다.
link → 첫 번째 노드None으로 끝나지 않음None.
link → first nodeNoneNonewhile current != Nonewhile current.link != head| 구분 | 단순 연결 리스트 | 원형 연결 리스트 |
|---|---|---|
| 마지막 link | None | 첫 번째 노드 |
| 순회 종료 | None 만남 | 시작 노드 재방문 |
| 활용 | 일반 목록 | 순환 스케줄링 |
Nonewhile current != Nonewhile current.link != head| Category | Simple Linked List | Circular Linked List |
|---|---|---|
| Last link | None | First node |
| Traversal end | Reaching None | Revisiting start node |
| Use case | General lists | Cyclic scheduling |
원형 연결 리스트의 노드 구조는 단순 연결 리스트와 동일합니다.
class Node() : def __init__(self) : self.data = None # 데이터 필드 self.link = None # 링크 필드
NoneThe node structure for a circular linked list is identical to a simple linked list.
class Node() : def __init__(self) : self.data = None # data field self.link = None # link field
NonenewNode를 생성하고 데이터에 "재남"을 저장합니다.
newNode.link에 정연 노드의 link(쯔위)를 대입합니다.newNode.link = node2.link
newNode로 변경합니다.node2.link = newNode
newNode and store "재남" in its data.
newNode.link.newNode.link = node2.link
newNode.node2.link = newNode
node2.link = node3.link
del(node3)
node2.link = node3.link
del(node3)
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 # 다시 node1을 가리킴 node3 = Node() node3.data = "쯔위" node2.link = node3 node3.link = node1 # 다시 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=" ")
link initially points back to node1while current.link != node1class Node() : def __init__(self) : self.data = None self.link = None node1 = Node() node1.data = "다현" node1.link = node1 # points to itself node2 = Node() node2.data = "정연" node1.link = node2 node2.link = node1 # points back to node1 node3 = Node() node3.data = "쯔위" node2.link = node3 node3.link = node1 # points back to node1 node4 = Node() node4.data = "사나" node3.link = node4 node4.link = node1 node5 = Node() node5.data = "지효" node4.link = node5 node5.link = node1 # last → first # traversal output current = node1 print(current.data, end=" ") while current.link != node1 : current = current.link print(current.data, end=" ")
# 앞의 Code05-01 이후에 추가 newNode = Node() newNode.data = "재남" # Step 1: 새 노드의 link를 정연의 다음(쯔위)으로 newNode.link = node2.link # Step 2: 정연의 link를 새 노드로 변경 node2.link = newNode # 순회 출력 current = node1 print(current.data, end=" ") while current.link != node1 : current = current.link print(current.data, end=" ")
Two pointer updates are needed:
newNode.link = node2.link - new node points to 쯔위node2.link = newNode - 정연 points to new node# after Code05-01, add: newNode = Node() newNode.data = "재남" # Step 1: new node's link to 정연's next (쯔위) newNode.link = node2.link # Step 2: change 정연's link to new node node2.link = newNode # traversal output current = node1 print(current.data, end=" ") while current.link != node1 : current = current.link print(current.data, end=" ")
정연(또는 재남 삽입 후라면 재남)과 사나 사이에서 쯔위를 제거합니다.
# 쯔위(node3) 삭제 # Step 1: 이전 노드의 link를 삭제 노드의 다음으로 node2.link = node3.link # Step 2: 노드 메모리 해제 del(node3) # 순회 출력 current = node1 print(current.data, end=" ") while current.link != node1 : current = current.link print(current.data, end=" ")
del은 변수 참조를 삭제합니다. 가비지 컬렉터가 실제 메모리를 회수합니다.
Remove 쯔위 from the list by bypassing it.
node2.link = node3.link - 정연 skips over 쯔위 to 사나del(node3) - free the deleted node# delete 쯔위 (node3) # Step 1: previous node's link to deleted node's next node2.link = node3.link # Step 2: free node memory del(node3) # traversal output current = node1 print(current.data, end=" ") while current.link != node1 : current = current.link print(current.data, end=" ")
del removes the variable reference. The garbage collector reclaims the actual memory.
원형 연결 리스트에서 마지막 노드의 link가 가리키는 것은 무엇인가?
None원형 연결 리스트에서 순회 시 종료 조건으로 적절한 것은?
current == Nonecurrent.link == Nonecurrent.link == headcurrent.data == None노드 A → B → C (원형)에서 B 뒤에 D를 삽입할 때, 올바른 순서는?
B.link = D 후 D.link = CD.link = C 후 B.link = DD.link = B 후 C.link = DC.link = D 후 D.link = BIn a circular linked list, what does the last node's link point to?
NoneWhat is the correct traversal termination condition for a circular linked list?
current == Nonecurrent.link == Nonecurrent.link == headcurrent.data == NoneTo insert D after B in A → B → C (circular), the correct order is:
B.link = D then D.link = CD.link = C then B.link = DD.link = B then C.link = DC.link = D then D.link = B원형 연결 리스트의 출력은 일반 연결 리스트와 다르다. 종료 조건이 None이 아니라 다시 시작 노드로 돌아왔는지 확인해야 한다.
current.link != start 조건으로 한 바퀴를 돌았는지 확인한다. 일반 연결 리스트의 current != None과 비교하자.
node.link = head). 이것이 초기 원형을 형성한다.
pre에 저장하고, 새 노드를 생성하여, pre에서 새 노드로 연결하고, 새 노드에서 다시 head로 연결한다.
Printing a circular linked list differs from a regular linked list. The termination condition is not None but rather checking whether we have returned to the start node.
current.link != start checks if we have gone around once. Compare with current != None in a regular linked list.
node.link = head). This forms the initial circle.
pre, create new node, link pre to new node, then link new node back to head.
다현 정연 쯔위 사나 지효
다현 정연 쯔위 사나 지효
findData를 가진 노드를 찾으면 그 앞에 새 노드를 삽입한다. pre.link를 새 노드로, 새 노드의 link를 current로 연결한다.
while 루프를 다 돌아도 찾지 못하면 마지막 노드 뒤에 추가한다.
결과: 화사 다현 정연 쯔위 사나 지효
"다현" 앞에 "화사"를 삽입 → head가 "화사"로 변경됨
결과: 화사 다현 정연 쯔위 솔라 사나 지효
"사나" 앞에 "솔라"를 삽입
결과: 화사 다현 정연 쯔위 솔라 사나 지효 문별
"재남"을 찾지 못해 "문별"이 마지막에 추가됨.
Output: 화사 다현 정연 쯔위 사나 지효
Insert "화사" before "다현" -- head changes to "화사"
Output: 화사 다현 정연 쯔위 솔라 사나 지효
Insert "솔라" before "사나"
Output: 화사 다현 정연 쯔위 솔라 사나 지효 문별
"재남" not found, so "문별" is appended at the end.
current에 현재 head를 저장한다 (삭제 대상).
head를 다음 노드(head.link)로 이동시킨다.
head로 변경한다.
current(이전 head)를 삭제한다.
head in current (the node to delete).
head to the next node (head.link).
head.
current (the old head).
pre와 current를 이동시키며 삭제 대상을 찾으면 pre.link = current.link로 연결을 우회한다.
current.link != head이다. 마지막 노드를 삭제해도 pre.link가 head를 가리키게 되어 자동으로 원형이 유지된다.
current.link != head. Even when deleting the last node, pre.link ends up pointing to head, so the circular structure is automatically maintained.
화사 다현 정연 쯔위 솔라 사나 지효 문별
결과: 화사 정연 쯔위 솔라 사나 지효 문별
결과: 화사 정연 솔라 사나 지효 문별
결과: 화사 정연 솔라 사나 문별
결과: 화사 정연 솔라 사나 문별
"재남"은 리스트에 없으므로 아무것도 삭제되지 않는다.
화사 다현 정연 쯔위 솔라 사나 지효 문별
Output: 화사 정연 쯔위 솔라 사나 지효 문별
Output: 화사 정연 솔라 사나 지효 문별
Output: 화사 정연 솔라 사나 문별
Output: 화사 정연 솔라 사나 문별
"재남" is not in the list, so nothing is deleted.
head부터 시작하여 먼저 head의 데이터를 확인한다.
.data에 안전하게 접근할 수 있도록 한다.
head and first check head's data.
.data.
결과: 다현
첫 번째 노드이므로 바로 반환된다.
결과: 쯔위
순회 중 발견되어 해당 노드가 반환된다.
결과: None
"재남"은 리스트에 존재하지 않는다. 전체 순회 후 빈 Node()가 반환된다. 해당 노드의 data 속성은 None이다.
| 경우 | 반환값 | data |
|---|---|---|
| head에서 발견 | head 노드 | 실제 데이터 |
| 중간에서 발견 | 일치하는 노드 | 실제 데이터 |
| 못 찾음 | 빈 Node() | None |
Output: 다현
It is the first node, so it is returned immediately.
Output: 쯔위
Found during traversal and the matching node is returned.
Output: None
"재남" does not exist in the list. After a full traversal, an empty Node() is returned. Its data attribute is None.
| Case | Return | data |
|---|---|---|
| Found at head | head node | actual data |
| Found in middle | matching node | actual data |
| Not found | empty Node() | None |
다음 원형 연결 리스트에서 insertNode("정연", "휘인")을 실행하면 리스트는 어떻게 변하는가? 각 단계의 포인터 변화를 그림으로 그려라.
리스트: 다현 -> 정연 -> 쯔위 -> 사나 -> 지효 -> (다현)
원형 연결 리스트에서 첫 번째 노드를 삭제할 때 마지막 노드의 link를 갱신하지 않으면 어떤 문제가 발생하는지 설명하라. printNodes 함수의 동작과 연관 지어 서술하시오.
findNode 함수를 수정하여 대상을 찾기 전까지 방문한 노드 수를 세도록 하라. 대상을 찾지 못하면 빈 노드 대신 -1을 반환하라.
힌트: current가 다음 노드로 이동할 때마다 증가하는 카운터 변수를 추가하라. head 노드부터 1로 시작한다.
Given the following circular linked list, what happens when insertNode("정연", "휘인") is executed? Draw the pointer changes at each step.
List: 다현 -> 정연 -> 쯔위 -> 사나 -> 지효 -> (다현)
Explain what problem occurs if the last node's link is not updated when deleting the first node in a circular linked list. Describe in relation to how the printNodes function behaves.
Modify the findNode function to count how many nodes were visited before finding the target. If the target is not found, return -1 instead of an empty node.
Hint: Add a counter variable that increments each time current moves to the next node. Start counting from 1 for the head node.
랜덤 숫자 7개를 원형 연결 리스트에 저장한 후, 홀수와 짝수의 개수를 세고 소수(적은 쪽)의 값을 음수로 변환합니다.
countOddEven() → 홀수/짝수 개수 반환makeZeroNumber() → 적은 쪽을 음수로 변환odd > even이면 소수 쪽의 나머지는 1(짝수)이므로 짝수 값을 음수로 변환합니다. while True + break 패턴으로 모든 노드를 빠짐없이 처리합니다.
45 12 78 33 91 56 27홀수 --> 4 짝수 --> 345 -12 -78 33 91 -56 27
Generate 7 random numbers, store them in a circular linked list, count odd and even numbers, then negate the minority group.
countOddEven() → return odd/even countsmakeZeroNumber() → negate the minority groupodd > even, the minority remainder is 1 (even numbers), so we negate even values. The while True + break pattern ensures every node is processed.
45 12 78 33 91 56 27Odd --> 4 Even --> 345 -12 -78 33 91 -56 27
while current.link != head 패턴은 마지막 노드의 데이터를 처리하지 못합니다! 조건 검사가 데이터 처리보다 먼저 실행되기 때문입니다.
while True + break 패턴을 사용하세요. while current.link != head는 위치를 찾을 때(데이터 처리 없이)만 사용합니다.
| 패턴 | 처리 노드 수 | 사용 상황 |
|---|---|---|
while link != head | N - 1 | 위치 탐색 |
while True + break | N (전부) | 전체 데이터 처리 |
while current.link != head condition checks before processing. When current is the last node, current.link == head is true, so the loop exits without processing that last node.
The while True + break pattern reverses the order:
break; otherwise → advanceThis guarantees every node in the circular list is visited and processed exactly once.
while True + break pattern. Use while current.link != head only when traversing to find a position (not processing data).
| Pattern | Nodes Processed | Use Case |
|---|---|---|
while link != head | N - 1 | Finding a position |
while True + break | N (all) | Processing all data |
10개의 편의점이 랜덤 좌표에 위치합니다. 원점(0, 0)에서의 거리를 기준으로 가까운 순서대로 정렬하여 원형 연결 리스트에 삽입합니다.
sqrt(x*x + y*y)('A', x, y) 여기서 'A'는 편의점 이름, x, y는 좌표입니다.
10 convenience stores are placed at random (x, y) coordinates. Sort them by Euclidean distance from the origin and build a circular linked list in ascending order.
sqrt(x*x + y*y)('A', x, y) where 'A' is the store name and x, y are coordinates.
B 편의점, 거리: 28.28...A 편의점, 거리: 42.43...E 편의점, 거리: 56.57...... (거리순 정렬)
makeStoreList()는 유클리드 거리를 비교하여 정렬 삽입을 구현합니다. head 앞 삽입, 중간 삽입, 끝 삽입의 세 가지 경우를 처리합니다.
B store, dist: 28.28...A store, dist: 42.43...E store, dist: 56.57...... (sorted by distance)
makeStoreList() implements sorted insertion by comparing Euclidean distances. It handles three cases: insert before head, insert in the middle, and insert at the tail.
각 노드가 이전 노드(plink)와 다음 노드(nlink) 두 개의 링크를 가집니다. 양방향 순회가 가능합니다.
Forward --> 다현 정연 쯔위 사나 지효Backward --> 지효 사나 쯔위 정연 다현
Each node has two links: plink (previous) and nlink (next). This enables bidirectional traversal.
Forward --> 다현 정연 쯔위 사나 지효Backward --> 지효 사나 쯔위 정연 다현
원형 연결 리스트에 랜덤 정수 10개를 저장한 후, 3의 배수의 개수와 합계를 구하는 함수 countMultiplesOf3()를 작성하시오.
while True + break 패턴을 사용하고, current.data % 3 == 0 조건으로 판별합니다.
이중 연결 리스트에 5명의 이름을 저장한 후, 특정 이름을 검색하여 그 이름의 앞 사람과 뒷 사람을 출력하는 함수를 작성하시오.
plink.data와 nlink.data를 활용합니다. 첫 번째/마지막 노드일 경우의 예외 처리도 해야 합니다.
Code05-08의 홀짝 카운트 예제를 수정하여, 적은 쪽을 음수로 만드는 대신 리스트에서 삭제하는 프로그램을 작성하시오.
pre 노드의 link를 current.link로 변경합니다. head 노드 삭제 시 특별 처리가 필요합니다.
Store 10 random integers in a circular linked list, then write a function countMultiplesOf3() that returns the count and sum of multiples of 3.
while True + break pattern with condition current.data % 3 == 0.
Store 5 names in a doubly linked list and write a function that searches for a name and prints the previous and next person.
plink.data and nlink.data. Handle edge cases for the first and last nodes.
Modify the odd-even count example (Code05-08) to delete the minority nodes from the list instead of negating them.
pre.link = current.link. Special handling is needed when deleting the head node.
| 특징 | 단순 | 원형 | 이중 |
|---|---|---|---|
| 방향 | 순방향만 | 순방향 (순환) | 양방향 |
| 마지막 노드 link | None | head | None |
| 노드당 링크 수 | 1 | 1 | 2 |
| 끝 감지 | link == None | link == head | nlink == None |
| 메모리 | 적음 | 적음 | 많음 |
| 역방향 순회 | 불가능 | 불가능 | 가능 |
| Feature | Simple | Circular | Doubly |
|---|---|---|---|
| Direction | Forward only | Forward (loop) | Both ways |
| Last node link | None | head | None |
| Links per node | 1 | 1 | 2 |
| End detection | link == None | link == head | nlink == None |
| Memory | Low | Low | Higher |
| Reverse traversal | Not possible | Not possible | Possible |
이름 배열로부터 원형 연결 리스트를 생성하고, 원형 구조를 순회하며 모든 노드를 출력합니다.
data와 link 필드를 가짐link = head (자기 자신을 가리킴)current.link == start까지 순회다현 정연 쯔위 사나 지효
link는 항상 head를 가리키며, 각 단계에서 원형 구조를 유지합니다. memory 리스트는 가비지 컬렉션을 방지합니다.
Creates a circular linked list from an array of names and prints all nodes by traversing the circular structure.
data and link fieldslink = head (points to itself)current.link == start다현 정연 쯔위 사나 지효
link always points to head, maintaining the circular structure at each step. The memory list prevents garbage collection.
다현 정연 쯔위 사나 지효화사 다현 정연 쯔위 사나 지효화사 다현 정연 솔라 쯔위 사나 지효화사 다현 정연 솔라 쯔위 사나 지효 문별
다현 정연 쯔위 사나 지효화사 다현 정연 쯔위 사나 지효화사 다현 정연 솔라 쯔위 사나 지효화사 다현 정연 솔라 쯔위 사나 지효 문별
다현 정연 쯔위 사나 지효다현 정연 사나 지효정연 사나 지효정연 사나
head.link로 변경, head를 앞으로 이동pre.link = current.link로 삭제 노드를 우회
다현 정연 쯔위 사나 지효다현 정연 사나 지효정연 사나 지효정연 사나
head.link, move head forwardpre.link = current.link to bypass the deleted node
다현 정연 쯔위 사나 지효쯔위 foundnot found
while current.link != head로 순회None 반환while 패턴을 사용할 수 있습니다.
다현 정연 쯔위 사나 지효쯔위 foundnot found
while current.link != headNone if notwhile pattern because we check head separately and return immediately upon finding the target.