Chapter 5. General Linear List [INA240] Data Structures and Practice Youn-Hee Han http://link.kut.ac.kr

0. Concept Linear List Linear List Categories In a linear list, each element has a unique successor Linear List Categories Element 1 Element 1 Element 1 Element 1 Linear List Restricted General Chapter 5 Stack Chapter 3 Queue Chapter 4 Data Structure

0. Concept General List 일상 생활에서의 예 a list in which operations, such as retrievals, insertions, changes, and deletions, can be done anywhere in the list 목록 또는 도표를 추상화 한 것 일상 생활에서의 예 Lists of employees Student lists Lists of our favorite songs Position Name Quantity 1 Beer 10 2 Gum 5 3 Apple 4 Potato 8 Onion ... Data Structure

0. Concept 필요한 연산은? Position-oriented List (위치 기반 리스트) 에서의 연산 정의 예 주 연산: insertion, deletion, retrieval, traversal 보조 연산: … 그렇다면, insertion에 대해서 다음 중 어떤 것을 제공해야 하는가? 사용자는 어떤 것을 더 원하는가? 둘 다 원하는가? insert (data): Ordered List insert (position, data): Position-oriented List Position-oriented List (위치 기반 리스트) 에서의 연산 정의 예 insert(position, data) 데이터를 주어진 위치(position)에 넣기 delete(position) 주어진 위치(position)의 데이터를 삭제 retrieve(position, &data) 주어진 위치(position)의 데이터를 Data 변수에 복사 traversal 리스트 안에 모든 Element에 대해 순서대로 일정한 작업 (예를 들어 단순 방문) 을 행한다. position name quantity 1 Beer 10 2 Gum 5 3 Apple 4 ... Data Structure

0. Concept Ordered List (순서 리스트) 에서의 연산 정의 예 Sequence Rule 이 존재 예를 들어 주민번호 (SSN) 오름차순, 학번 내림차순, 이름 오름차순 … insert(data) 주어진 데이터를 정해진 Rule 에 따라 알맞은 위치에 넣기 delete(data) 주어진 데이터를 리스트에서 찾아 삭제 retrieve(data1, &data2) 주어진 데이터가 리스트에 있는지 검색 data1과 연관된 데이터를 얻어옴 traversal 리스트 안에 모든 Element에 대해 순서대로 일정한 작업 (예를 들어 단순 방문) 을 행한다. 교재에서는 Ordered List를 가정하여 코딩을 제시한다. Name Grade Cho A Kim B+ Lee C+ ... Data Structure

1. Basic Operations Insertion Deletion In ordered list: maintained in sequence according to data Key: one or more field that identifies the data (ex: SSN) Deletion Deletion requires search to locate the data to delete Data Structure

1. Basic Operations Retrieval Traversal provides a data without changing list Search: finding an element in a list by some key Traversal process of visiting each element in a list in sequence to do something Ex) print all elements in a list Requires looping for all elements Data Structure

3. List ADT Generic Coding for List Node Data (including key) + pointer to next node Stack과 Queue에서의 Node 정의도 이와 같은 Generic 방법을 사용하고 있음 typedef struct node { void* dataPtr; struct node* link; } NODE; data Generic coding Note] Heap memory for actual data should be allocated by using malloc() Data Structure

3. List ADT Generic Coding for List Head Data (including key) + pointer to next node In our List ADT, data are stored in key sequence How to arrange the elements in ordered mode Solution  compare function How to handle different types of parameters Each type of data requires different functions to compare two data (keys) Solution  function pointer of compare function Application programmer writes a function to compare two data (keys) typedef struct { int count; NODE* pos; // 현재 가리키는 노드 NODE* head; // 첫번재 노드 NODE* rear; // 마지막 노드 int (*compare) (void* argu1, void* argu2); } LIST; Data Structure

3. List ADT Generic Coding for List Head int (*compare) (void* argu1, void* argu2); 본 교재에서는 다음과 같이 return 값이 정해짐 Case I) argu1 의 데이터 > argu2 의 데이터  양수가 리턴됨 Case II) argu1 의 데이터 < argu2 의 데이터  음수가 리턴됨 Case III) argu1 의 데이터 == argu2 의 데이터  0 이 리턴됨 Examples int compareInt(void *argu1, void *argu2) { return *(int*)argu1 - *(int*)argu2; } int compareStr(void *argu1, void *argu2) { return strcmp((char*)argu1, (char*)argu2); } Data Structure

