Computer Science/Data Structure3 [Swift] Queue 구현해보기 [Swift] Queue 구현해보기 Swift에서는 Queue 자료구조를 기본적으로 지원하지 않는다. Array의 배열의 맨 앞 원소를 지워주는 removeFirst()를 지원하긴 하지만 O(N) 시간복잡도를 갖는다. 제네릭 타입을 가지고, 시간 복잡도가 O(1)인 Queue를 구현해보자. struct Queue { private var inputStack = [T]() private var outputStack = [T]() mutating public func append(_ x: T) { inputStack.append(x) } mutating public func pop() -> T? { var top: T? while !(inputStack.isEmpty) { let x = inputStack... 2023. 4. 28. [Swift] 양방향 Linked List 구현해보기 [Swift] 양방향 Linked List 구현해보기 정의 단일 연결 리스트와 다른 점 이전 노드를 나타내는 포인터(prev)가 추가되었고, 리스트 자체의 tail도 있어 역방향 탐색이 절반정도 좋아짐 시간 복잡도 구현 class Node { var data: T var prev: Node? var next: Node? init(data: T, prev: Node? = nil, next: Node? = nil) { self.data = data self.prev = prev self.next = next } } class DoublyLinkedList { private var head: Node? private var tail: Node? init(head: Node? = nil, tail: Node? .. 2023. 4. 14. [Swift] 단방향 Linked List 구현해보기 [Swift] 단방향 Linked List 단방향 링크드 리스트는 데이터를 갖고 있는 노드들을 포인터로 선형적으로 연결해 사용하는 자료구조 삭제와 삽입에 O(1)의 시간 복잡도가 걸리기 때문에 빈번하게 삽입/삭제가 필요한 상황에 유용 하지만 원하는 노드까지의 '탐색'은 O(N)이 걸림 따라서 배열처럼 동시에 인덱스를 통한 Random Access는 불가능하고, 처음부터 원하는 데이터가 나올 때까지 탐색을 진행해야 하기 때문에 O(N)의 시간 복잡도가 요구된다는 단점이 있음 /// /// data: 실제로 저장할 데이터 /// next: 현재 노드의 다음 노드를 저장할 데이터 /// class Node { let data: T var next: Node? init(data: T, next: Node? = .. 2023. 4. 13. 이전 1 다음
