기본적인 데이터 구조

이번 절에서는 책 전반에 걸쳐 다루게 될 다양한 고급 데이터 구조의 기초가 될 스위프트의 대표적인 데이터 구조에 대해 살펴본다.

데이터 구조의 가장 근원적인 형태는 사실상 배열과 포인터 두 가지 타입이며, 다른 데이터 구조는 여기서 파생된다고 할 수 있다.

• 인접 데이터 구조^{Contiguous data structures}는 이름에서 알 수 있듯이 데이터를 메모리 영역 중 인접한 부분에 저장한다. 인접 데이터 구조에는 배열^arrays, 힙^heaps, 매트릭스^matrices, 해시 테이블^{hash tables} 등이 있다.
• 연결 데이터 구조^{Linked data structures}는 서로 명확히 구분되는 메모리 영역을 차지하되, 프인터라는 주소 체계로 연결, 관리되는 구조다. 연결 데이터 구조에는 목록^lists, 트리^trees, 그래프^graphs 등이 있다.

고급 데이터 구조를 만들 때 이들 두 가지 타입의 데이터 구조를 연결할 수 있다.

인접 데이터 구조

인접 데이터 구조는 선형 데이터 구조^{linear data structures}를 이루며 일정한 순서에 따라 개별 데이터 요소에 접근할 수 있는 인덱스 기반의 데이터 구조다.

배열

배열^array은 데이터 구조 가운데 가장 널리 사용되고 있으며, 대부분의 프로그래밍 언어에서 기본적으로 제공하는 데이터 구조다. 가장 단순한 유형은 일차원 배열^{one-dimensional array}로 부르기도 하는 선형 배열^{linear array}이다. 스위프트에셔 배열의 인덱스 값은 0부터 시작하며, 데이터 간의 순서가 있으며, 임의로 특정 요소에 접근할 수 있는 데이터 집합의 성질을 지닌다.

일차원 배열에서는 간단하게 ai 의 형식으로 특정 요소를 지칭할 수 있는 인덱스 표준 기법을 사용하며, 이때 인덱스를 나타내는 i 는 0부터 n 사이의 값을 넣을 수 있다.

$$a = \begin{pmatrix} a_0 & a_1 & \cdots & a_n \end{pmatrix}$$

다음과 같은 배열이 있다고 해보자.

$$a = \begin{pmatrix} 3 & 5 & 7 & 9 & 3 \end{pmatrix}$$

인덱스 표기법으로 다음과 같이 나타낼 수 있다.

$$a_0 = 3, a_1 = 5, \cdots, a_4 = 13$$

다른 배열 형식으로 다차원 배열^{multi-dimensional array}이 있으며, 행렬^matrix은 다차원 배열의 대표적인 형식이다. 행렬은 이차원 배열을 구현한 것인데, 이를 위한 인덱스 표기법은 aij 이다. 이 때 i 는 행을, j 는 열을 나타낸다.

$$a = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ \end{pmatrix}$$

아래와 같은 행렬이 있다면

$$a = \begin{pmatrix} 2 & 5 & 7 \\ 10 & 3 & 5 \\ 4 & 1 & 4 \\ \end{pmatrix}$$

인덱스 표기법으로 다음과 같이 나타낼 수 있다.

$$a_{00} = 2, a_{11} = 3, \cdots, a_{22} = 4$$

배열 선언

스위프트에서 배열을 선언하기 위한 문법 형식은 세 가지다. 첫 번째는 배열 선언을 위한 기본 방법인 Array<Type> 형식을 사용하는 것, 두 번째는 축약형인 [Type] 형식을 사용하는 것, 그리고 세 번째는 배열을 명시적으로 선언하지 않고 컴파일러가 타입을 추측^{type inference}하게 하는 방법이다.

// case1
var myIntArray:Array<Int> = [1, 3, 5, 7, 9]

// case2
var myIntArray:[Int] = [1, 3, 5, 7, 9]

// case3
var myIntArray = [1, 3, 5, 7, 9]

노트

타입 추측은 컴파일러가 컴파일을 실행할 개발자가 제공한 단서를 기준으로 타입을 추측하는 기능이다. 타입 추측 기능을 사용하면 변수의 초기 타입을 선언할 때 타이핑 횟수를 줄일 수 있다.

배열 선언 시 배열 빈 배열을 선언하고 싶다면 다음과 같이 작성한다.

var myIntArray:[Int] = []

