20260507 데이터구조와알고리즘 10주차

강의 핵심 요약 — 연결 리스트 I (Linked List)

이번 강의는:

배열 기반 리스트 → 연결 리스트

로 넘어가는 첫 핵심 파트였음.

특히:

배열 리스트의 한계
연결 리스트 구조
노드(Node)
삽입/삭제
헤더 노드
원형 연결 리스트
다항식 표현

이 부분이 핵심.

1. 리스트(List)란?

리스트:

순서 있는 데이터 집합

예:

10 20 30

같은 형태.

2. 리스트 기본 연산

핵심 연산:

연산	의미
insert	삽입
delete	삭제
search	탐색
clear	전체 제거
get_entry	특정 위치 반환

3. 배열 기반 리스트(Array List)

초반엔 배열로 리스트 구현함.

typedef struct {
    element array[MAX];
    int size;
} ArrayListType;

4. 배열 리스트 장점

인덱스 접근 빠름

array[5]

즉시 접근 가능.

구현 쉬움

구조 단순함.

5. 배열 리스트 단점

핵심 문제:

중간 삽입/삭제 느림

예:

10 20 30

중간에 삽입:

10 15 20 30

하려면:

20,30 이동 필요

6. insert() 동작 원리

for(i=size-1; i>=pos; i--)
    array[i+1]=array[i];

뒤에서부터 밀어야 함.

왜 뒤에서 하냐?
앞에서 하면 값 덮어쓰기 때문.

7. delete() 동작 원리

for(i=pos; i<size-1; i++)
    array[i]=array[i+1];

뒤 값을 앞으로 당김.

8. 연결 리스트(Linked List)

배열 문제 해결하려고 등장.

핵심:

데이터를 포인터로 연결

함.

9. 노드(Node)

노드 구조:

구성	의미
data	실제 데이터
link	다음 노드 주소

예:

[10|*] -> [20|*] -> [30|NULL]

10. 노드 정의

typedef struct ListNode {
    int data;
    struct ListNode *link;
} ListNode;

11. 왜 struct ListNode *link 인가

자기 자신 타입 가리켜야 함.

즉:

다음 노드 주소 저장

하려고.

12. Head Pointer

리스트 시작 주소 저장.

ListNode *head = NULL;

13. 노드 생성

head = (ListNode *)malloc(sizeof(ListNode));

동적 메모리 생성.

데이터 저장

head->data = 10;

링크 연결

head->link = NULL;

14. 연결 리스트 장점

삽입/삭제 쉬움

포인터만 바꾸면 됨.

연속 메모리 필요 없음

배열과 다름.

크기 제한 적음

malloc 기반.

15. 연결 리스트 단점

구현 어려움

포인터 꼬이면 터짐.

디버깅 어려움

주소 실수 많음.

교수도 계속:

오류 발생하기 쉽다

강조함.

16. insert_first()

맨 앞 삽입.

핵심 코드

p->link = head;
head = p;

17. 왜 이 순서가 중요한가

순서 바꾸면:

기존 리스트 주소 잃어버림

됨.

올바른 순서

1단계

p->link = head;

기존 연결 저장.

2단계

head = p;

새 노드를 시작으로 지정.

18. 중간 삽입 insert()

p->link = pre->link;
pre->link = p;

19. 중간 삽입 핵심

반드시:

새 노드 링크 먼저 연결

해야 함.

안 그러면:

뒤 리스트 증발

함.

20. delete_first()

첫 노드 삭제.

removed = head;
head = removed->link;
free(removed);

21. free() 왜 필요한가

안 하면:

메모리 누수

발생.

22. print_list()

for(p=head; p!=NULL; p=p->link)

포인터 따라가며 출력.

종료 조건

p == NULL

즉:
끝 노드 도달.

23. 문자열 연결 리스트

정수만 가능한 게 아님.

char name[100];

사용 가능.

예:

BANANA -> KIWI -> APPLE

24. 탐색(search)

while(p != NULL)

순회하며 찾음.

if(p->data == x)

이면 성공.

25. 리스트 합치기(concat)

핵심:

첫 리스트 끝까지 이동

후:

p->link = head2;

26. reverse()

역순 만들기.

핵심 포인터 3개:

포인터	역할
p	현재
q	이전
r	임시 저장

27. reverse 핵심

q->link = r;

링크 방향 반대로 바꿈.

즉:

화살표 뒤집기

임.

28. 연결 리스트 응용 — 다항식

이번 강의 후반 핵심.

다항식을:

연결 리스트로 표현

함.

29. 다항식 노드 구조

typedef struct ListNode {
    int coef;
    int expon;
    struct ListNode *link;
}

필드	의미
coef	계수
expon	차수

30. 다항식 예시

3x^12 + 2x^8 + 1

↓

[3|12] -> [2|8] -> [1|0]

31. 다항식 덧셈 핵심

차수 비교

같으면:

계수 더함

다르면

큰 차수 먼저 결과에 추가.

32. Header Node

교수 후반 강조 개념.

일반 head pointer랑 다름.

Header Node 역할

리스트 전체 정보 저장.

예:

size
head
tail

33. 왜 Header Node 쓰는가

핵심:

tail 바로 접근 가능

없으면

맨 끝 삽입 시:

처음부터 끝까지 스캔