순차 자료구조 방식

1. 순차 자료구조 특징

장점

• 인덱스를 사용하여 특정 원소를 쉽게 액세스 

단점

• 원소를 삽입하거나 삭제할 경우 원소들을 뒤로 밀어내거나 앞으로 당겨서 추가적인 오버헤드 발생
• 삽입, 삭제 연산이 많은 문제는 비효율

 

2. 선형 리스트

선형 리스트란?

• 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트를 선형 리스트(Linear list) 또는 순서 리스트(Ordered List)라고 한다.

라면 종류		IT회사
1	신라면	1	네이버
2	안성탕면	2	카카오
3	진라면	3	구글
4	짜파게티	4	페이스북

 

선형리스트 특징

• 원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조로 되어있다.
• 선형리스트에서의 원소삽입 특징의 예시

상황:

인덱스가 8까지 있는 선형리스트, 이미 값이 있는 인덱스 3번 자리에 값을 삽입하려 함

발생과정:

인덱스 3번부터 7번까지 값을 각각 한 칸씩 뒤로 이동시킨다. -> 3번 자리에 값을 삽입한다.

총 이동 횟수: 5번

 

• 선형 리스트에서의 원소 삭제의 예시

상황:

인덱스가 8까지 있고 인덱스마다 값이 모두 있음. 선형리스트, 인덱스 3번 자리에 값을 삭제

발생과정:

인덱스 3번 값을 삭제 -> 인덱스 4번부터 8번까지 값을 앞으로 한 칸씩 이동시킨다.

총 이동 횟수: 5번

 

출처: Beginnersbook

 

 

3. 선형 리스트의 구현

-1차원 배열의 순차 표현

분기별 강수량

분기	1	2	3	4
강수량	30	21	45	59

int rain[] = new int[] {30, 21, 45, 59};

 

-2차원 배열의 순차 표현

2019년~2021년 분기별 강수량

년 / 분기	1	2	3	4
2019년	30	21	45	59
2020년	59	49	40	50

 

@Test
public void rain() {
	int rain[][] = new int[][] {{30, 21, 45, 59}, {59, 49, 40, 50}};
    
    Assertions.assertThat(rain[1][3]).isEqualTo(50);
}

 

-3차원 배열의 순차 표현

한국과 미국의 2019년~2020년 분기별 강수량

한국
년 / 분기	1	2	3	4
2019년	30	21	45	59
2020년	59	49	40	50

미국
년 / 분기	1	2	3	4
2019년	23	21	21	23
2020년	11	13	15	17

@Test
public void rain() {
	int rain[][][] = new int[][][] {{{30, 21, 45, 59}, {59, 49, 40, 50}}, {{30, 21, 45, 59}, {59, 49, 40, 50}}};
    
    Assertions.assertThat(rain[0][1][2]).isEqualTo(40);
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음