다중 배열을 선언하려 할 때는 대괄호 안에 또 다른 대괄호를 추가한다. 요소의 기본 타입은 대괄호 중 가장 내부에 요소를 기준으로 결정한다.

var my2DIntArray:[[Int]] = [[1, 2], [10, 11], [20, 30]]

대괄호를 중첩해 2차원 이상의 다중 배열도 만들 수 있다.

var my3DIntArray:[[[Int]]] = [[[1, 2], [3, 4]], [[10, 11], [9]], [[20], [30]]]

배열 요소 가져오기

배열 내부의 요소를 가져오는 방법은 여러가지가 있다. 다음과 같은 배열을 활용해 배열의 요소를 가져와보자.

var myArray:[Int] = [1, 3, 5, 7, 9]

• 인덱스 번호를 통해 배열 요소를 직접 가져오기

var anotherNumber = myArray[2] // 5

• 배열 내 요소를 반복적으로 가져오기

for number in myArray {
    print(number) // print(1, 3, 5, 7, 9)
}

• 배열 요소 중 일정 범위에 속한 배열 요소를 가져오기

var sliceArray = myArray[2...4] // [5, 7, 9]

• 2차원 배열에서 특정 배열 요소 직접 가져오기

var my2DArray = [[1, 2], [10, 11], [200, 222]]

var myNumber = my2DArray[0][0] // 1

배열 요소 추가

배열 요소를 추가하는 방법은 해당 요소를 추가하려는 위치가 배열의 맨 끝 부분인지, 배열 내 처음과 끝 사이인지에 따라 달라진다.

위와 동일하게 아래와 같은 배열을 사용해보자.

var myArray:[Int] = [1, 3, 5, 7, 9]

• 기존 배열의 맨 끝 부분에 요소를 추가하기

myArray.append(10)
print(myArray) // [1, 3, 5, 7, 9, 10]

• 기존 배열의 특정 인덱스 위치에 요소를 삽입하기

myArray.insert(4, at: 2)
print(myArray) // [1, 3, 4, 5, 7, 9]

배열 요소 삭제

배열 요소의 삭제 역시 삭제하려는 요소의 위치가 배열의 맨 끝 부분인지, 중간인지에 따라 다르다.

위와 동일하게 아래와 같은 배열을 사용해보자.

var myArray:[Int] = [1, 3, 5, 7, 9]

• 배열의 맨 끝 부분의 요소 삭제하기

myArray.removeLast()
print(myArray) // [1, 3, 5, 7]

• 특정 인덱스 위치의 요소 삭제하기

myArray.remove(at: 3)
print(myArray) // [1, 3, 5, 9]

배열은 스택, 큐, 힙, 해시 테이블, 문자열 등 다양한 데이터 구조를 표현하는 데 활용된다.

연결 데이터 구조

연결 데이터 구조^{Linked data structures}는 데이터 타입과 이를 다른 데이터와 묶어주는 포인터로 구성된다. 여기서 포인터^pointer란 메모리상의 위치 주소를 의미한다. C와 같은 로우 레벨 프로그래밍 언어와 달리, 스위프트는 직접적으로 포인터에 접근하지 않으며, 포인터를 활용할 수 있는 별도의 추상 체계를 제공한다.

연결 데이터 구조 중 하나인 연결 리스트^{linked lists}에 대해 알아보자. 연결 리스트는 일련의 노드로 구성되며, 이들 노드는 링크 필드를 통해 서로 연결되어 있다. 가장 간단한 형태의 연결 리스트는 데이터와 다음 노드에 연결할 수 있는 레퍼런스(또는 링크) 정보를 포함한다. 좀 더 복잡한 형태의 경우, 추가 링크 정보를 통해 연결된 데이터에서 앞 또는 뒤로 이동할 수 있다. 연결 리스트에서 추가 노드를 삽입하거나 삭제하는 일은 매우 간단하다.

연결 리스트는 자체 참조 클래스인 노드로 구성되고, 각각의 노드는 데이터와 전체 연결 데이터에서 다음 노드로 이동할 수 있는 링크 정보를 포함한다.

컴퓨터 과학 분야에서,이와 같은 연결성을 표현하기 위해 시각적인 참조 방식인 화살표 기호를 사용한다.^[1]

single linked list

doubly linked list

circular linked list

단일 연결 리스트

연결 리스트 데이터 구조는 다음과 같이 선언한다.

class LinkedList<T> {
    var item: T? // 데이터
    var next: LinkedList<T>? // 다음 노드로 이동할 수 있는 링크 정보
}

---

[1] 이미지 출처: geeksforgeeks.org