JAVA 자료구조 (리스트) - 배열리스트 2

배열 리스트 2

2. 배열 리스트의 작업

원소 삭제

리스트에서 원소를 삭제할 때는 특정 위치의 원소를 삭제하게 할 수도 있고, 특정 원소를 삭제하게 할 수도 있다. 

그림 5 - 11 리스트의 3번째 원소를 삭제하는 예

 

[그림 5-11]은 리스트의 3번째 원소를 삭제하는 예다. 리스트에 총 9개의 원소가 저장되어 있어 변수 numItems 값은 9인 상태다. 3번째 원소인 17을 삭제하고 4~8번째 원소들을 왼쪽으로 시프트 한다.

 

 

알고리즘 5-3 배열 리스트의 k번째 원소 삭제하기

void remove(int k){
    if(isEmpty() || k < 0 || k > numItems-1)
      /* 에러처리  */
    else{
      for(int i = k; i < numItems-2l i++ 
        item[i] = item[i+1]; // ◀ 왼쪽으로 시프트
      
      numItems--;
      }
        
}

 

[알고리즘 5-3]리스트의 k번째 원소를 삭제하는 알고리즘이다. 삭제된 원소의 다음 원소부터 맨 마지막 원소까지 모두 왼쪽으로 시프트하고 numItens 값을 1 감소시킨다. 삽입에서 오른쪽으로 시프트 할때와는 반대로 왼쪽으로 시프트를 할때는 왼쪽에서 오른쪽으로 진행한다.(index의 번호가 작은 것부터 value를 변경)

 

 

⭐알고리즘 5-4   배열 리스트에서 원소 x 삭제하기

public boolean removeItem(T x){
	
    k = 0;
    while(k < numItems && item[k] != x){ //◀ 원소 x 찾기
    	k ++;
      }
    // k는 numItem 보다 작을 때 까지 이므로 
    //item에 x와 일치하는 값이 없으면
    // k가 numItems와 동일해지는 순간 while문이 종료된다.
    
    if(k == numItems) return false;  // ◀ 원소 없음
    else{
    	for(int i = k; i < numItems-2; i ++) // ◀ 원소 삭제
        	item[i] = item[i + 1];       // ◀ 왼쪽으로 시프트
        
        numItems--;
        return true;
      } 
    
}

 

[그림 5-11]은 특정 위치를 파라미터롤 받고 해당 위치의 원소를 삭제하는 예인데 리스트에서는 특정 원소를 파라미터 값으로 받아 해당 값을 찾아 삭제 해야 하는 경우도 많다. [알고리즘 5-4]는 리스트에서 원소 x를 찾아 삭제하는 알고리즘이다. 

 

삭제하고자 하는 원소가 x가 존재하지 않으면 에러 처리를 할 수도 있는데, 여기서는 false를 리턴해서 호출한 프로그램이 알아서 하도록 하였다. 특정 위치의 원소를 삭제할 때와 마찬가지로 삭제된 원소의 다음 원소부터 맨 마지막 원소까지 모두 외쪽으로 시프트 하고 numItems 값을 1감소 시킨다. 다만, 원소를 찾는 과정이 추가되었다.

 

 

기타작업

 

알고리즘 5-5 배열 리스트의 i번째 원소 알려주기

public T get(int i){
    if(i >= 0 && i <= numItens-1)
    	return item[i]
    else
    	return OUT_OF_BOUND
}

 

먼저 리스트의 i번째 원소를 알려주는 작업 get()의 핵심은 return item[i]인데 범위를 벗어난 원소를 요구할 경우 까지 감안하면 [알고리즘 5-5]와 같다.

 

 

알고리즘 5-6 배열 리스트의 i번째 원소를 x로 대체하기 

public T set(int i, T x){
    if(i >= 0 && i <= numItems-1)
    	item[i] = x;
    else
    	/* 에러 처리 */
}

 

리스트의 i번째 원소를 원소 x로 대체하는 작업 set(i, x)의 핵심은 item[i] = x 인데 범위를 벗어난 원소를 요구할 경우까지 감안하면 [알고리즘 5-6]과 같다.

 

알고리즘 5-7 원소x가 배열리스트의 몇 번째 원소인지 알려주기

public int indexOf(int x){
    
    i =0;
    while(i < numItems %% item[i] !=x)
      i++;
      
   if(i ==numItems)
     return NOT_FOUND
   else
     return i;  // ◀ x = item[i]는 i번째 원소
}

 

 

원소 x가 리스트의 몇 번째 원소인지 알아내는 작업은 [알고리즘 5-7]과 같다. 원소 x가 리스트에 없으면 상수NOT_FOUND를 리턴한다. 리스트가 원소 x를 포함하는지 체크하는 작업(예: contains(x))은 따로 만들지 않았다. indexOf(x) 함수에서 0에서 numItem-1 사이의 인덱스를 리턴하면 x를 포함하고 NOT_FOUND를 리턴하면 포함하지 않는 것이다.

 

알고리즘 5-8 기타작업들

// 리스트의 총 원소 수 알려주기
public int len(){
    return numItems
}

// 리스트가 비었는지 알려주기
public boolean isEmpty(){
	if(numItems == 0)
        return true;
    else
    	return false;
}

//리스트 깨끗이 청소하기
public void clear(){
	numItems = 0;
}

 

리스트의 총 원소 수를 알려주는 len()은 변수 numItems 값을 리턴하면 된다. 리스트가 비었는지 알려주는 isEmpty()는 Items 값이 0인지 여부를 리턴하면 된다. 리스트를 깨끗이 청소하는 clear()는 numItems 값을 리셋하면 된다.

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바