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

배열리스트 

1. 배열 리스트의 객체 구조 

[그림 5-5]에서 위쪽은 배열을 보는 물리적 관점이고, 아래쪽은 리스트를 보는 추상적 관점이다.  배열 item[0...] 에 원소들이 들어가 있다. ADT리스트 관점은 하부 구조를 특정하지 않는다. ADT에서 리스트는 원소를 리스트의 0번째 원소, 6번째 원소, 마지막 원소와 같이 추상적으로 본다. 배열을 이용해 리스트를 구현한다는 것은 이 추상적 관점을 물리적 배열에 대응시켜 주는 것이다. 예를 들어, 리스트의 0번째 원소를 배열의 item[0]에 대응시킨다. 마찬가지로 리스트 i번째 원소는 배열의 item[i]에 대응된다.

 

 

그림 5-5 물리적 배열과 리스트의 추상적 관점

 

그림 5-6 배열 방향을 역순으로 해석한 물리적 배열과 리스트의 추상적 관점

 

 

추상적 관점을 물리적으로 대응시킬 때 [그림 5-6]과 같이 배열을 역순으로 해석할 수도 있다. 배열로 구현한 리스트에 원소를 삽입하거나 삭제할 때 원소들은 오른쪽이다 왼쪽으로 시프트하는데, [그림 5-6]에서 리스트 순서를 반대로 해석하기 때문에 시프트 방향이 [그림 5-5]와 정반대가 된다. 이 절에서는 [그림 5-5]의 관점을 따른다.

 

 

그림 5-7 배열 리스트 객체 구조

 

 

이제 배열의 리스트를 설계할 준비가 외었다. [그림  5 -7]은 배열 리스트의 객체 구조를 나타낸 것이다. 임의의 리스트 객체에는 2개의 필드, 즉 원소들이 저장되는 배열 item[ ] 필드와 원소의 총 수를 저장하는 numItems필드가 있다. 그리고 이전 게시물에서  ADT 리스트에서 정의한 핵심 작업 6개에 4개를 더 추가했다. (ADT를 처음부터 이 10개의 집합으로 정의해도 좋다.) ADT 리스트를 좀더 구체화하여 리스트 객체의 필드와 지원하는 작업을 같이 나열하였다. 그림에서 박스 안에 그린 배열 item[ ]과 변수 numItems는 박스 내부에서만 사용되는 필드라는 뜻이다. 즉, 두 필드는이 객체 내부에서만 사용되며 바깥에서는 접근할 필요가 없다. 박스 안팎으로 열려 있는 메서드 들은 객체 깥에서 접근할 수 있다는 뜻이다.

 

오픈 소스로 제공되는 배열 기반 리스트들은 이보다 더 다양한 작업을 지원하지만 여기서는 리스트의 핵심을 파악하기 충분한 정도로 선택하였다. 여기서 리스트의 i번째 원소로 삽입하는 작업과 리스트의 맨 뒤에 원소를 추가하는 작업은 하나로 합칠 수도 있지만 따로 분리했다, 그 이유는 알고리즘을 설명할 때 함께 설명한다.

 

[그림 5-7]에서 각 필드와 작업의 의미는 위와 같다.

 

 

2. 배열 리스트의 작업

원소 삽입

리스트에서는 보통 규칙 없이 저장되므로 원소를 삽입할려면 어디에 넣을지에 관한 정보도 함께 주어져야 한다.

 

[그림 5-8] 77을 리스트의 3번째 원소로 삽입하는 예다. 리스트에 원소가 총 9개 저장되어 있으므로 numItems 값이 9다. 원소들은 배열 item[0...8]에 저장되어 있다. 리스트의 3번째 자리는  item[3]이므로 item[3...8]을 오른쪽으로 한 칸씩 시프트해서 item[3]에 빈 공간을 만든 다음 77을 넣는다.

 

 

알고리즘 5-1   배열 리스트의 k번째 자리에 원소 x삽입하기

void add(int k, T x){
    if(numItems >= item.length || k < 0 || k > numItems)
    	/* 에러 처리 */ 
        // ◀ 배열 용량 초과 또는 부적절한 인덱스   
    else{
    	1️⃣for(int i = k; i < item.length; i++)
        	item[i+1] = item[i]; // ◀ 오른쪽으로 시프트
            
            item[k] = x;
            numItems++;
     }
}

 

리스트의 k번째 원소로 x를 삽입하려면 item[k..numItems-1]구간의 원소들을 오른쪽으로 한 칸씩 시프트하고 item[k] 원소 x를 넣는다. 리스트의 원소가 하나 늘었으므로 numItems값을 1 증가시킨다. [알고리즘 5-1]은 이 이를 알고리즘으로 표현한 것이다.

그림 5 - 9 리스트의 맨 앞에 원소(77)를 삽입하는 예

 

시프트가 가장 번거로운 삽입은 맨 앞, 즉 k = 0 자리에 원소를 삽입하는 add(0, x)이다. 이 때는 모든 원소를 시프트해야한다. [그림 5- 9]는 맨 앞에 원소 77을 삽입하는 예다. 삽입 전 리스트에 있던 원소 9개가 모두 시프트 되었다.

 

그림 5 -10 리스트의 맨 뒤에 원소를 삽입하는 예

 

리스트의 맨 뒤에 원소를 삽입하는 작업이 가장 단순한다. 시프트할 필요 없이 리스트의 끝바로 다음에 원소를 저장하면 된다. [그림 5-10]은 맨 뒤에 원소를 추가하는 작업의 예다. 시프트 없이 단순히 맨 끝에 원소를 추가했다.

 

 

알고리즘 5-2   배열 리스트의 맨 뒤에 원소 추가하기

void append(T x){
    if(numItems >= item.length)
    	/* 에러 처리 */  // ◀ 방어적 프로그래밍
    else{
    	item[numItems] = x;
        numsItems++;
      }
}

 

[알고리즘 5-2]는 리스트의 맨 뒤에 원소를 추가하는 알고리즘이다. 리스트의 맨 뒤에 원소를 추가하는 작업을 할 때는 add(numitems, x)를 호출해도 된다. 다만, 리스트 끝에 원소를 덧붙이는 작업은 아주 흔해서 대개 위 알고리즘 처럼 메서드를 따로 제공한다. 비슷하게 리스트의 맨 앞에 원소를 삽입하는 작업도 흔하여 따로 메서드가 제공되기도 하는 데 여기서는 그냥 add(0, x)를 사용한다.

 

 

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

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