[자료 구조] 선형(Linear) 자료 구조 (1) 배열(Array), 연결 리스트(Linked List)

 

포스트를 읽으실 때 참고하실 점

• 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다.
• 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다.

 

---

 

자료 구조와 알고리즘에 대한 이해는 프로그래머 꿈나무에게 있어서 아주 기초적으로 필요한 덕목이지만 본격적으로 파고 들려면 굉장히 어려운 분야이다. 우리 같은 초보 프로그래머 꿈나무들이 자료 구조를 공부해야하는 목적은 '남들이 봤을 때 휘황찬란하고 복잡한 자료 구조를 써야 멋지고 고수 같아서' 가 절대 아니다. 주어진 상황에 따라 어떤 자료 구조를 사용하는 것이 적합할지 스스로 판단하는 능력을 기르고, 현재 사용하는 코드를 분석하여 보다 효율적으로 개선할 수 있는 능력을 기르기 위함이므로, 이러한 점에 중점을 두어 자료 구조 및 알고리즘 공부를 시작했다. 기초만 탄탄하게 쌓으면 복잡한 자료 구조를 구현하고 문제를 풀 수 있게 되는 응용력은 프로그래밍 경험(시간)을 통해 자연스럽게 쌓일 것이라고 생각한다.

 

자료 구조 및 알고리즘을 공부할 때에는 복잡한 자료 구조들이나 알고리즘의 구현도 중요하지만, 기초 개념들의 원리나 사용되는 예시와 이유 등을 잘 숙지하는 것이 더 중요하다.

---

 

선형 자료 구조란?

자료 구조 분야에서 다루는 가장 기본적인 형태의 구조로, 자료들을 선형적인(linear) 구조로 관리하는 자료 구조이다. 선형적이라는 말은 자료 간의 전후 관계가 1 대 1인 구조를 말한다.

 

자료 간의 전후 관계가 1 대 1인 구조?

 

자료 간의 전후 관계가 1 대 1이라는 말은, '자료들 사이에 명확하게 앞, 뒤 순서가 있다' 는 뜻이기도 하다. 용어가 어찌되었든 이공계 분야에서 '선형(linear)' 이라는 단어가 붙은 개념들은 일반적으로 다른 파생 개념들의 기반이 되는 매우 중요한 개념들이다. 자료 구조는 크게 선형 자료 구조와 비선형(non-linear) 자료 구조로 나뉘는데('파일 구조' 라는 분류로도 나눌 수 있다고 하는데 이 부분은 포스팅에서 예외함), 대표적으로 활용되는 자료 구조들을 위주로 포스팅 해볼 계획이다.

 

대표적인 선형 자료 구조로는 배열(array), 연결 리스트(linked list), 스택(stack), 큐(queue)가 있다. 이번 포스트에서는 배열과 연결 리스트에 대해 간단하게 정리해보려고 한다. 특히나, 앞으로 계속 포스팅 할 모든 개념들이 모두 배열 또는 연결 리스트를 활용하여 구현되기 때문에 기본 중의 기본 중의 기본 중의 기본 중의 ...

 

---

 

배열(array)

배열은 요소의 크기 단위로 연속적인 메모리 공간을 이용해 데이터를 선형적으로 관리하는 자료 구조이다. 배열을 공부하다보면 한 번쯤 배열의 주소 연산 결과를 출력해 본 경험이 있을 수 있는데, 그렇다면 쉽게 이해할 수 있다.

 

배열이 가지는 주요한 특징(장점 및 단점)들은 전부 '연속적인 메모리' 공간을 다루기 때문에 나타난다. 배열이 가지는 장점으로는, 자료에 해당하는 인덱스를 알고 있을 때 해당 자료에 대한 접근이 빠르다는 것이다. 데이터가 배열 내에서 몇 번째에 위치하는지 알고 있다면 해당 데이터에 접근할 때 인덱스(index) 연산을 통해 단번에 접근 가능함을 의미한다.

 

int myArray[5];			// C++ 프로그래머에게 친숙한, 길이가 5인 int 형의 고정 배열.
std::vector<int> myVector;	// STL vector 헤더를 포함한 뒤 사용할 수 있는 동적 배열.

myArray[3];			// 4번째 요소에 바로 접근, vector의 경우에도 마찬가지로
				// 인덱스 연산을 위한 [] 연산자가 오버로딩 되어있다(또는 at() 메서드).

 

이외의 장점으로는, 배열은 C나 C++에서 기본적으로 별다른 헤더의 추가 없이도 제공하는 기능이며 프로그래밍을 배울 때 누구나 자연스럽게 초반부에 배열의 개념을 배우게 되어 자료 구조를 아직 잘 모르는 프로그래밍 초보자에게도 사용이 아주 쉽고(맞나?...) 익숙하다는 점이다.

 

배열이 메모리를 연속적으로 사용하기 때문에 발생하는 단점도 존재한다. 배열은 요소의 크기의 배수 단위로 메모리를 할당/해제해야 하므로, 배열에 대한 동적 메모리의 할당/해제가 빈번하게 일어날 경우 메모리 단편화(memory fragmentation)가 발생할 소지가 특히 크다. 또한, 기존의 데이터들 사이에 새로운 데이터를 삽입하는 과정(데이터들을 일부 뒤로 밀어야 함)이 복잡하다.

 

[핵심] 배열의 특징은 '연속적인 메모리 공간의 사용' 으로부터 나타난다.

