자료구조의 종류와 iOS 개발에서 자주 사용되는 자료구조

자료구조는 데이터를 효율적으로 사용할 수 있도록 정리하는 방법이다. 데이터 간의 관계 그리고 적용할 수 있는 함수나 명령을 의미한다. 

선형 자료구조와 비선형 자료구조로 나눌 수 있으며, 선형 자료구조는 데이터 요소를 순서대로 정렬하고 비선형 자료구조는 데이터를 비연속적으로 연결한다. 개별 요소에 접근하는 작업에는 선형 자료구조가 더 효율적이지만, 네트워크 연결과 같은 특정 문제를 효율적으로 해결하기 위해서는 비선형 자료구조가 더 알맞다.

배열, 연결 리스트, 스택, 큐의 특징과 iOS에서 구현 방법

배열

배열은 연속적인 메모리 블록에 요소를 저장한다. 각 0부터 인덱싱된다.

C언어의 경우에는 선언 시 크기가 고정되는 반면 Swift에서는 capacity가 초기화될 때 일정 크기의 메모리 공간을 할당받으며, capacity보다 요소가 많이 추가되면 2배로 늘어난다. 

var arr = [Int]()  // capacity = 0
arr.append(1)  // capacity = 1
arr.append(2)  // capacity = 2
arr.append(4)  // capacity = 4

var newArr: [Int] = [1, 2, 3, 4, 5]  // capacity = 5

 

배열의 크기가 동적으로 변경될 수 있다는 말은 메모리 힙 영역에 저장된다는 말과 같다. 여기서 힙 영역에 저장되는 것은 배열의 데이터이며, 인스턴스 자체는 스택에 할당된다.

// 구현
var words: [String] = []
words.append("Hello")
words.append("World")

var numbers = [Int]()

var alphabets = ["a", "b", "c"]

 

연결 리스트

배열과 마찬가지로 선형 데이터 구조이다. 인접한 메모리 주소로 저장되지 않는 점이 배열과 다르다.

다음 요소에 대한 주소 참조를 저장하는 entity와 데이터를 가지는 node로 연결되어 있다.

list

 

class Node<T> {
    var value: T
    var next: Node?
    
    init(_ value: T) {
        self.value = value
    }
}

class List<T> {
    private var head: Node<T>?
    
    func append(_ value: T) {
        let newNode = Node(value)
        if head == nil {
            head = newNode
            return
        }
        
        var current = head
        while let next = current?.next {
            current = next
        }
        current?.next = newNode
    }
}

 

스택

LIFO(후입선출: Last In, First Out) 규칙을 따르는 추가된 마지막 요소는 스택에서 제거하는 첫번째 요소이다.

데이터를 넣는 push, 데이터를 제거하는 pop, 스택의 마지막 요소를 반환하는 peek이 있다. 

데이터 삽입, 삭제의 시간 복잡도는 O(1)이다.

Stack

struct Stack<T> {
    private var array: [T] = []
    
    var peek: T? {
        return array.last
    }
    
    mutating func push(_ element: T) {
        array.append(element)
    }
    
    mutating func pop() -> T? {
        return array.popLast()
    }
}

 

큐

FIFO(선입선출: First In, First Out) 규칙을 따르는 가장 먼저 추가된 요소는 큐에서 제거하는 첫 번째 요소이다.

데이터를 추가하는 enqueue, 데이터를 제거하는 dequeue, 큐의 앞쪽 데이터를 반환하는 front가 있다.

Queue

 

Queue에서 enqueue와 dequeue의 시간 복잡도는 O(1)이다.

Swift에서는 배열의 시작 메모리 주소를 변경할 수 없기 때문에 frontIndex로 접근하는 방식으로 표현했다. 이러한 방식은 시간 복잡도만 신경쓰는 알고리즘 문제를 풀 때 사용하는 방법 중 하나이다.

struct Queue<T> {
    private var array: [T] = []
    private var frontIndex = 0
    
    mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    mutating func dequeue() -> T? {
        gaurd !array.isEmpty else {
            return nil
        }
        
        if frontIndex < array.count {
            frontIndex += 1
            return array[frontIndex-1]
        } else {
            return nil
        }
    }
}

 

큐의 연장선으로 덱(Deque, Double - Ended Queue)은 한쪽에서만 삽입, 다른 한쪽에서만 삭제가 가능했던과는 다르게 양쪽 front, rear에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조이다.

그리고 우선순위 큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오도록 한다. 주로 트리의 형태로 표현하며, 삽입 및 삭제의 시간 복잡도는 O(log N) 이다.

 

해시 테이블의 개념, 충돌 해결 방법

Hash Table, Hashing

 

트리 자료구조의 종류

트리 구조는 하나의 루트 노드를 가지며, 0개 이상의 자식 노드를 갖고 있습니다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있는 계층적 관계를 표현합니다. 

 

이진 트리는 자식 노드가 왼쪽 노드 그리고 오른쪽 노드 최대 2개를 갖는 트리 자료구조입니다. 

 

이진 탐색 트리

이진 트리의 한 종류로 노드의 값이 유일한 특성이 있습니다.

왼쪽 자식 노드는 루트 노드보다 값이 작고, 오른쪽 자식 노드는 루트 노드의 값보다 큽니다. (leftNode < rootNode < rightNode)

검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)입니다.

 

정렬된 데이터를 다룰 때 매우 효율적이기 때문에 데이터베이스, 파일 시스템 등에서 사용됩니다.

 

AVL 트리

AVL 트리는 G.M. Adelson-Velskii와 E.M. Landis의  이름을 딴 이름으며, Self-Balancing Binart Search Tree 라고 합니다.

모든 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 최대 1이어야 합니다.

조건을 만족하기 위해 노드의 회전 연산을 통해 트리를 재구성합니다. 

검색, 삽입, 삭제의 시간 복잡도는 O(log n)으로 유지할 수 있습니다.

 

효율적인 구조로 데이터베이스, 파일 시스템, 컴파일러 등에서 사용됩니다.