20260514 데이터구조와 알고리즘 11주차

강의 핵심 요약 — 연결 리스트 II (원형 연결 리스트, 이중 연결 리스트, 스택/큐 구현)

이번 강의는 연결 리스트 심화편.

핵심 흐름:

단순 연결 리스트
→ 원형 연결 리스트
→ 이중 연결 리스트
→ 연결 리스트 기반 스택
→ 연결 리스트 기반 큐

특히:

• 원형 연결 리스트(Circular Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 헤드 노드(Header Node)
• 연결 리스트 기반 Stack/Queue

이 부분이 핵심이었음.

---

1. 원형 연결 리스트(Circular Linked List)

정의:

마지막 노드가 첫 노드를 가리키는 리스트

---

일반 연결 리스트

10 -> 20 -> 30 -> NULL

끝 존재.

---

원형 연결 리스트

10 -> 20 -> 30
^             |
|_____________|

끝이 없음.

---

2. 원형 연결 리스트 특징

교수 핵심:

어떤 노드에서도 전체 순회 가능

---

3. 왜 원형 연결 리스트 쓰는가

장점:

• 반복 순회 쉬움
• 끝 처리 간단
• 순환 구조 표현 가능

예:

• 멀티 플레이어 턴
• 음악 재생 목록
• 라운드 로빈 스케줄링

---

4. head 포인터 특징

중요:

head가 마지막 노드를 가리킴

---

이유

처음/끝 삽입 쉬워짐.

---

5. insert_first()

맨 앞 삽입.

핵심 코드:

node->link = head->link;
head->link = node;

---

의미

1단계

새 노드가 첫 노드 가리킴

---

2단계

마지막 노드가 새 노드 가리킴

---

6. insert_last()

끝 삽입.

핵심 코드:

node->link = head->link;
head->link = node;
head = node;

---

마지막 줄 중요

head = node;

새 마지막 노드 지정.

---

7. print_list()

출력 핵심.

do {
   ...
} while(p != head);

---

왜 do-while 사용?

원형 구조라:

최소 한 번은 실행해야 함

---

8. 원형 연결 리스트 응용 — 멀티 플레이어 게임

강의 대표 예제.

KIM
CHOI
PARK
KIM
CHOI
PARK

반복 순환.

---

9. 핵심 원리

p = p->link;

만 계속 하면:

자동 순환

됨.

NULL 끝처리 필요 없음.

---

10. 단순 연결 리스트 문제점

교수 강조:

이전 노드를 찾기 어렵다

---

예

현재 노드 삭제하려면:

이전 노드 필요

근데 단방향이라 불편함.

---

11. 이중 연결 리스트(Doubly Linked List)

해결책:

양쪽 방향 연결

---

12. 노드 구조

핵심:

typedef struct DListNode {
    element data;
    struct DListNode *llink;
    struct DListNode *rlink;
}

---

의미

필드	역할
llink	이전 노드
rlink	다음 노드

---

13. 이중 연결 리스트 장점

양방향 이동 가능

앞/뒤 이동 자유

---

삭제 쉬움

이전 노드 바로 접근 가능.

---

14. 단점

교수 강조:

공간 더 많이 사용
코드 복잡

---

15. 헤드 노드(Header Node)

중요 개념.

정의:

데이터 저장 안 하는 특수 노드

---

역할

삽입/삭제 코드 단순화.

---

16. 헤드 노드 vs 헤드 포인터

많이 헷갈림.

개념	의미
head pointer	시작 주소 변수
head node	실제 존재하는 노드

---

17. init()

초기화 핵심.

phead->llink = phead;
phead->rlink = phead;

---

의미

공백 상태에서도:

자기 자신 가리킴

---

18. 이중 연결 리스트 삽입

핵심 함수:

dinsert()

---

핵심 코드

newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;

---

19. 삽입 핵심 원리

중요:

링크 순서 틀리면 연결 깨짐

---

해야 하는 것

새 노드를:

• 양쪽과 연결
• 기존 링크 수정

순서대로 처리.

---

20. 삭제 연산

핵심 코드:

removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
free(removed);

---

의미

삭제 노드를:

양옆 노드끼리 직접 연결

---

21. mp3 재생기 예제

이번 강의 핵심 응용 예제.

< 이전곡
> 다음곡

---

22. 왜 이중 연결 리스트가 적합한가

노래 이동:

• 이전 곡
• 다음 곡

둘 다 필요.

즉:

양방향 탐색 필수

---

23. current 포인터

현재 재생 위치 저장.

current = current->rlink;

→ 다음곡

current = current->llink;

→ 이전곡

---

24. head 건너뛰기

중요 코드:

if(current == head)
    current = current->rlink;

---

이유

head node는:

실제 데이터 없음

---

25. 연결 리스트 기반 스택

배열 대신 연결 리스트 사용.

---

구조

typedef struct {
    StackNode *top;
} LinkedStackType;

---

26. push()

핵심 코드:

temp->link = s->top;
s->top = temp;

---

의미

새 노드가:

기존 top 위에 올라감

---

27. pop()

핵심 코드:

temp = s->top;
s->top = s->top->link;
free(temp);

---

핵심

top 제거 후:

다음 노드가 새 top

---

28. 연결 리스트 스택 장점

크기 제한 거의 없음

배열 스택:

overflow 가능

---

연결 리스트:

필요할 때 malloc

---

29. 연결 리스트 기반 큐

구조:

QueueNode *front, *rear;

---

30. enqueue()

핵심 코드:

q->rear->link = temp;
q->rear = temp;

---

중요

교수 강조:

순서 중요

---

이유

rear 먼저 바꾸면:

기존 연결 끊김

---

31. dequeue()

핵심 코드:

q->front = q->front->link;

---

마지막 노드 삭제 시 중요

if(q->front == NULL)
    q->rear = NULL;

---

이유

큐 완전히 비면:

front/rear 둘 다 NULL

이어야 함.

---

32. 교수 전체 핵심 메시지

이번 강의 전체 핵심:

연결 리스트는
포인터 연결 구조를 이해하는 게 전부다

였음.

특히:

링크 수정 순서

엄청 강조함.

---

시험 관점 핵심

진짜 중요:

원형 연결 리스트

• 마지막 노드가 처음 가리킴
• do-while 사용 이유

---

이중 연결 리스트

• llink / rlink
• 양방향 이동

---

헤드 노드

• 데이터 없음
• 코드 단순화

---

삽입/삭제

• 링크 수정 순서 중요

---

스택

push:
temp->link = top
top = temp

---

큐

rear->link = temp
rear = temp

순서 중요.

---

절대 헷갈리면 안 되는 거

구조	특징
단순 연결 리스트	한 방향
원형 연결 리스트	끝 없음
이중 연결 리스트	양방향

교수 계속 강조한 거:

포인터 연결 순서 틀리면 자료구조 박살난다

이거였음 ㅋㅋ