순차 자료구조 / 연결 자료구조

자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉜다.
자료구조 유형을 프로그램으로 구현하는 방식은 순차 자료구조 와 연결 자료구조 가 있다.

구분	순차 자료구조	연결 자료구조
메모리 저장 방식	빈자리 없이 자료를 연속해 저장한다. 논리적인 순서와 물리적인 순서(메모리 저장 순서)가 일치한다.	메모리의 물리적 위치나 순서에 상관없이 링크로 논리적 순서를 표현한다.
연산 특징	삽입, 삭제 연산 시 빈자리 없이 수행한다.	삽입, 삭제 연산 시 논리적 순서가 변경되어도 링크 정보만 변경되고 물리적 순서는 변하지 않는다.
프로그래밍 기법	배열	포인터

---

선형 리스트

메모리에 저장하는 구현 방식에 따라
순차 방식으로 구현하는 선형 순차 리스트 , 연결 방식으로 구현하는 선형 연결 리스트 로 구분한다.
( 간단히 선형 순차 리스트 = 선형 리스트 / 선형 연결 리스트 = 연결 리스트 라고 한다 )

순차 자료구조는 시작 위치와 원소 크기를 알면 특정 원소의 위치를 쉽게 알 수 있다. 시작 위치가 a, 원소 크가가 b 인 선형 리시트의 i번째 원소의 위치는 a+(i-1)*b 이다.
ex) 두 번째 원소 위치 : a+b / 세 번째 원소 위치 : a+2b

선형 리스트의 원소 삽입

선형 리스트는 순차 자료구조 방식이므로, 삽입 후 변경된 논리적 순서와 물리적 순서가 일치해야 한다. 즉, 삽입할 위치 다음의 원소들을 모두 한 자리씩 뒤로 옮긴다.

원소가 (n+1)개 , 원소 삽입 위치 k 일 때,
원소 삽입을 위해 k번 ~ n번 원소까지 뒤로 이동한다. (인덱스는 0번부터 이므로 원소 개수가 n+1)
∴ 원소 삽입 시 빈자리를 만들기 위한 이동 횟수 : n-k+1

n-k+1 에서 +1은 삽입 위치에 원래 있던 원소까지 포함하는 것이다.

ex)
| 1 | 2 | 3 | 4 | 5 | => 3번 째 자리에 0 원소 삽입하려면 3,4,5가 한 칸씩 뒤로 이동해야함
n-k+1 = 5-3+1 = 3번의 이동

선형 리스트의 원소 삭제

선형 리스트에서 원소 삭제가 이루어지면, 삭제된 원소 뒤의 모든 원소가 한 칸씩 앞으로 이동한다.

원소가 (n+1)개 , 원소 삽입 위치 k 일 때,
원소가 삭제되어 k+1번 ~ n번 원소까지가 앞으로 당겨진다.
∴ 원소 삭제 시 빈자리를 채우기 위한 이동 횟수 : n-(k+1)+1 = n-k

ex)
| 1 | 2 | 3 | 4 | 5 | => 원소 3 삭제하면 4,5가 앞으로 한 칸씩 이동한다.
n-k = 5-3 = 2번의 이동

선형 리스트 구현

1차원 배열

: 인덱스를 하나만 사용하는 배열

• int 자료형으로 선언되었을 경우 각 원소의 길이는 4byte 이다.
• 배열 인덱스는 0부터 시작한다.
• 각 원소의 위치는 시작 주소가 a일 때, a+(배열 인덱스 * 4byte) 이다.
  1000 -> 1004 -> 1008 ...

2차원 배열

int arr2[2][4] = {{1,2,3,4},
				  {5,6,7,8}};

2차원 배열 구조를 논리적으로 표현할 때는 행과 열의 구조지만, 실제로 메모리에 저장될 때는 1차원 구조로 저장된다. 이때, 저장되는 방식이 두 가지가 있는데,

행 우선 순서 : 행을 기준, 같은 행 안에 있는 열을 먼저 저장
→
→
1,2,3,4,5,6,7,8 순서로 저장

열 우선 순서 : 열을 기준, 같은 열 안에 있는 행을 먼저 저장
↓↓
1,5,2,6,3,7,4,8 순서로 저장

2차원 배열의 A[i][j]의 위치 구하는 법
시작 주소 a , 원소 길이 b (int의 경우 4byte) , 행의 개수 ni , 열의 개수 nj 일 때,

• 행 우선 순서 방법 : a+(ixnj+j)xb
• 열 우선 순서 방법 : a+(jxni+i)xb

3차원 배열

int arr3[2][2][4] = {{{1,2,3,4},
					{5,6,7,8}},
                    {{9,10,11,12},
                    {13,14,15,16}}};

3차원 배열의 A[i][j][k]의 위치 구하는 법
시작 주소 a , 원소 길이 b , 면의 개수 ni , 행의 개수 nj , 열의 개수 nk

• 면 우선 순서 구조 : a+{(ixnjxnk)+(jxnk)+k}xb
• 열 우선 순서 구조 : a+{(kxnixnj)+(jxni)+i}xb