3. Queue ADT 간단한 List ADT Test 프로그램 교재에 없는 내용 (list_test.c) #include <stdio.h> #include <stdlib.h> #include "stdbool.h" #include "list.h" int compareInt(void *argu1, void *argu2); int main (void) { int done = false; int* dataPtr; LIST* list; list = createList(compareInt); while (!done) { dataPtr = (int*)malloc(sizeof(int)); printf ("Enter a number: <EOF> to stop: "); if ((scanf ("%d" , dataPtr)) == EOF || fullList(list)) done = true; else addNode(list, dataPtr); } Data Structure

3. Queue ADT 간단한 List ADT Test 프로그램 교재에 없는 내용 (list_test.c) printf ("\n\nThe Ordered list of numbers:\n"); while (!emptyList(list)) { removeFirst(list, &dataPtr); printf ("%3d\n", *dataPtr); free (dataPtr); } destroyList(list); return 0; int compareInt(void *argu1, void *argu2) { return *(int*)argu1 - *(int*)argu2; Enter a number: <EOF> to stop: 3 Enter a number: <EOF> to stop: 9 Enter a number: <EOF> to stop: 7 Enter a number: <EOF> to stop: 1 Enter a number: <EOF> to stop: <CTRL-Z> The ordered list of numbers: 1 3 7 9 Data Structure

3. List ADT Header file with List ADT Prototypes #include "stdbool.h" File Name: list.h (이후 모든 ADT 구현은 이 한 파일에 추가) #include "stdbool.h" typedef struct node { void* dataPtr; struct node* link; } NODE; typedef struct { int count; NODE* pos; NODE* head; NODE* rear; int (*compare) (void* argu1, void* argu2); } LIST; LIST* createList (int (*compare) (void* argu1, void* argu2)); LIST* destroyList (LIST* list); stdbool.h #ifndef _STDBOOL_H #define _STDBOOL_H typedef int _Bool; #define bool _Bool #define true 1 #define false 0 #define __bool_true_false_are_defined 1 #endif Data Structure

3. List ADT Header file with List ADT Prototypes int addNode (LIST* pList, void* dataInPtr); bool removeNode (LIST* pList, void* keyPtr, void** dataOutPtr); bool removeFirst (LIST* pList, void** dataOutPtr) // 교재에 없음 bool searchList (LIST* pList, void* pArgu, void** pDataOut); bool retrieveNode (LIST* pList, void* pArgu, void** dataOutPtr); bool traverse (LIST* pList, int fromWhere, void** dataOutPtr); int listCount (LIST* pList); bool emptyList (LIST* pList); bool fullList (LIST* pList); static int _insert (LIST* pList, NODE* pPre, void* dataInPtr); static void _delete (LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr); static bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu); 함수에 붙은 static: Private Function 의미.자신이 정의되는 파일내에서만 호출 가능 Data Structure

3. List ADT List ADT functions List ADT 사용자는 main 함수를 작성시에 반드시 compare 함수도 작성해야 한다. List ADT functions removeFirst Data Structure

3. List ADT createList The parameter: the compare function required to compare two data (keys) LIST* createList (int (*compare) (void* argu1, void* argu2)) { LIST* list; list = (LIST*) malloc (sizeof (LIST)); if (list) { list->head = NULL; list->pos = NULL; // working pointer for list traversal list->rear = NULL; list->count = 0; list->compare = compare; } return list; main() 함수에서… list = createList (cmpYear); Data Structure

3. List ADT addNode 1. 노드가 추가될 위치를 찾는다  preceding node에 대한 포인터를 얻는다. 결과 값 0: 성공적으로 노드 삽입 1: 추가하려는 노드가 이미 존재 -1: 삽입 실패 Inserting 52 Inserting 55 Data Structure

3. List ADT addNode 1. 노드가 추가될 위치를 찾는다  preceding node에 대한 포인터를 얻는다. int addNode (LIST* pList, void* dataInPtr) { bool found; bool success; NODE* pPre; NODE* pLoc; found = _search (pList, &pPre, &pLoc, dataInPtr); if (found) return (+1); success = _insert (pList, pPre, dataInPtr); if (!success) return (-1); return (0); } Inserting 55 pPre: dataInPtr을 포함하는 NODE가 삽입되어야 할 위치 바로 직전의 NODE를 가리키는 포인터 pLoc: dataInPtr과 같은 값을 지니는 NODE가 list 내에 존재할 때 그 NODE를 가리키는 포인터 Data Structure

3. List ADT _search It is internal function Two Macros target  dataInPtr Two Macros #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) Data Structure

3. List ADT _search Two Macros bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; … if ( COMPARE_LAST > 0) { } while ( (result = COMPARE) > 0 ) { Data Structure

3. List ADT _search Case (a) – 1 : 찾는 노드가 리스트의 첫 번째 노드일 때 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 음수 pList [TABLE 5-1] Target=first node pPre=NULL pLoc=First node Return is True Data Structure

3. List ADT _search Case (a) – 2 : 찾는 노드가 리스트의 중간에 위치한 노드일 때 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 음수 양수, 양수, …, 0 [TABLE 5-1] Target=middle node pPre=Node’s predecessor pLoc=Equal node (middle node) Return is True Data Structure

3. List ADT _search Case (a) – 3 : 찾는 노드가 리스트의 마지막 노드일 때 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 음수 양수, 양수, …, 0 (마지막 노드에서) [TABLE 5-1] Target=last node pPre=Last’s predecessor pLoc=Last node Return is True Data Structure

3. List ADT _search Case (b) – 1 : 찾는 노드가 리스트의 첫번째 노드 보다 작을 때 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 음수 pList 음수 [TABLE 5-1] Target<first node pPre=NULL pLoc=First node Return is False Data Structure

3. List ADT _search Case (b) – 2 : 찾는 노드가 리스트에 존재하지 않고 그 값이 리스트 중간에 위치 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 음수 양수, 양수, …, 음수 [TABLE 5-1] First<Target<Last pPre=Largest Node (< Target) pLoc=First Node (> Target) Return is False Data Structure

3. List ADT _search Case (b) – 3 : 찾는 노드가 리스트의 마지막 노드 보다 더 클 때 bool _search (LIST* pList, NODE** pPre, NODE** pLoc, void* pArgu) { #define COMPARE ( ((* pList->compare) (pArgu, (*pLoc)->dataPtr)) ) #define COMPARE_LAST ((* pList->compare) (pArgu, pList->rear->dataPtr)) int result; *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; if ( COMPARE_LAST > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } while ( (result = COMPARE) > 0 ) { *pPre = *pLoc; *pLoc = (*pLoc)->link; if (result == 0) return true; else return false; 양수 [TABLE 5-1] Target>Last pPre=Last Node pLoc=NULL Return is False Data Structure

3. List ADT _insert Given the predecessor, there are three steps to the insertion 1. Allocate memory for the new node and move data to the node 2. Point the new node to its successor 3. Point the new node’s predecessor to the new node. Cases of Predecessor point Case I) NULL (_search 결과 *pPre 가 NULL 인 경우, Case (b) - 1 ) 1. The new node is inserted to the beginning of the list, or 2. List is empty Case II) contain the address of a node (_search 결과 *pPre 가 NULL 이 아닌 경우, Case (b) – 2,3 ) 1. The new node is inserted in the middle of the list, or 2. The new node is inserted at the end of the list Data Structure

3. List ADT _insert Case I – 1 : 삽입할 노드가 리스트의 첫번째 노드가 되어야 할 때 static bool _insert (LIST* pList, NODE* pPre, void* dataInPtr) { NODE* pNew; if (!(pNew = (NODE*) malloc(sizeof(NODE)))) return false; pNew->dataPtr = dataInPtr; pNew->link = NULL; if (pPre == NULL) { pNew->link = pList->head; // 1) pList->head = pNew; // 2) if (pList->count == 0) // 0 아님 pList->rear = pNew; } else { pNew->link = pPre->link; pPre->link = pNew; if (pNew->link == NULL) } (pList->count)++; return true; 2) 1) Data Structure

3. List ADT _insert Case I – 2 : 비어있는 리스트에 노드를 삽입할 때 static bool _insert (LIST* pList, NODE* pPre, void* dataInPtr) { NODE* pNew; if (!(pNew = (NODE*) malloc(sizeof(NODE)))) return false; pNew->dataPtr = dataInPtr; pNew->link = NULL; if (pPre == NULL) { pNew->link = pList->head; // 1) pList->head = pNew; // 2) if (pList->count == 0) pList->rear = pNew; // 3) } else { pNew->link = pPre->link; pPre->link = pNew; if (pNew->link == NULL) pList->rear = pNew; } (pList->count)++; return true; 1) 2) 3) 1 Data Structure

3. List ADT _insert Case II – 1 : 삽입할 노드가 리스트 중간에 위치 static bool _insert (LIST* pList, NODE* pPre, void* dataInPtr) { NODE* pNew; if (!(pNew = (NODE*) malloc(sizeof(NODE)))) return false; pNew->dataPtr = dataInPtr; pNew->link = NULL; if (pPre == NULL) { pNew->link = pList->head; pList->head = pNew; if (pList->count == 0) pList->rear = pNew; } else { pNew->link = pPre->link; // 1) pPre->link = pNew; // 2) if (pNew->link == NULL) // NULL아님 } (pList->count)++; return true; 2) 1) Data Structure

3. List ADT _insert Case II – 2 : 삽입할 노드가 리스트의 마지막 노드 보다 더 이후에 위치 static bool _insert (LIST* pList, NODE* pPre, void* dataInPtr) { NODE* pNew; if (!(pNew = (NODE*) malloc(sizeof(NODE)))) return false; pNew->dataPtr = dataInPtr; pNew->link = NULL; if (pPre == NULL) { pNew->link = pList->head; pList->head = pNew; if (pList->count == 0) pList->rear = pNew; } else { pNew->link = pPre->link; pPre->link = pNew; if (pNew->link == NULL) } (pList->count)++; return true; 2) rear 1) Data Structure

3. List ADT removeNode pPre: _search() 호출 결과 삭제하고자 하는 노드의 바로 이전 노드의 포인터 pLoc: _search() 호출 결과 삭제하고자 하는 노드의 포인터 bool removeNode (LIST* pList, void* keyPtr, void** dataOutPtr) { bool found; NODE* pPre; NODE* pLoc; found = _search(pList, &pPre, &pLoc, keyPtr); if (found) _delete(pList, pPre, pLoc, dataOutPtr); return found; } 삭제하고자 하는 노드의 데이터값 _delete() 이후에 삭제된 노드의 데이터 값이 할당됨 Data Structure

3. List ADT _delete Case I) pPre가 NULL인 경우 1. 삭제하고자 하는 노드가 첫 번째 노드임 void _delete (LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr) { *dataOutPtr = pLoc->dataPtr; if (pPre == NULL) pList->head = pLoc->link; else pPre->link = pLoc->link; if (pLoc->link == NULL) pList->rear = pPre; (pList->count)--; free (pLoc); return; } Data Structure

3. List ADT _delete Case I) pPre가 NULL인 경우 2. 삭제하고자 하는 노드가 첫 번째 노드이고 그 첫번째 노드가 유일한 노드 void _delete (LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr) { *dataOutPtr = pLoc->dataPtr; if (pPre == NULL) pList->head = pLoc->link; else pPre->link = pLoc->link; if (pLoc->link == NULL) pList->rear = pPre; // NULL (pList->count)--; free (pLoc); return; } 1 rear Data Structure

3. List ADT _delete Case II) pPre가 NULL이 아닌 경우 1. 삭제하고자 하는 노드가 중간 노드인 경우 void _delete (LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr) { *dataOutPtr = pLoc->dataPtr; if (pPre == NULL) pList->head = pLoc->link; else pPre->link = pLoc->link; if (pLoc->link == NULL) pList->rear = pPre; (pList->count)--; free (pLoc); return; } Data Structure

3. List ADT _delete Case II) pPre가 NULL이 아닌 경우 2. 삭제하고자 하는 노드가 마지막 노드인 경우 void _delete (LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr) { *dataOutPtr = pLoc->dataPtr; if (pPre == NULL) pList->head = pLoc->link; else pPre->link = pLoc->link; if (pLoc->link == NULL) pList->rear = pPre; (pList->count)--; free (pLoc); return; } 2 1 rear Data Structure

3. List ADT removeFirst (교재에는 없음) 가장 첫번째 노드를 삭제하면서 데이터를 가져온다. bool removeFirst (LIST* pList, void** dataOutPtr) { bool found; if (emptyList(pList)) { found = false; } else { NODE* pLoc; pLoc = pList->head; *dataOutPtr = pLoc->dataPtr; pList->head = pList->head->link; free(pLoc); pList->count--; found = true; } return found; Data Structure

3. List ADT searchList bool searchList (LIST* pList, void* pArgu, void** pDataOut) { bool found; NODE* pPre; NODE* pLoc; found = _search (pList, &pPre, &pLoc, pArgu); if (found) *pDataOut = pLoc->dataPtr; else *pDataOut = NULL; return found; } 검색하고자 하는 노드의 데이터값 _search() 이후에 검색된 노드의 데이터 값이 할당됨 Data Structure

3. List ADT emptyList fullList listCount bool emptyList (LIST* pList) { return (pList->count == 0); } bool fullList (LIST* pList) { NODE* temp; if ((temp = (NODE*)malloc(sizeof(*(pList->head))))) { free (temp); return false; } return true; int listCount(LIST* pList) { return pList->count; } Data Structure

3. List ADT traverseList fromWhere: 0 ~ start position at the first element bool traverse (LIST* pList, int fromWhere, void** dataPtrOut) { if (pList->count == 0) return false; if (fromWhere == 0) { pList->pos = pList->head; *dataPtrOut = pList->pos->dataPtr; return true; } else { if (pList->pos->link == NULL) else { pList->pos = pList->pos->link; } traverse() 함수는 한번 불리워질 때마다 현재 리턴하는 값을 지닌 노드 포인터를 pList->pos에 저장을 해 둔다. 그래서, 다음 번 traverse()를 부를 때에는 이미 pList->pos는 바로 직전에 traverse() 호출 결과에 대한 노드 포인터를 가지고 있다. 즉, traverse() 함수는 main()에서 for나 while 루프 속에서 사용하여 전체 노드의 값들을 가져올 때 유용하게 사용할 수 있다. Data Structure

3. List ADT traverseList int traverseList(List *pList, int fromWhere, void** dataPtrOut); pList: an ordered list fromWhere: if fromWhere == 0 pList->pos = pList->head (pos 포인터의 초기화) return first data dataPtrOut: an address to receive the next data Return value: TRUE if next node exists, otherwise, FALSE Usecase) Printing all data using traverseList operation int n = 0; // current index int* data; bool ret; do { ret = traverseList(pList, n++, (void**)&data); if(ret) printf("%d ", *data); } while(ret); Data Structure

3. List ADT destroyList LIST* destroyList (LIST* pList) { NODE* deletePtr; if (pList) { while (pList->count > 0) { free (pList->head->dataPtr); deletePtr = pList->head; pList->head = pList->head->link; pList->count--; free (deletePtr); } free (pList); return NULL; Data Structure

3. List ADT _search 함수 내에서 pHead = pHead->link 와 같은 코딩을 사용하면 어떨까? PP. 249 연습문제 1 _search 함수 내에서 pHead = pHead->link 와 같은 코딩을 사용하면 어떨까? 왜 pPre와 pLoc을 별도로 사용할까? Data Structure