1. 인덱스를 통해 데이터에 빠르게 접근 가능하다 !
2. 자료형 크기의 배수만큼 메모리를 할당/해제해야 하므로
    → 배열을 빈번히 동적 할당/해제하면 메모리 단편화 발생의 소지가 크다 !
3. 기존의 데이터들 사이에 새로운 데이터를 끼워 넣는 과정이 복잡하다 !

 

---

 

연결 리스트(linked list)

연결 리스트는 선형 자료 구조이면서 연속적이지 않은 메모리 공간을 사용하여 데이터를 관리하는 구조이다. 메모리 공간을 연속적으로 사용하지 않는데도 데이터를 선형적으로 관리할 수 있는 이유는 포인터(pointer)에 기반하기 때문이다. 연결 리스트는 노드(node)라는 형태로 데이터를 보관하는데, 이 노드들은 각각 다른 데이터를 가지는 노드를 가리킬 수 있는 포인터 변수를 가진다. 이러한 포인터들에 의해 선형적 연결 형태로 데이터를 관리하는 것이 연결 리스트이다.

 

// 연결 리스트의 단위가 되는 노드는
// 아래와 같이 데이터를 보관하면서, 인접한 노드를 가리키는 포인터를 가진다.
// 편의상, 데이터는 int형이라고 가정했다.
class LinkedList
{
public:
	struct Node
	{
		int Data;	// 데이터
		Node* Next;	// 인접한 노드를 가리키는 포인터이므로 자기 자신(노드)에 대한 포인터형
	};

private:
	Node* Head;		// 가장 앞의 노드를 가리킨다

public:
	// Some methods...
};

 

따라서, 연결 리스트는 배열과는 다른 특징을 갖는다. 연결 리스트는 구조 전체에 대한 메모리를 할당/해제할 필요 없이, 노드 단위로 추가/제거를 할 수 있다는 특징이 있다. 또한 단순히 포인터로 연결하는 구조이므로 기존 데이터들사이에 새로운 데이터를 삽입/제거하는 과정이 배열에 비해 간단하다(단, 노드 삽입/제거할 때 앞, 뒤를 가리키는 포인터 변수를 잘 제어해야 한다).

 

한편, 연결 리스트 역시 단점이 존재하는데 일반적으로 찾고자 하는 데이터에 접근하는 과정이 배열에 비하여 느리다. 왜냐하면 찾고자 하는 데이터를 가지는 노드가 처음 노드에서 몇 번째로 떨어져있는지를 알 수 없기 때문이다. 따라서 처음 노드부터 순차적으로 탐색을 수행해야하기 때문에, 일반적으로 특정 데이터에 접근하는 과정이 배열에 비하여 느리다.

 

[핵심] 연결 리스트의 특징은 '포인터를 통한 불연속적인 연결 형태' 로부터 나타난다.

1. 노드 단위로 메모리 할당/해제 → 배열의 할당/해제에 비해 메모리 단편화 발생 소지가 적다 !
2. 데이터들 사이에 새로운 데이터를 추가하는 게 비교적 쉽다 !
3. 원하는 노드를 찾기 위해서는 첫 노드부터 순차적으로 탐색해야하므로,
    특정 데이터에 접근하는 과정이 배열보다 느리다 !
4. 일반적으로 연결 리스트를 구현할 때 포인터를 재귀적으로 이용하므로,
    반드시 첫 노드(head), 마지막 노드(tail)가 잘 처리되는지 확인해야 한다 !

 

이 포스트에서 구체적으로 설명하지는 않지만, 연결 리스트는 연결 방향에 따라 노드들의 포인터가 한 방향으로만 다음 노드를 가리키는 단방향 리스트(singly-linked list), 앞/뒤 노드를 각각 가리키는 포인터를 가지는 양방향 리스트(doubly-linked list)로 나뉠 수 있다. 또한, 연결 리스트의 첫 노드와 마지막 노드를 연결한 형태인 환형 연결 리스트(circularly linked list)와 같은 파생 구조도 존재한다(그러나 자주 사용되지는 않음). 단방향 연결 리스트와 노드에 대한 이해만 확실하게 갖춘다면, 시간만 더 걸리고 약간 더 헷갈리기만 할 뿐(?) 양방향 연결 리스트나 환형 연결 리스트를 직접 구현하는 것이 그리 어려운 일은 아니다.

 

 

---

 

배열과 연결 리스트의 활용

배열과 연결 리스트가 활용되는 예시로, 가장 대표적인 것은 다른 자료 구조들의 기반으로 사용되는 것이다. 다른 선형 자료 구조인 스택과 큐를 비롯하여 모든 비선형 자료 구조 역시 배열과 연결 리스트 중의 하나를 기반으로 만들어진다.

 

배열을 사용하게 되는 경우는 일반적으로 자료 구조의 최대 크기가 고정되며, 한 번 선언되면 지속적으로 재활용할 수 있는 경우, 또는 인덱스를 이용한 빠른 데이터 접근이 필요한 경우라고 정리할 수 있다.

 

연결 리스트가 활용될 때는 자료 구조의 최대 크기를 확정할 수 없는 경우, 메모리 단편화 등의 문제점을 최소화하기 위하여 사용될 수 있다(주로 트리 및 그래프 구조의 기반으로 많이 활용한다).

 

---

 

포스트에 소개되지 않은 구체적인 내용은 1) 글 아래의 태그 또는 블로그 내 검색을 통해 활용 예시 찾아보기(코딩 문제 풀이 등), 2) 관련 링크나 구글링을 통해 따로 공부해야하는 점은 양해를 부탁드립니다.