[Swift] 자료구조 - 배열(Array), 연결 리스트(Linked List)

배열(Array)

• 동일한 타입의 요소를 메모리의 연속적인 공간에 저장
• 인덱스를 통해 각 요소에 빠르게 접근할 수 있어, 인덱스를 알고 있는 경우 시간 복잡도가 O(1)이다.
• 하지만 배열의 크기가 고정되어 있거나 중간에 있는 요소를 추가하거나 삭제하는 경우 다른 요소들을 이동해야 하므로, 이러한 작업은 시간 복잡도가 O(n)이다.
• 빠른 인덱스를 통한 접근이 필요하거나, 데이터의 크기가 고정되어 있고 변경될 일이 없는 경우에 적합함.

  // 배열 생성 및 초기화
  var fruits = ["Apple", "Banana", "Cherry"]

  // 요소 추가
  fruits.append("Durian")

  // 요소에 접근
  print(fruits[2])  // 출력: Cherry

  // 요소 수정
  fruits[2] = "Blueberry"

  // 요소 삭제
  fruits.remove(at: 2)

  // 배열을 사용한 반복
  for fruit in fruits {
      print(fruit)
  }

연결 리스트(Linked List)

• 노드들이 포인터를 통해 연결되어 있는 선형 자료구조
• 각 노드는 데이터와 다음 노드에 대한 참조(또는 포인터)를 가진다.
• 요소의 추가와 삭제가 O(1) 시간에 이루어질 수 있다는 장점이 있지만, 특정 인덱스의 요소에 접근하기 위해서는 처음부터 해당 노드까지 순회해야 하므로 최악의 경우 O(n) 시간이 소요된다.

  class ListNode<T> {
      var value: T
      var next: ListNode?

      init(value: T, next: ListNode? = nil) {
          self.value = value
          self.next = next
      }
  }

  class LinkedList<T> {
      var head: ListNode<T>?

      // 마지막 노드에 요소 추가
      func append(value: T) {
          let newNode = ListNode(value: value)
          if let lastNode = self.last() {
              lastNode.next = newNode
          } else {
              head = newNode
          }
      }

      // 마지막 노드 찾기
      func last() -> ListNode<T>? {
          var node = head
          while let nextNode = node?.next {
              node = nextNode
          }
          return node
      }

      // 모든 요소 출력
      func printAllElements() {
          var node = head
          while node != nil {
              print(node!.value)
              node = node?.next
          }
      }
  }

  // 사용 예시
  let list = LinkedList<String>()
  list.append(value: "Apple")
  list.append(value: "Banana")
  list.append(value: "Cherry")
  list.printAllElements()

배열(Array)의 사용이 적합한 경우

1. 데이터 접근이 빈번한 경우
   배열은 인덱스를 통해 즉시 접근할 수 있기 때문에, 데이터에 빠르게 접근해야 할 때 유리함.
2. 데이터의 크기가 고정되어 있는 경우
   배열은 고정된 크기를 가지기 때문에, 데이터의 크기가 변하지 않을 것으로 예상되는 경우에 적합함 (ex. 게임 개발에서 화면에 표시되는 픽셀의 배열, 설정 값의 저장 등).
3. 메모리를 효율적으로 사용해야 하는 경우
   배열은 요소마다 추가적인 메모리를 필요로 하지 않으므로, 메모리 사용을 최소화할 수 있음. 메모리 사용량을 예측하기 쉽고 관리하기 편함.

연결 리스트(Linked List)의 사용이 적합한 경우

1. 데이터 추가 및 삭제가 빈번한 경우
   연결 리스트는 노드 사이의 연결만 변경하면 되기 때문에, 요소의 추가나 삭제가 매우 간단하고 효율적임.
2. 데이터의 크기가 미리 예측하기 어려운 경우
   연결 리스트는 데이터의 크기가 동적으로 변할 수 있으므로, 데이터의 크기를 미리 알 수 없거나 데이터가 계속 추가될 것으로 예상되는 경우에 유리함.
3. 메모리 할당이 동적으로 이루어져야 하는 경우
   연결 리스트는 필요할 때마다 메모리를 할당하므로, 사용 가능한 메모리 크기가 변동적인 환경에서 유리함 (ex. 사용자 입력에 따라 데이터의 양이 변하는 경우).