연결리스트 (Linked List) 충북대학교 컴퓨터공학과 서 영 훈

배열 vs. 연결리스트 (1) 배열 배열 선언 및 메모리 할당 Homogeneous fixed-size elements에 적합 Element access: efficient (direct access) Location of L[i] =  + (I – LB) * E where  is the beginning address of array L, LB is lower bound of subscript, and E is the size of an element Insertion and deletion of element: expensive 실행 효율은 좋지만, 메모리가 낭비될 가능성이 있음 배열 선언 및 메모리 할당 int grade[5]; grade[0] grade[1] grade[2] grade[3] grade[4] 응용컴퓨터프로그래밍

배열 및 연결리스트 (2) 연결리스트 (Linked List) 연결리스트의 예 Variable size elements에 적합 필요한 만큼만 메모리 사용 (메모리가 낭비될 가능성이 없음) 하지만 포인터 저장 공간이 추가로 필요함 Element access: inefficient (sequential access) Insertion and deletion of element: easy Flexible: Tree나 Graph 같은 자료구조를 개념 형태로 표현 가능함 연결리스트의 예 연결리스트에 “Mary” 노드를 삽입하는 예제 Bob first John Tom pre cur Mary newrec 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (1) 이름을 오름차순(ascending order)으로 정렬 자료구조 선언 John, Bob, Tom, Mary 순서로 자료가 입력된다고 가정 자료구조 선언 struct NameRec { char name[20]; struct NameRec * next; }; struct NameRec *first; // 연결리스트의 맨 처음을 가리키는 포인터 struct NameRec *newrec; // 새로 만들어지는 노드를 가리키는 포인터 struct NameRec *pre, *cur; // 삽입, 삭제 연산을 위한 포인터 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (2) 초기화 새로운 노드를 만드는 연산 first = NULL; // 처음에는 first가 가리키는 노드가 없음 새로운 노드를 만드는 연산 새로운 노드를 만드는 연산 (malloc) newrec = malloc(sizeof(struct NameRec)); 이름값 지정(이름이 “John”일 경우) strcpy(newrec->name, “John”); 스트링이기 때문에 strcpy를 이용해야 함 포인터 필드 값 지정 newrec->next = NULL; // 삽입연산을 진행할 때는 optional John newrec 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (3) 리스트에 John 삽입 리스트에 Bob 노드 삽입 if (first == NULL) first = newrec; 리스트에 Bob 노드 삽입 이름이 Bob인 노드 생성 (malloc, strcpy 함수 이용) newrec = malloc(sizeof(struct NameRec)); strcpy(newrec->name, “Bob”); 새로운 노드가 들어갈 위치 결정 cur = first; while (strcmp(newrec->name, cur->name) > 0) { pre = cur; cur = cur->next; } John first Bob newrec John first cur 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (4) 리스트에 Bob 노드 삽입 (계속) 리스트에 Tom 노드 삽입 결정된 위치에 노드 삽입 if (cur == first) { newrec->next = first; first = newrec; } 리스트에 Tom 노드 삽입 이름이 Tom인 노드 생성 newrec = malloc(sizeof(struct NameRec)); strcpy(newrec->name, “Tom”); Bob first John Tom newrec 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (5) 리스트에 Tom 노드 삽입 (계속) 새로운 노드가 들어갈 위치 결정 cur = first; while (strcmp(newrec->name, cur->name) > 0) { pre = cur; cur = cur->next; if (cur == NULL) break; } Bob first John Tom newrec cur Bob first John pre cur Bob first John pre cur = NULL 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (6) 리스트에 Tom 노드 삽입 (계속) 리스트에 Mary 노드 삽입 결정된 위치에 노드 삽입 pre->next = newrec; newrec->next = cur; 리스트에 Mary 노드 삽입 이름이 Mary인 노드 생성 newrec = malloc(sizeof(struct NameRec)); strcpy(newrec->name, “Mary”); Bob first John Tom Mary newrec 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (7) 리스트에 Mary 노드 삽입 (계속) 새로운 노드가 들어 갈 위치 결정 cur = first; while (strcmp(newrec->name, cur->name) > 0) { pre = cur; cur = cur->next; if (cur == NULL) break; } Bob first John Tom cur Mary newrec Bob first John Tom pre cur Bob first John Tom pre cur 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (8) 리스트에 Mary 노드 삽입 (계속) 결정된 위치에 노드 삽입 pre->next = newrec; newrec->next = cur; Mary newrec Bob first John Tom pre cur 응용컴퓨터프로그래밍

연결리스트를 이용한 삽입 정렬 (9) 전체 알고리즘 first = NULL; while (scanf(“%s”, newName) != EOF) { newrec = malloc(sizeof(struct NameRec)); strcpy(newrec->name, newName); cur = first; while (cur != NULL) { if (strcmp(newrec->name, cur->name) > 0) { pre = cur; cur = cur->next; } else break; if (cur = first) { newrec->next = first; first = newrec; } else { pre->next = newrec; newrec->next = cur; } 응용컴퓨터프로그래밍

Bob first John pre cur 응용컴퓨터프로그래밍