2.2.1 리스트, 배열로 구현한 리스트

2.2 리스트 (배열 리스트, 연결 리스트)

- 개념 : 리스트란 순서를 가지고 일렬로 나열한 데이터들의 모임이다. 

          (순서를 가지고 있다는 점에서 집합과 구분된다.)

- 예시 : 한 주일의 요일 리스트 : (일, 월, .. 토요일), 한글 자음 리스트 (ㄱ, ㄴ, …ㅎ)

2.2.1 배열로 구현한 리스트 (개념, 장점, 단점, 삽입, 삭제)

- 개념 : 메모리안에 순차적으로 공간이 할당되는 배열을 이용한 방법으로,  배열 인덱스 번호를 이용해 

          데이터에 접근한다.

 

 

- 장, 단점

장점	단점
인덱스를 이용하여 원하는 데이터요소를  빠르게 찾을 수 있다. ( O(1) )	1) 자료의 삽입과 삭제가 비효율 적이다. (삽입과 삭제시 모든 요소를 이동 시켜야 한다. O(N) )   삽입) 배열에 ABCDE가 저장되어 있고, B 다음에 N을 삽입하려면C,D,E를 한 칸씩 이동해야 한다.   삭제) 배열에 ABCDE가 있고, C를 삭제 하려면, C를 삭제하고 작업을 완료할 수 있지만, 그러면 배열에는 처리되지 않아야 할 정보(Null)가 포함되므로 이를 없애 주어야 한다. 그렇기 때문에 C를 삭제하고 D,E를 한 칸씩 앞으로 이동해야 한다.
구현이 간단하다.	2) 한번 선언된 배열은 크기를 늘리거나 줄일 수 없다. (배열을 사용할 때 크기가 고정이므로 사용할 데이터 양을 예측하여 배열을 선언하기 때문에 메모리 공간이 낭비되는 경우가 많다.) 10개 상자가 있는데 저장할 물건이 5개면 5개 상자 낭비된다. 또는 저장할 물건이 15개면 초과하는 5개 물건은 저장할 수 없다.

 

- 1차원 배열을 이용하여 리스트 구현 (초기화, 삽입, 삭제)

  (1) 주요 변수

    1) list : 배열 이름

    2) element : 배열에 저장되는 데이터형을 사용자 정의 형으로 나타냄 

                    (int로 해도 무관하지만, 차후 데이터형의 변경을 쉽게하기 위해서 정의)

    3) ArrayListType : 1차원 배열 list와 length를 구조체로 묶은 것, 리스트의 모든 함수에 

                           이 구조체 포인터가 매개변수로 전달된다.

                           (이런 식으로 사용하면, 전역변수를 사용하지 않아도 되는 장점이 있다. )

    * 참고 : C언어의 오류를 줄이는 대표적인 방법으로는 전역변수를 사용하지 않는 것이 

               1가지 방법이다.

 

 

  (2) 주요 함수

    1) init() : 배열 리스트를 초기화하는 함수로 length를 0으로 만든다.

    2) is_empty() : 배열 리스트가 비어있는지 검사하는 함수이다.

 

 

 

 

3) is_full() : 배열 리스트가 가득 찼는지 검사하는 함수로 length 값이 MAX_LIST_SIZE보다 크면 1을 반환, 

               그렇지 않으면 0을 반환한다.

 

4) display() : 배열의 요소들을 한 줄에 하나씩 출력 한다.

 

 

 

5) add() : 배열 리스트에 데이터를 삽입하는 함수이다.

먼저 배열이 가득 차지 않았나 검사하고 삽입 위치가 적합한 범위인지 검사 후 삽입한다.

                                                 

    

 

  

6) delete() : 배열 리스트에 데이터를 삭제하는 함수이다.

            먼저 자료를 삭제한 후에 삭제 위치부터 맨 끝까지의 자료를 한 칸씩 앞으로 옮긴다.