1. 정의

자료구조는 데이터를 효율적으로 구성하고 저장하며 조작하기 위한 방법이나 원칙을 의미합니다.데이터를 효율적으로 저장하고 관리하기 위해서는 적절한 자료구조를 선택하고 활용하는 것이 중요합니다.

2. 선형구조와 비선형구조

자료구조는 크게 선형구조, 비선형구조로 구분할 수 있다.

2-1. 선형구조(Linear Data Structure)

선형 구조는 순차적으로 하나의 선(Line) 처럼 나열된 형태의 자료 구조입니다. 대표적인 선형 구조로는 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등이 있습니다.

동일한 데이터 타입의 요소들을 연속된(연결된) 메모리 공간에 저장하는 자료구조입니다. 각 요소는 인덱스를 통해 접근할 수 있으며, 연속된 메모리 공간에 저장되어 있기 때문에 빠른 접근이 가능합니다. 하지만 배열의 크기는 정적으로 할당되기 때문에 크기를 동적으로 변경하기 어렵습니다.
장점 : 연속된 메모리 공간에 저장되어 있기 때문에 빠른 접근이 가능합니다.
단점 : 배열의 크기가 정적으로 할당되어 동적으로 변경하기 여렵습니다.

※ swift에서 배열은 동적으로 크기가 할당되기 때문에 배열의 단점을 보완되었습니다.

데이터를 저장하는 데이터필드와 다음 방향을 알려주는 포인터가 하나의 쌍으로 이루어진 노드라는 단위가 한줄로 연결되어있는 구조입니다. 실질적으로 연결되어 있지는 않고, 포인터로 다음이나 이전으로 연결해줍니다.(단방향, 양방향 모두 가능)

장점 : 크기를 동적으로 할당할 수 있고, 데이터 삽입/삭제를 하기 쉽고,빠릅니다.
단점 : 데이터에 접근하기 위해선 순차적으로 탐색해야 하므로 접근 시간이 배열에 비해 느릴 수 있습니다.

코드구현

 class Node<T> {
     var data: T?
     var next: Node?
 
     init(data: T?, next: Node? = nil) {
         self.data = data
         self.next = next
     }
 }
 

정의에서 말씀 드린대로, 노드는 데이터와 다음을 알려주는 포인터로 구현해줍니다.

 class LinkedList<T> {
   private var head: Node<T>?
 }
 

연결 리스트 class를 작성하여 내부에 필요한 메서드를 작성해줍니다.

 func append(data: T?) { // 노드 추가하기
 
 //head가 없는 경우 Node를 생성 후 head로 지정해준다
 if head == nil {
     head = Node(data: data)
     return
 }
 
 var node = head
 
 // while문으로 head부터 끝까지 순회하여 마지막 노드는 next가 없기 때문에 마지막에 추가.
 while node?.next != nil {
     node = node?.next
 }
 node?.next = Node(data: data)
   }
 

이해를 돕기 위해 이미지를 첨부하겠습니다.

