[자료구조] 연산

대부분의 자료구조의 연산에는 네 가지 기본 방법을 사용하며 읽기, 검색, 삽입, 삭제가 있다.

위 배열을 사용해서 설명해 보자.

읽기

"어떤 배열의 인덱스 2의 값을 찾아주세요."라는 질문에 train을 반환하는 연산이다.

별다른 과정이 없이 한 단계만에 인덱스 값(2)을 주면 값(train)을 반환한다.

가장 빠른 연산 유형이다.

 

검색

"train"의 인덱스를 찾아주세요." 라는 질문에 2를 반환하는 연산이다.

가장 기본적인 방식의 검색(선형검색)을 하면

1. 0번 인덱스를 확인하고 train인지 확인한다. 아니므로 1번 인덱스로 이동

2. 1번 인덱스를 확인하고 train인지 확인한다. 아니므로 2번 인덱스로 이동

3. 2번 인덱스를 확인하고 train인지 확인한다. 맞으므로 2를 반환한다.

이처럼 위의 배열에서만 3단계가 필요하다.

만약, train이 3번 인덱스에 있다면 4단계가 필요하다.

즉, 가장 기본적인 방식의 검색에서는 n의 크기 배열에서는 최대 n단계 검색과정이 필요함을 알 수 있다.

검색 연산

 

삽입

""abc"를 x위치에 넣어주세요"라는 명령을 하는 연산이다.

마지막에 집어넣으면 한 단계만에 집어넣을 수 있다.

하지만 첫 번째나 중간에 집어넣는다면 말이 달라진다.

"abc"를 인덱스 2에 넣고 싶다고 가정하자. 그러면 다음 단계를 거친다.

1. bca를 인덱스 4로 옮긴다.

2. train을 인덱스 3으로 옮긴다.

3. abc를 인덱스 2로 넣는다.

이처럼 위의 배열에서 3단계가 필요하다.

만약, abc1번 인덱스에 넣는다면 5단계가 필요하다.

즉, 삽입은 n의 크기 배열에서는 최대 n+1단계 삽입과정이 필요함을 알 수 있다.

삽입 연산

삭제

"x인덱스에 값을 삭제하라는"라는 명령을 하는 연산이다.

마지막을 삭제하면 한 단계만에 삭제할 수 있다.

하지만 첫 번째나 중간에 집어넣는다면 말이 달라진다.

인덱스 2를 삭제한다고 가정하자. 그러면 다음 단계를 거친다.

1. 인덱스 2 값인 abc를 지운다.

2. train을 인덱스 2로 옮긴다.

3. bca를 인덱스 3으로 옮긴다.

이처럼 위의 배열에서 3단계가 필요하다.

만약, 0번 인덱스를 지운다면 5단계가 필요하다.

즉, 삭제는 n의 크기 배열에서는 최대 n단계 삭제과정이 필요함을 알 수 있다.

삭제 연산