자료구조 16강 - 배열과 단일/이중 연결 리스트의 연산 비교

배열과 단일/이중 연결 리스트의 검색 연산 비교 

 

자료구조	검색연산
배열	선형 검색	for( int i=0 ; i<n ; i++ ){     if( arr[i] == x ) return i; }
	이진 검색	int mid = (s + e) / 2; if( x == arr[mid] ) return mid; else if( x < arr[mid] ) return bs( arr, s, mid-1, x ); else return bs( arr, mid+1, e, x )
단일 연결 리스트	선형 검색	node * curr = this; while( curr != NULL){     if( curr -> item == item ) return curr;     curr = curr -> link; }
이중 연결 리스트		for( node * curr = this ; curr != NULL ; curr = curr -> link ){     if( curr -> item == item ) return curr; }

 

배열과 단일 연결 리스트의 추가 연산 비교

 

자료구조	추가연산
배열	// 1. Find a proper position for( i = 0 ; i < n ; i++ )      if( arr[i] > x ) break; // 2. Move the items to the next positions ( j → j + 1 ) for( j = n - 1 ; j >= i ; j-- )     arr[j + 1] = arr[j]; // 3. Insert the item arr[i] = x; n++;
단일 연결 리스트	// 1. Find a proper position for( node * curr = this ; curr -> link != NULL ; curr = curr -> link )      if( curr -> link -> item > item ) break; // 2. Build a new node node * nnode = new node; nnode -> item = item; // 3. Modify the pointers nnode -> link = curr -> link; curr -> link = nnode;

 

 

배열과 단일/이중 연결 리스트의 제거 연산 비교

 

자료구조	추가연산
배열	// 1. Find a proper position for( i = 0 ; i < n ; i++ )      if( arr[i] == x ) break;     if( i == n ) return ; // 2. Move the items to the previous positions ( j ← j + 1 ) for( j = 1 ; j >= n - 1 ; j-- )     arr[j + 1] = arr[j]; n--;
단일 연결 리스트	// 1. Find a proper position for( node * curr = this ; curr -> link != NULL ; curr = curr -> link )      if( curr -> link -> item == item ) break; // 2. Modify the pointers node * nnode = curr -> link; curr -> link = dnode -> link; // 3. Free the deleted node free( dnode );