[자료구조] - 순차 자료구조와 선형 리스트

👋 본 글은 "C로 배우는 쉬운 자료구조" 책을 읽고 요약, 정리한 글입니다.

---

책 구매 링크에서 책을 확인하실 수 있습니다.

 

🎯 1. 순차 자료구조와 선형 리스트의 이해

---

📌 1 - 1. 순차 자료구조의 개념

순차 자료구조란? : 구현할 자료들을 논리적인 순서로 메모리에 연속 저장하는 구현 방식

논리적인 순서와 물리적인 순서가 항상 일치해야 함

C 프로그래밍에서 순차 자료구조의 구현 방식을 제공하는 프로그램 기법은 배열

 

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

 

📌 1 - 2. 선형 리스트의 표현

리스트 : 자료를 나열한 목록

선형(순서) 리스트 : 원소들을 순서대로 나열한 리스트

 

선형 순차 리스트 (선형 리스트)

• 원소를 논리적인 순서대로 메모리에 연속하여 저장하는 순차 자료구조 방식의 선형 리스트
• 순차 자료구조 방식 : 원소를 논리적인 순서대로 메모리에 연속하여 저장

선형 연결 리스트 (연결 리스트)

• 원소를 논리적인 순서대로 연결하여 구성하는 연결 자료구조 방식의 선형 리스트

 

📌 1 - 3. 선형 리스트의 배열 표현

1차원 배열을 이용한 선형 리스트 표현

아래와 같은 자료가 있을 때

분기	1/4 분기	2/4 분기	3/4 분기	4/4 분기
판매량	157	209	251	321

C 언어로 표현하면

int sale[4] = {157, 209, 251, 312};

각 원소의 길이는 int 자료형이기 때문에 4byte

각 원소의 위치는 시작 주소가 a일 때 a + (원소의 배열 인덱스 x 4byte)

 

배열 sale의 시작 주소가 5241668 일 때

sale[2]의 위치는 5241668 + (2 x 4)이므로 = 5241676

 

2차원 배열을 이용한 선형 리스트 표현

아래와 같은 자료가 있을 때

연도 \ 분기	1/4 분기	2/4 분기	3/4 분기	4/4 분기
2021년	63	84	140	130
2022년	157	209	251	312

C 언어로 표현하면

int sale[2][4] = {
	{63, 84, 140, 130},
    {157, 209, 251, 312}
};

2차원 배열 구조를 논리적으로 표현할 때는 행과 열의 구조로 나타내지만, 실제로 메모리에는 1차원 구조로 저장됨

 

2차원인 논리적 순서가 1차원인 물리적 순서로 변환되는 방법에는 행 우선 순서 방법과 열 우선 순서 방법이 있음

• 행 우선 순서 방법 : 행을 기준으로 같은 행 안에 있는 값들을 먼저 저장
  • ex) sale[0][0], sale[0][1], sale[0][2], sale[0][3], sale[1][0], sale[1][1], sale[1][2], sale[1][3]
  • A[i][j]의 위치 = 시작 위치 + (i * 열의 개수 + j) * 자료형의 크기
• 열 우선 순서 방법 : 열을 기준으로 같은 열 안에 있는 값들을 먼저 저장
  • ex) sale[0][0], sale[1][0], sale[0][1], sale[1][1], sale[0][2], sale[1][2], sale[0][3], sale[1][3]
  • A[i][j]의 위치 = 시작 위치 + (j * 행의 개수 + i) * 자료형의 크기

C 언어에서는 행 우선 순서 방법을 사용함

 

배열의 시작 위치가 1374812일 때

행 우선 순서 방법에서의 sale[1][2]의 위치는 1374812 + (1 * 4 + 2) * 4 = 1374836

 

3차원 배열을 이용한 선형 리스트 표현

아래와 같은 자료가 있을 때

팀	연도 \ 분기	1/4 분기	2/4 분기	3/4 분기	4/4 분기
1팀	2021년	63	84	140	130
	2022년	157	209	251	312
2팀	2021년	59	80	130	135
	2022년	149	187	239	310

C 언어로 표현하면

int sale[2][2][4] = {
	{
    	{63, 84, 140, 130},
        {157, 209, 251, 312}
    },
    {
    	{59, 80, 130, 135},
        {149, 187, 239, 310}
    }
};

3차원 배열로 2차원 배열처럼 물리 구조는 1차원의 선형 구조로 저장된다

3차원 배열에서 면 우선 순서 방법과 열 우선 순서 방법이 있는데

• 면 우선 순서 방법 : ex) sale[0][0][0], sale[0][0][1], sale[0][0][2], sale[0][0][3], sale[0][1][0], ..., sale[1][1][3]
  • A[i][j][k]의 위치 = 시작 위치 + {(i * 행의 개수 * 열의 개수) + (j * 열의 개수) + k)} * 자료형의 크기
• 열 우선 순서 방법 : ex) sale[1][0][0], sale[0][1][0], sale[1][1][0], sale[0][0][1], ..., sale[1][1][3]
  • A[i][j][k]의 위치 = 시작 위치 + {(k * 면의 개수 * 행의 개수) + (j * 면의 개수) + i} * 자료형의 크기

 

