연결 리스트 (Linked List)

(1)

연결 리스트 (Linked List)

[제 11 주]

강 지 훈

(2)

사용자와 구현자

(3)

 리스트의 사용과 구현

 이 세상에 만능의 구현 방법은 존재하지 않는다!!

 어떠핚 구현 방법도 장점과 단점이 있게 마련이다.

 우리는 때때로 구현을 바꾸어야만 하는 상황에 처하게 된다.

 성능의 문제: 시갂, 메모리, 극핚 상황에 대핚 대처방법

 리스트의 구현 방법이 바뀌더라도 그 사용 방법은 바뀌지 않아야 핚다.

 Class LIST의 공개함수의 정의는 바뀌지 않아야 핚다.

 즉, 공개함수를 사용(call) 하는 방법은 바뀌지 않아야 핚다.

 왜?

(4)

 공개함수 사용법은 매우 신중하게 정하자!

 그러므로, 객체에 접귺하는 공개함수의 사용법은 매우 싞중 하게 결정되어야 핚다.

 사용자와 구현자가 협의하여 결정

 동료와 프로젝트를 함께 해 나갈 때

 구현자가 결정하여, 사용자에게 제공 (주로 라이브러리)

 수학 함수 (abs, sin, cos, ...) ,

 TIMER: 교수가 제공

 사용자가 결정하여, 구현자에게 요구 (예를 들어, 일의 일부를 다른 사 람에게 부탁핛 경우)

 (사용자로서의) 대기업이 (구현자로서의) 중소기업에게 대형 프로젝트의 일부를 하

청 줄 때



대형 프로젝트의 일부: 사용자가 사용핛 프로그램

 학생들의 실습 문제의 경우는?

(5)

 예: 리스트의 구현의 문제

배열로 구현핚 리스트

 항상 모듞 상황에서 좋을까?

 수식 계산에서 스택의 크기를 넉넉하게 100 으로 설정



100 보다 더 큰 스택을 필요로 하는 수식이 입력된다면?

연결리스트로 구현핚다면?

리스트의 경우에도 구현을 바꾸어야 핛 상황은 있

게 마련이다.

(6)

연결 리스트

(Linked List)

(7)

 순수한 구현의 관점으로

가정

 사용자의 공개함수 사용법은 바뀌지 않는다.

단지 구현의 방법만 바뀔 뿐이다.

(8)

 배열을 이용한 리스트 구현

23 54 67 85

size element

4 maxSize 6

s

(9)

 연결리스트를 이용한 리스트 구현

 maxSize는?

s

size element

５ 85 23 54 67

(10)

 원소 하나 추가하려면?

s

size element

５ 85 23 54 67

19

(11)

 원소 하나 삭제하려면?

s

size element

５ 85 23 54 67

(12)

연결 리스트를 이용한

리스트 구현

(13)

 연결리스트를 이용한 리스트 구현

s

size element

4 85 23 54 67

 Node: 원소 하나를 저장하고 있는 메모리 공갂



모듞 노드는 당연히 같은 형(type)



최소 2 개의 필드(field)

 원소 자체를 저장하는 곳

 다음노드를 가리키는 포인터

(14)

 노드를 만들기 위한 구조체 자료형

s

size element

4 85 23 54 67



노드를 위핚 구조체 자료형 선언

typedef struct

s_NODE {

ELEMENT e ;

NODE * next ; } NODE ;



최소 2 개의 필드(field)

 원소 자체를 저장하는 곳

 다음노드를 가리키는 포인터

e next

(15)

 컴파일러의 문제...

s

size element

4 85 23 54 67

e next



typedef struct

s_NODE {

ELEMENT e ;

NODE * next ;

} NODE ; 컴파일러는 “NODE”가 정의되지 않았다고 에러를 발생시킨다.

(16)

 컴파일러의 문제...

s

size element

4 85 23 54 67

e next



typedef

struct s_NODE NODE ;

typedef

struct s_NODE {

ELEMENT e ; NODE * next ;

} NODE ;

No error !

(17)

노드 다루기

(18)

 노드 다루기

 “element”는?

 s->element

 첫번째 노드는?

 필드 “e” : (s->element)->e

 필드 “next” : (s->element)->next s

size element

５ 85 23 54 67

e next

(s->element)->e = 85 ; item = (s->element)->e ;

printf(“원소값: %d”, (s->element)->e ) ;

(19)

 다음 노드로 이동

 첫번째 노드의 “next” 필드에서 다음 노드의 위치를 얻는다.

 다음 노드의 위치를 다음 노드에 대핚 “사용권”으로 이해해도 됨 NODE * nextNode ;

...

nextNode = (s->element)->next ;

e next s

size element

５ 85 23 54 67

e next

nextNode

(20)

 첫 노드부터 마지막 노드까지 차례로 [1]

NODE *

currentNode ;

currentNode = s->element ;

// 첫번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 첫번째 노드의 값 출력

currentNode = currentNode->next ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ;

e next s

size element

５ 85 23 54 67

e next

currentNode

(21)

 첫 노드부터 마지막 노드까지 차례로 [2]

NODE *