(이미지 출처 : https://babbab2.tistory.com/86)

 func insert(data: T?, at index: Int) {
 //head가 없는 경우 Node를 생성 후 head로 지정한다
 if head == nil {
     head = Node(data: data)
     return
 }
 
 var node = head
 // insert 할 index 전까지 반복문으로 순회
 for _ in 0..<(index - 1) {
     if node?.next == nil { break }
     node = node?.next
 }
 // nextNode에 insert 전 다음 노드를 할당해주고, node.next에 insert 해줄 노드를 할당해줍니다. 마지막으로 다음 다음 노드에 nextNode를 할당해줍니다.
 
 let nextNode = node?.next
 node?.next = Node(data: data)
 node?.next?.next = nextNode
 }
 

이해를 돕기 위해 이미지를 첨부하겠습니다.

(이미지 출처 : https://babbab2.tistory.com/86)

 func removeLast() { // 마지막 노드 삭제
 // 아무것도 없을땐 return
 if head == nil { return }
 
  // head를 삭제하는 경우
 if head?.next == nil {
     head = nil
     return
 }
 
 var node = head
 // while문으로 다음 다음 노드가 nil일때까지 순회하고, 다음 다음이 없을때 다음 노드에 nil을 할당하여 제거해준다.
 while node?.next?.next != nil {
     node = node?.next
     }
 node?.next = nil
   }
 

이해를 돕기 위해 이미지를 첨부하겠습니다.

(이미지 출처: https://babbab2.tistory.com/86)

 func remove(at index: Int) {
 
 if head == nil { return }
 
 // head를 삭제하는 경우
 if index == 0 || head?.next == nil {
     head = head?.next
     return
 }
 
 var node = head
 for _ in 0..<(index - 1) {
     if node?.next?.next == nil { break }
     node = node?.next
 }
 
 node?.next = node?.next?.next
 
 }
 

 struct Stack<T> {
     private var elements: [T] = []
 
     var count: Int {
         return elements.count
     }
 
     mutating func push(_ element: T) {
         elements.append(element)
     }
 
     mutating func pop() -> T? {
         return elements.popLast()
     }
 
     func peek() -> T? {
         return elements.last
     }
 }
 
 var stack = Stack<Int>()
 stack.push(100) // 100 append
 stack.push(200) // 200 append
 stack.push(300) // 300 append
 stack.push(400) // 400 append
 stack.count // 4
 stack.pop // 400 popLast
 stack.count // 3
 

 public struct Queue<T> {
   // queue의 데이터를 저장할 배열 선언
   private var data = [T]()
   public init() {}
 
   // 새로운 데이터 삽입
   // 가장 뒤에 삽입하면 되기 때문에 append 사용
   mutating func enqueue(_ element: T) {
     data.append(element)
   }
 
   // FIFO의 특성에 따라 첫번째 값 반환 및 삭제
   mutating func dequeue() -> T? {
     return data.removeFirst()
   }
 
   // 첫번째 값 반환(삭제는 X)
   func peek() -> T? {
     return data.first
   }
 
   // 모든 데이터 삭제하기
   mutating func clear() {
     data.removeAll()
   }
 
   // 큐에 있는 데이터 갯수 반환
   // 연산 프로퍼티
   var count: Int {
     return data.count
   }
 
 }
 
 var queue = Queue<Int>()
 queue.enqueue(100) // 100 append
 queue.enqueue(200) // 200 append
 queue.enqueue(300) // 300 append
 queue.enqueue(400) // 400 append
 queue.count // 4
 queue.peek() // 100
 queue.dequeue() // 100 remove
 queue.count // 3
 

2-2. 비선형구조(NonLinear Data Structure)

비선형 구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는것입니다.자료들 간의 앞뒤 관계가 1:n 또는 n:n의 관계를 가집니다. 대표적인 비선형 구조로는 트리(Tree),그래프(Graph) 등이 있습니다.

트리는 이름처럼 나무를 뒤집어 놓은 모양이다. 노드들이 나무가지처럼 연결된 비선형 계층적 자류구조입니다.

2-2-1. 트리 용어

노드 (Node)

• 트리를 구성하는 기본 요소
• 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있습니다.

간선 (Edge)

• 노드와 노드 간의 연결선

루트 노드 (Root Node)

• 트리 구조에서 부모가 없는 최상위 노드
• root node : A

부모 노드 (Parent Node)

• 자식 노드를 가진 노드
• H, I에 부모 노드는 D

자식 노드 (Child node)

• 부모 노드의 하위 노드
• 노드 D의 자식 노드는 H, I

외부 노드(external node, outer node),리프 노드(leaf node)

• 자식 노드가 없는 노드
• H, I, J, F, G

내부 노드 (internal node, inner node),가지 노드 (branch node)

• 자식 노드 하나 이상 가진 노드
• A, B, C, D, E

높이 (height)

• 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
• A 노드의 높이 : 3

레벨(Level)

• 루트에서 어떤 노드까지의 간선(Edge) 수

노드의 차수(Degree)

• 노드의 자식 수

2-2-2. 트리의 종류

트리는 많은 종류의 트리가 있지만 흔히 사용되는 이진트리, 이진탐색트리와 생소한 AVL트리를 다뤄보겠습니다.

이진트리(Binary Tree)

이진 트리는 모든 노드들이 둘 이하의 자식을 가진 트리입니다. 이진트리에는 다양한 종류의 이진트리가 있습니다.(이진탐색트리,포화이진트리, 완전이진트리, 편향이진트리,정이진트리,균형이진트리)

이진탐색트리(Binary Search Tree)

이진탐색트리 또한 이진트리의 한 종류로 모든 노드에 대해 왼쪽 자식노드의 값은 현재 노드 의 값보다 작고 오른쪽 자식노드의 값은 현재 노드의 값보다 크다는 특징이 있습니다.
이러한 특징 때문에 이진탐색트리는 기존 이진트리보다 탐색이 빠릅니다.

AVL트리

AVL트리는 과거 소련과 이스라엘 컴퓨터 과학자인 Adelson-Velsky와 Evgenii Landis가 함께 발명한 트리이며 이름의 앞 글자를 따서 AVL 트리로 명명하였습니다.
특징으로는 이진탐색트리의 속성을 가지고 있고, 왼쪽 오른쪽 자식 자식 노드의 높이 차이가 최대 1이며, 높이차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄입니다.

3. 해시테이블

해시 테이블을 알기전 알아야할 용어가 있습니다. 조금 알아보고 설명을 드리겠습니다.

관련 용어

• 키(key) : 원래의 데이터 값, 해시함수의 인풋(해시 함수 입력 전)
• 값(value) : 최종 저장되는 값
• 해싱(hashing) : key -> index로 바꾸는 과정
• 해시함수(hash funtion) : key -> index로 바꿔주는 함수
• 해시값(hash value) : key에 해시함수를 적용한 값 (index)

해시 테이블은 키 값 쌍을 저장하는 자료구조이며, 키(key) → 해시 함수(Hash function) → 인덱스(index)로 변환해 저장하는 공간, 저장하는 자료구조라 이해하면 이해가 편하실겁니다.

해시충돌

이러한 해시테이블에서 서로 다른 키가 동일한 해시값을 가지는 현상을 말합니다. 즉 서로 다른 . 두입력 값에 대해 동일한 출력값을 내는 상황을 의미합니다.
이러한 예시로 여러 사람이 모였을 때 생일이 같은 2명이 존재하는 상황입니다.

이러한 충돌을 해결하는 방법으로는 같은 주소로 해싱 될 때. 연결 리스트로 연결하여 해결하는 체이닝 방식과 충돌 발생 시 탐사를 통해 다른 빈 공간을 찾아 나서는 개방 주소법이 있습니다.