제7강 연결리스트 응용
1
금오공과대학교 컴퓨터공학과
원형 연결리스트
• 원형 연결리스트
• 전체 노드의 수가 n일 경우
– 맨 처음 노드의 압쪽에 새로운 노드 삽입 : O(n) – 맨 마지막 노드의 뒤쪽에 새로운 노드 삽입 : O(n) – O(n)을 O(1)으로 줄일 주 있는 방법은?
head 포인터를 마지막 노드에 위치
2 금오공과대학교 컴퓨터공학과
head NULL NULL
…
head
NULL NULL
…
원형 연결리스트
• 맨 처음 노드 압쪽에 새로운 노드 삽입
• 맨 마지막 노드 다음에 새로운 노드 삽입
3 금오공과대학교 컴퓨터공학과
head
A B NULL C NULL D
… E
new_node (1)
(2)
new_node head
A B C NULL D NULL
…
(2) E (1)
(3)
원형 연결리스트(앞쪽 삽입)
// head: 리스트의 헤드 포인터
// p : 선행 노드, new_node : 삽입 노드
void insert_first(ListNode **head, ListNode *new_node) {
if( *head == NULL ){
*head = new_node;
new_node->link = new_node;
}
else {
new_node->link = (*head)->link;
(*head)->link = new_node;
} }
4 금오공과대학교 컴퓨터공학과
head
A B C NULL D NULL
… E
new_node (1)
(2)
원형 연결리스트(뒤쪽 삽입)
// head : 리스트의 헤드 포인터 // p : 선행 노드
// new_node : 삽입 노드
void insert_last(ListNode **head, ListNode *new_node) { if( *head == NULL ){
*head = new_node;
new_node->link = new_node;
} else {
new_node->link = (*head)->link;
(*head)->link = new_node;
*head = new_node;
} }
5 금오공과대학교 컴퓨터공학과
new_node head
A B C NULL D NULL
…
(2) E (1)
(3)
이중 연결리스트
• 하나의 노드가 선행 노드와 후속 노드에 대핚 두 개의 링크를 가짐
• 양방향 이동이 자유로움
• 메모리 사용이 증가(두 개 링크)
• 이중 연결리스트 예
금오공과대학교 컴퓨터공학과 6
이중 연결리스트(노드구조)
• 노드 구조
• 구조체 정의
typedef int element;
typedef struct DlistNode { element data;
struct DlistNode *llink;
struct DlistNode *rlink;
} DlistNode;
금오공과대학교 컴퓨터공학과 7
llink data rlink
이중 연결리스트(삽입연산)
void dinsert_node(DlistNode *before, DlistNode *new_node)
{
new_node->llink = before;
new_node->rlink = before->rlink;
before->rlink->llink = new_node;
before->rlink = new_node;
}
금오공과대학교 컴퓨터공학과 8
(1) (2) (3)
(4)
before
new_node
이중 연결리스트(삭제연산)
void dremove_node(DlistNode *phead_node,
DlistNode *removed)
{
if( removed == phead_node ) return;
removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
free(removed);
}
금오공과대학교 컴퓨터공학과 9
removed (1)
(2)
다항식 덧셈
• 연결리스트를 이용핚 다항식 표현
A=3x 12 +2x 8 +1
• 연결 리스트의 구조체 정의
typedef struct ListNode { int coef;
int expon;
struct ListNode *link;
} ListNode;
ListNode *A, *B;
금오공과대학교 컴퓨터공학과 10
A 3 12 2 8 1 0 NULL
(coef) 계수 지수
(expon) link
다항식 덧셈
금오공과대학교 컴퓨터공학과 11
A
B
C
3 12 2 8
8 12 -3 10
11 12
p
q
1 0
10 6
NULL
NULL
-3 10 r
A
B
3 12 2 8
8 12 -3 10
C 11 12
p
q
r
1 0
10 6
NULL
NULL
다항식 덧셈
금오공과대학교 컴퓨터공학과 12
A
B
3 12 2 8
8 12 -3 10
C 11 12
p
q 1 0
10 6
NULL
NULL
-3 10 2 8
r
A
B
3 12 2 8
8 12 -3 10
C 11 12
p
q 1 0
10 6
NULL
NULL
-3 10 2 8 10 6
r
1 0 NULL