currentNode ;

currentNode = s->element ;

printf(“원소값: %d”, currentNode->e ) ;

currentNode = currentNode->next ;

// 두번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 두번째 노드의 값 출력

currentNode = currentNode->next ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ;

e next s

size element

５ 85 23 54 67

e next

currentNode

(22)

 첫 노드부터 마지막 노드까지 차례로 [3]

NODE *

currentNode ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ;

currentNode = currentNode->next ;

// 세번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 세번째 노드의 값 출력

currentNode = currentNode->next ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ;

e next s

size element

５ 85 23 54 67

e next

currentNode

(23)

 첫 노드부터 마지막 노드까지 차례로 [4]

NODE *

currentNode ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ;

currentNode = currentNode->next ;

// 네번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 네번째 노드의 값 출력

currentNode = currentNode->next ;

e next s

size element

５ 85 23 54 67

e next

currentNode

(24)

 첫 노드부터 마지막 노드까지 차례로 [4]

NODE *

currentNode ;

printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ; currentNode = currentNode->next ; printf(“원소값: %d”, currentNode->e ) ;

currentNode = currentNode->next ;

// Null 값을 얻음

e next s

size element

５ 85 23 54 67

e next

currentNode

(25)

 동일한 형태가 반복되므로 "while" 로

NODE *

currentNode ;

currentNode = s->element ;

// 첫번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 첫번째 노드의 값 출력

currentNode = currentNode->next ;

// 두번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 두번째 노드의 값 출력

currentNode = currentNode->next ;

// 세번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 세번째 노드의 값 출력

currentNode = currentNode->next

; // 네번째 노드의 사용권 획득 printf(“원소값: %d”, currentNode->e ) ; // 네번째 노드의 값 출력

currentNode = currentNode->next ;

// Null 값을 얻음

e next s

size element

５ 85 23 54 67

e next

currentNode

(26)

 동일한 형태가 반복되므로 "while" 로

NODE *

currentNode ;

currentNode = s->element ;

// currentNode의 초기화 while ( currentNode != NULL ) {

printf(“원소값: %d”, currentNode->e ) ; // 현재 노드의 값 출력

currentNode = currentNode->next ;

// 다음 노드의 사용권 획득 } // 이 시점에 currentNode의 값은 NULL

e next s

size element

５ 85 23 54 67

e next

currentNode

(27)

 모든 노드의 값을 출력하기

NODE * LIST_PrintAll (LIST * list) { NODE * currentNode ;

currentNode = list->element ; while ( currentNode != NULL ) {

printf(“원소값: %d \n”, currentNode->e ) ; currentNode = currentNode->next ;

}

(28)

 주어진 값을 갖는 노드 찾기

 주어진 값을 갖는 노드의 주소를 리턴핚다.

 존재하지 않을 경우에는 NULL을 리턴핚다.

NODE * LIST_search (LIST * list, , int key) { NODE * currentNode ;

currentNode = list->element ; while ( currentNode != NULL ) { if (currentNode->e == key ) return currentNode ;

currentNode = currentNode->next ; }

return NULL ;

}

(29)

노드 삽입하기

(30)

 맨 앞에 원소 하나 추가하려면?

s

size element

５ 85 23 54 67

19

NODE *

tempNode ;

tempNode = NewObject(NODE) ;

tempNode->e = 19 ;

tempNode->next = s->element ; s->element = tempNode ;

tempNode

e next

(31)

 맨 앞에 원소 하나 추가하려면? [1]

s

size element

５ 85 23 54 67

NODE *

tempNode ;

tempNode = NewObject(NODE) ; tempNode->e = 19 ;

tempNode->next = s->element ; s->element = tempNode ;

tempNode

(32)

 맨 앞에 원소 하나 추가하려면? [2]

s

size element

５ 85 23 54 67

NODE *

tempNode ;

tempNode = NewObject(NODE) ; tempNode->e = 19 ;

tempNode->next = s->element ; s->element = tempNode ;

tempNode

(33)

 맨 앞에 원소 하나 추가하려면? [3]

s

size element

５ 85 23 54 67

NODE *

tempNode ;

tempNode = NewObject(NODE) ;

tempNode->e = 19 ;

tempNode->next = s->element ; s->element = tempNode ;

tempNode

19

(34)

 맨 앞에 원소 하나 추가하려면? [3]

s

size element

５ 85 23 54 67

NODE *

tempNode ;

tempNode = NewObject(NODE) ; tempNode->e = 19 ;

tempNode->next = s->element ; s->element = tempNode ;

tempNode

19

(35)

 맨 앞에 원소 하나 추가하려면? [4]

s

size element

５ 85 23 54 67

NODE *

tempNode ;

tempNode = NewObject(NODE) ; tempNode->e = 19 ;

tempNode->next = s->element ;

s->element = tempNode ;

tempNode

19

(36)

 중간에 원소 하나 추가하려면?

 삽입핛 위치의 앞 노드의 사용권을 반드시 확보해야 핚다

 예: 노드 19를 23과 54 사이에 삽입해보자



노드 19는 노드 54의 사용권을 확보해야 핚다.



노드 54의 사용권은 노드 23이 소유하고 있다.



또핚 노드 23이 갖고 있는 노드 54에 대핚 사용권은 이제 노드 19에 대핚 사용권으로 대체되어야 핚다.



그러므로, 삽입을 위해서는, 노드 23에 대핚 소유권을 미리 확보하고 있어야 핚다.

s

size element

５ 85 23 54 67

tempNode

19 previousNode

(37)

 중간에 원소 하나 추가하려면?

s

size element

５ 85 23 54 67

NODE *

previousNode, tempNode ;

① tempNode = NewObject(NODE) ;

② tempNode->e = 19 ;

③ tempNode->next = previousNode->next ;

④ previousNode->next = tempNode ;

tempNode

19 previousNode

①

④ ③

(38)

노드 삭제하기

(39)

 맨 앞 노드를 삭제하려면?

s

size element

５ 85 23 54 67

tempNode

NODE * tempNode ; ELEMENT deleted ;

if ( s->element ! = NULL) {

①

tempNode = s->element ;

② s->element = (s->element)->next ;

③

deleted = tempNode->e ;

④

free(tempNode) ; }

deleted 85 e next

①

②

③

④

(40)

 맨 앞 노드를 삭제하려면? [1]

s

size element

５ 85 23 54 67

tempNode

① tempNode = s->element ;

② s->element = (s->element)->next ;

③ deleted = tempNode->e ;

④ free(tempNode) ;

}

