[자료구조] 선형 리스트(Linear List) 개념과 구현

선형 리스트

데이터를 구조화시키는 가장 기본적인 방법은 나열하는 것입니다. 예를 들어, 좋아하는 음식을 나열하거나 오늘의 할 일을 나열하는 것 등 이렇게 나열한 목록을 리스트(List)라고 합니다. 이와 같이 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트를 선형 리스트(Linear List)라고 합니다.

선형리스트 특징

선형 리스트는 배열을 이용하여 구현하기 때문에 원소들의 논리적인 순서와 메모리에 저장되는 물리적인 순서가 같다는 특징이 있습니다.

선형 리스트 구현

선형 리스트는 배열을 이용하여 구현할 수 있습니다.

 

· 1차원 배열의 순차 표현

public class MainForOneDimensionalArray {
	public static void main(String[] args) {
		int[] array = new int[] { 7, 13, 1, 9 };

		for (int i = 0; i < array.length; i++) {
			System.out.printf("array[%d] = %d\n", i, array[i]);
		}
	}
}

 

1차원 배열 논리 구조

· 2차원 배열의 순차 표현

public class MainForTwoDimensionalArray {
	public static void main(String[] args) {
		int[][] array = new int[][] { { 7, 13, 1, 9 }, { 23, 41, 8, 12 } };

		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.printf("array[%d][%d] = %d\n", i, j, array[i][j]);
			}
			System.out.println();
		}
	}
}

2차원 배열 논리 구조

2차원 배열은 실제 메모리에 저장될 때 1차원 순서로 저장됩니다. 2차원의 논리적 순서가 1차원의 물리적 순서로 변환되는 방법은 첫 번째 인덱스를 기준으로 하는 행 우선 순서(Row Major Order) 방법과 마지막 인덱스를 기준으로 하는 열 우선 순서(Column Major Order) 방법이 있습니다. 이와 같이 논리적 순서를 물리적 순서로 변환하는 방법은 프로그래밍 언어의 컴파일러에 의해서 결정됩니다.

 

· 3차원 배열의 순차 표현

public class MainForThreeDimensionalArray {
	public static void main(String[] args) {
		int[][][] array = new int[][][] { { { 7, 13, 1, 9 }, { 23, 41, 8, 12 } },
				{ { 5, 40, 32, 28 }, { 17, 45, 22, 27 } } };

		for (int i = 0; i < array.length; i++) { // 2
			for (int j = 0; j < array[i].length; j++) { // 2
				for (int k = 0; k < array[i][j].length; k++) { // 4
					System.out.printf("array[%d][%d][%d] = %d\n", i, j, k, array[i][j][k]);
				}
				System.out.println();
			}
		}
	}
}

3차원 배열 논리 구조

3차원 배열이 메모리에 저장되는 물리 구조는 2차원 배열과 마찬가지로 1차원 순서로 저장됩니다. 3차원의 논리적 순서가 1차원의 물리적 순서로 변환되는 방법은 첫 번째 인덱스인 면을 기준으로 하는 면 우선 순서(Plane Major Order) 방법과 마지막 인덱스인 열을 기준으로 하는 열 우선 순서 방법(Column Major Order)이 있습니다. 이와 같이 논리적 순서를 물리적 순서로 변환하는 방법은 프로그래밍 언어의 컴파일러에 의해서 결정됩니다.

선형 리스트 장점

배열을 이용하여 쉽게 구현할 수 있으며 인덱스를 사용하여 원소의 위치를 쉽고 빠르게 찾아 접근할 수 있습니다.

선형 리스트 단점

원소를 삽입 · 삭제할 경우 논리적인 순서와 물리적인 순서를 유지하기 위해 추가적인 오버헤드가 발생합니다. 따라서 삽입 · 삭제 연산이 많이 필요한 문제에서 사용하는 것은 비효율적입니다.

 

배열을 이용하여 구현하기 때문에 제한된 크기를 가지며 메모리 사용의 비효율성 문제를 그대로 갖습니다.