시작 위치가 1374524 일 때

면 우선 순서 방법에서의 sale[1][1][2]의 위치 = 1374524 + {(1 * 2 * 4) + (1 * 4) + 2} * 4 = 1374580

 

순차 자료구조는 물리적 주소의 순서로 간단히 구성할 수 있고, 인덱스로 주소를 계산할 수 있으므로 특정 원소를 쉽게 액세스 할 수 있지만 원소를 삽입하거나 삭제할 경우에 물리적으로 원소들을 뒤로 밀거나 앞으로 당겨서 연속 저장 순서를 유지해야 하므로 읽기, 쓰기, 순차 액세스 같은 연산에서는 순차 자료구조가 효율적이지만 삽입, 삭제 연산이 많이 필요한 문제일 경우 순차 자료구조가 비효율적이다

 

🎯 2. 선형 리스트의 연산과 알고리즘

---

📌 2 - 1. 선형 리스트에서 원소 삽입과 알고리즘

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

 

10

20

40

50

60

70

위와 같은 선형 리스트가 있을 때 원소 삽입 방법은

1. 원소를 삽입할 빈자리 만들기

• 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 이동 (자리 이동하면서 원소가 덮어쓰기 되지 않도록, 마지막 원소부터 자리 이동)

10

20

40

50

60

70

 

2. 준비한 빈자리에 원소 삽입하기

10

20

30

40

50

60

70

 

삽입할 자리를 만들기 위한 자리 이동 횟수

• n개의 원소로 이루어진 선형 리스트에서 k 인덱스 자리에 원소를 삽입하는 경우 : k 인덱스 원소부터 마지막 인덱스(n - 1)번 원소까지 (n - 1) - k + 1개의 원소를 이동
• 이동 횟수 : 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1

 

📌 2 - 2. 선형 리스트에서 원소 삭제와 알고리즘

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

 

10

20

30

40

50

60

70

위와 같은 선형 리스트가 있을 때 원소 삭제 방법은

 

1. 원소 삭제하기

10

20

40

50

60

70

 

2. 삭제한 빈자리 채우기

• 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 자리 이동 (자리 이동하면서 원소가 덮어쓰기 되지 않도록, 앞에서부터 자리 이동)

10

20

40

50

60

70

 

삭제 후, 빈자리를 채우기 위한 자리이동 횟수

• n개의 원소로 이루어진 선형 리스트에서 k번의 원소를 삭제한 경우 : (k + 1)번 원소부터 마지막(n - 1)번 원소까지 (n - 1) - (k + 1) + 1개의 원소를 이동
• 이동 횟수 = n - k - 1 = 전체 원소 개수 - 삭제한 원소의 인덱스 - 1

 

🎯 3. 선형 리스트의 응용 및 구현

---

행렬의 개념

• 행과 열로 구성된 자료구조
• m x n 행렬 : 행 개수가 m개, 열 개수가 n개인 행렬
• 정방 행렬 : 행렬 중에서 m과 n이 같은 행렬
• 전치 행렬 : 행렬의 행과 열을 서로 바꿔 구성한 행렬(A, A')
• 희소 행렬 : 원소 대부분이 0인 행렬
  • 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어짐

 

희소 행렬에 대해 기억 공간을 좀 더 효율적으로 사용하기 위해 0이 아닌 값이 있는 원소만 따로 배열로 구성하는 방법을 사용 {행 번호, 열 번호, 값}의 쌍을 구해 2차원 배열에 저장

위 그림처럼 희소 행렬을 좀 더 효율적으로 표현한 2차원 배열의 첫 번째 행에는 전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수를 표시하고, 행, 열 순서대로 값을 저장한다.

 

기존에선 6 * 6의 36개의 공간을 사용했었지만, 9 * 3의 27개의 공간으로 줄여 표시할 수 있게 되었다.

 

📌 3 - 2. 다항식의 선형 리스트 표현

다항식의 개념

• axⁿ 형식의 항들의 합으로 구성된 식
  • a : 계수
  • x : 변수
  • n : 지수
• 지수에 따라 내림차순으로 항을 나열
• 다항식의 차수 : 가장 큰 지수
• 다항식 항의 최대 개수 = (차수 + 1) 개

희소 다항식의 차수가 1000일 때 순차 자료구조로 표현하면 크기가 1001인 배열을 사용, 기억 공간의 낭비가 심하기 2차원 배열로 표현

 

3x¹⁰⁰⁰ + x + 4라는 다항식을 순차 자료구조로 표현하면 기억 공간의 낭비가 심함

[0]	[1]	[2]	[3]	[4]	[∙∙∙]	[997]	[998]	[999]	[1000]
3	0	0	0	0	∙∙∙	0	0	1	4

 

2차원 배열로 표현하면

	[0]	[1]
[0]	1000	3
[1]	1	1
[2]	0	4

로 메모리를 아껴서 표현할 수 있다.