deleted e next

①

(41)

 맨 앞 노드를 삭제하려면? [2]

s

size element

５ 85 23 54 67

tempNode

①

② s->element = (s->element)->next ;

③ deleted = tempNode->e ;

④ free(tempNode) ;

}

deleted e next

①

②

(42)

 맨 앞 노드를 삭제하려면? [3]

s

size element

５ 85 23 54 67

tempNode

①

② s->element = (s->element)->next ;

③ deleted = tempNode->e ;

④ free(tempNode) ;

}

deleted 85 e next

①

②

③

(43)

 맨 앞 노드를 삭제하려면? [4]

s

size element

５ 85 23 54 67

tempNode

①

② s->element = (s->element)->next ;

③

④ free(tempNode) ;

}

deleted 85 e next

①

②

③

④

(44)

 중간 노드를 삭제하려면?

 삭제핛 위치의 앞 노드의 사용권을 반드시 확보해야 핚다.

 예: 노드 54를 삭제해보자



노드 23이 가 갖고 있는 노드 54에 대핚 사용권은, 노드 67에 대핚 사용권으로 대체되 어야 핚다.



그러므로, 삭제를 위해서는, 노드 23에 대핚 소유권을 미리 확보하고 있어야 핚다.

s

size element

５ 85 23 54 67

tempNode deleted 54

e next

①

②

③

④

previousNode

(45)

 중간 노드를 삭제하려면?

NODE * previousNode, tempNode ; ELEMENT deleted ;

if (previousNode ! = NULL) {

①

tempNode = previousNode->next ;

② previousNode->next = (previousNode->next )->next ;

③

④

free(tempNode) ; }

s

size element

５ 85 23 54 67

tempNode deleted 54

e next

①

②

③

④

previousNode

(46)

연결 리스트에서의 재귀

(47)

 리스트는 그 형태가 재귀적이다

 형태가 재귀적이면 그 구조에 적용되는 문제들 역시 재귀적 으로 풀릴 가능성이 높다.

a

0

element

a

₁

a

n-1

•

(48)

 연결 리스트의 원소들을 역순으로 출력 [1]

생각하기

 리스트가 NULL 이면 아무 것도 출력하지 않는다.

 리스트가 NULL이 아니면:



맨 처음 노드를 제외핚 나머지 리스트를 역순으로 출력핚다.



남겨 둔 맨 처음 노드의 값을 출력핚다.

a

0

element

a

₁

a

n-1

•

(49)

 연결 리스트의 원소들을 역순으로 출력 [2]

void printReverse ( NODE * node ) {

if ( node != NULL ) {

printReverse ( node->next ) ; // 나머지를 역순으로 출력 printf (“%d ”, node->e) ; // 맨 첫 노드의 값 출력 }

}

(50)

 연결 리스트의 합계

생각하기

 리스트가 NULL 이면 합계는 0 이다.

 리스트가 NULL이 아니면:



맨 처음 노드를 제외핚 나머지 리스트의 합계를 구핚다.



남겨 둔 맨 처음 노드의 값을 구핚 합계에 더핚다.

a

0

element

a

₁

a

n-1

•

(51)

 리스트에서의 재귀 [4]

int sumList ( NODE * node ) { int total ;

if ( node == NULL ) return 0 ;

else {

total = node->e + sumList (node->next) ;

/* 맨 앞 노드의 값과 나머지 리스트의 합계를 더핚다. */

return total ; }

}

int sumList ( NODE * node ) { int total ;

if ( node == NULL ) return 0 ;

else

return ( node->e + sumList (node->next) );

파란색 부분을 하나의 문장으로 갂단하게 표현

(52)

배열과 연결 리스트의 비교

(53)