[자료구조] 선형리스트

1. 선형리스트의 개념

1) 리스트

• 자료의 목록
• 배열

2) 선형리스트

• 순서 리스트(Ordered List)
• 자료 간에 순서를 갖는 리스트

(1) 선형리스트 예

 - 요일

 

일

월

화

수

목

금

토

 

 - 요리 분야 (순서가 없지만, 선형리스트 일부분이다.)

 

한정식

중식

일식

분식

양식

 

3) 리스트의 표현 방식

• 리스트 이름 = (원소1, 원소2, 원소n)
• 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 됨

4) 선형 리스트의 저장

• 원소들의 논리적 순서와 같은 순서로 메모리에 저장

5) 선형 리스트에서의 원소 삽입

• 선형리스트 중간에 원소가 삽입되면 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킨다.

(1) 원소 삽입 방법

• 원소를 삽입할 빈자리 만든다.
   - 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 자리 이동시킨다.
• 준비한 빈자리에 원소 삽입

 - 위 방법을 통해 20과 40 사이에 원소를 삽입하는 것을 간단하게 도식화하였다.

 

10	20	40	50	60
10	20		40	50	60
10	20	30	40	50	60

 

6) 선형 리스트에서의 원소 삭제

• 선형리스트 중간에서 원소가 삭제되면 그 이후의 원소들은 한 자리씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킨다.

(1) 원소 삭제 방법

• 원소 삭제하기
   - 삭제한 빈자리를 채운다.
• 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 자리 이동시킨다.

 - 위 방법을 통해 30을 삭제한다.

 

10	20	30	40	50	60
10	20		40	50	60
10	20	40	50	60

 

 

2. 1차원 배열을 이용한 선형 리스트의 구현

1) 논리적 구조

국어	영어	수학	과학
90	100	99	94

2) 코드화

#include <stdio.h>

void main(){
	int i, score[4] = {90, 100, 99, 94};
	for(i = 0; i < 4; i++){
		printf("En_Geon 점수 %d : %d \n", i + 1, score[i]);
	}
    return 0;
}

 

3. 2차원 배열을 이용한 선형 리스트의 구현

1) 논리적 구조

	국어	영어	수학	과학
1	90	100	99	94
2	88	90	89	91

2) 물리적 구조

• 행 우선 순서 방법(row major order)
• 2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 사용하는 방법

90	[0][0]
100	[0][1]
99	[0][2]
94	[0][3]
88	[1][0]
90	[1][1]
89	[1][2]
91	[1][3]

3) 코드화

#include <stdio.h>

void main(){
	int i, j, score[2][4] = {{90, 100, 99, 94}, {88, 90, 89, 91}};
	for(i = 0; i < 2; i++){
		printf("%d번 성적\n", i + 1);
		for(j = 0; j < 4; j++){
			printf(" 점수 %d : %d\n", j + 1, score[i][j]);
		}
	}
    return 0;
}

 

4. 3차원 배열을 이용한 선형 리스트의 구현

3차원 배열에서는 면, 행, 열을 사용한다.

1) 논리적 구조

1반	국어	영어	수학	과학
1	90	100	99	94
2	88	90	89	91

 

2반	국어	영어	수학	과학
1	85	90	80	75
2	70	79	60	61

3) 코드화

#include <stdio.h>

void main(){
	int i, j, k, score[2][2][4] = {
    	{{90, 100, 99, 94}, {88, 90, 89, 91}},
        {{85, 90, 80, 75}, {70, 79, 60, 61}}
        };
	for(i = 0; i < 2; i++){
		printf("%d반\n", i + 1);
		for(j = 0; j < 2; j++){
			printf("%d번 성적\n", j + 1);
			for(k = 0; k < 4; k++){
				printf("점수 %d : %d \n", k + 1, score[i][j][k]);
			}; // k
		}; // j
	}; // i
	
    return 0
}