CS/자료구조5 LinkedList 정리 (Single, Double, Circular) Linked List List의 종류 배열(Array) 기반 연결(Link) 기반 배열 기반 리스트 장점 특정 위치의 데이터 조회가 빠르다 단점 데이터의 추가, 삭제 비용이 크다 (다 뒤로 밀거나 앞으로 당기거나..) 크기가 고정되어 있다. 맨 앞에도 쉽게 넣고 싶고, 맨 뒤에도 쉽게 넣고 싶은데..? 그럴 때 사용할 수 있는게 연결 기반 (linked) 리스트 ! 연결 기반 리스트의 종류 단방향 연결 리스트 (Linked List라고 하면 기본으로 이것) 양방향 연결 리스트 (Double Linked List) Circular Linked List (원형 혹은 순환 연결 리스트) Circular single Circular Double 연결 기반 리스트 Node Node는 데이터(Item)과 포인터(P.. 2023. 8. 9. Stack 구현 (Array, LinkedList) Stack LIFO: Last In First Out 리스트의 제한된 형태: 넣고 빼기가 리스트의 한쪽 끝에서만 가능 Notation PUSH POP TOP: 맨 위의 값 리턴. 종류 Array based link based Array based Stack struct stack { var elemensts: [T] = [] var isEmpty: Bool { elemensts.isEmpty } mutating func push(element: T) { elemensts.append(element) } @discardableResult mutating func pop() -> T? { elemensts.popLast() } func peek() -> T? { elemensts.last } } 단순 배열을.. 2023. 8. 4. Queue 구현 (feat. Swift) https://github.com/kodecocodes/swift-algorithm-club/tree/master/Queue 해당 문서를 직접 번역하면서 공부한 내용입니다. BFS를 공부하면서 Queue를 쓰고싶었는데, built-in swift에서의 removieFirst()함수는 배열에서 맨 앞단의 요소를 제거하는 것이기 때문에 O(n)의 시간복잡도가 생긴다. 파이썬에서 deque라이브러리를 통해 O(1)로 맨 앞단의 요소를 제거하는 것처럼 하기 위해서 Swift의 Queue에 대해서 공부해보았다. 단순한 Queue의 구현 public struct Queue { fileprivate var array = [T]() public var isEmpty: Bool { return array.isEmpty .. 2023. 2. 7. Heap 구현 (feat. Swift) https://www.kodeco.com/586-swift-algorithm-club-heap-and-priority-queue-data-structure#toc-anchor-001 해당 원문을 공부하면서 직접 번역한 내용입니다. 정확하지 않은 표현과 필자가 본인의 이해를 위해 추가로 적은 내용들이 있으니 그 점 유의하시기 바랍니다. 우선순위 큐를 구현하는데 Heap을 더 선호하는 이유: https://codingmon.tistory.com/23 Heap은 binary tree(BST와 유사한)와 닮았다. Heap은 트리이고, 모든 노드는 0, 1, 2개의 자식들을 가지고 있다. Heap의 요소들은 그들의 우선 순위에 따라 부분적으로 정렬돼있다. 트리의 모든 노드는 각 노드의 자식들보다 높은 우선순위를 .. 2023. 2. 5. 이전 1 2 다음
