[자료구조] 순차 자료구조

리스트(List)

 - 자료를 나열한 목록

 ex)

    분식 = ['떡볶이', '김밥', '순대', '핫도그', '튀김', '어묵']

    수능 = ['국어', '수학', '영어', '사회', '과학', '외국어']

    나라 = ['대한민국', '미국', '중국', '일본']

 

선형 리스트(Linear List)

 - 순서 리스트(Ordered List)

 - 자료들 간 순서를 갖는 리스트

 

선형 리스트의 저장

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

 - 순차 자료구조의 원소 위치 계산

    - 선형 리스트가 저장된 시작 위치 a

    - 원소의 길이 : l

    - i번째 원소의 위치 = a + (i-1) x l

 

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

 - 중간에 원소 삽입시 그 뒤 원소들은 한 자리씩 뒤로 이동하여 물리적 순서와 논리적 순서를 일치시킨다.

 - 방법

    ① 원소를 삽입할 자리 이후 원소들을 뒤로한 자리씩 밀어 빈자리 만들기

    ② 준비한 빈자리에 원소 삽입

 - 자리 이동 횟수 : 마지막 원소 인덱스 - 삽입할 자리 인덱스 + 1

 

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

 - 중간에 원소 삭제 시 그 뒤 원소들은 한 자리씩 앞으로 이동하여 물리적 순서와 논리적 순서를 일치시킨다.

 - 방법

    ① 원소 삭제

    ② 삭제한 자리 이후 원소들을 앞으로 한 자리씩 앞으로 당겨 삭제한 빈자리 채우기

 - 자리 이동 횟수 : 마지막 원소 인덱스 - 삭제한 자리 인덱스

 

선형 리스트 구현

 - 순차 구조의 배열 사용 ( 배열 = <인덱스, 원소> )

 - 1차원 배열 이용

 ex)

논리적 구조

[0]

[1]

[2]

[3]

물리적 구조

[0]

[1]

[2]

[3]

 - 2차원 배열 이용

 ex)

논리적 구조

[0][0]	[0][1]	[0][2]	[0][3]
[1][0]	[1][1]	[1][2]	[1][3]

물리적 구조

① 행 우선 순서 방법(row major order)

    ㄴ 원소의 위치 계산 방법 : 배열의 시작 주소 + (행 x 열의 개수 + 열) x 원소의 길이

[0][0]

[0][1]

[0][2]

[0][3]

[1][0]

[1][1]

[1][2]

[1][3]

② 열 우선 순서 방법(column major order)

    ㄴ 원소의 위치 계산 방법 : 배열의 시작 주소 + (열 x 행의 개수 + 행) x 원소의 길이

[0][0]

[1][0]

[0][1]

[1][1]

[0][2]

[1][2]

[0][3]

[1][3]

 - 3차원 배열 이용

 ex)

논리적 구조

[0][0][0]	[0][0][1]	[0][0][2]	[0][0][3]
[0][1][0]	[0][1][1]	[0][1][2]	[0][1][3]

[1][0][0]	[1][0][1]	[1][0][2]	[1][0][3]
[1][1][0]	[1][1][1]	[1][1][2]	[1][1][3]

물리적 구조

① 면 우선 순서 방법

    ㄴ 원소의 위치 계산 방법 : 배열의 시작 주소 + {(면 x 행의 개수 x 열의 개수) + (행 x 열의 개수) + 열} x 원소의 길이

[0][0][0]

[0][0][1]

[0][0][2]

[0][0][3]

[0][1][0]

[0][1][1]

[0][1][2]

[0][1][3]

[1][0][0]

[1][0][1]

[1][0][2]

[1][0][3]

[1][1][0]

[1][1][1]

[1][1][2]

[1][1][3]

② 열 우선 순서 방법

    ㄴ 원소의 위치 계산 방법 : 배열의 시작 주소 + {(열 x 행의 개수 x 면의 개수) + (행 x 면의 개수) + 면} x 원소의 길이

[0][0][0]

[1][0][0]

[0][1][0]

[1][1][0]

[0][0][1]

[1][0][1]

[0][1][1]

[1][1][1]

[0][0][2]

[0][1][2]

[1][0][2]

[1][1][2]

[0][0][3]

[0][1][3]

[1][0][3]

[1][1][3]