LinkedList
-
Queue in SwiftComputer Science/DataStructure 2021. 2. 5. 14:45
- 선형 자료구조 - FIFO (선입선출) - 구현 - LinkedList - DoubleStack Swift에서는 Queue와 LinkedList를 기본 자료구조로 제공하지 않고 있는데요, array를 사용해 queue를 만들면 enqueue 작업이 O(n)이 걸려서 비효율적입니다. 특히 코딩테스트 문제를 풀다보면 queue가 필요한 상황이 많기 때문에 미리 알아두고 구현해둔다면 좋겠죠? 오늘은 간단하게 Queue 에 대해 알아보고 swift에서는 어떻게 구현할 수 있을지 알아보겠습니다. LinkedList를 사용한 구현과, stack 두 개를 사용한 doubleStack 구현을 알아볼텐데요, LinkedList는 제가 구현해서 그런지 doubleStack과 복잡도 차이가 꽤 나더라구요... 😢 코딩테..
-
Array vs LinkedListComputer Science/DataStructure 2019. 12. 16. 15:53
둘다 선형 방식의 자료구조이다. 배열(Array): 인덱스를 가지고 있는 데이터의 모음. 리스트(List): 순서가 있는 데이터의 모음. 각 원소는 다음이 어떤 원소인지만 알고 있음. 배열은 인덱스를 가지고 있기 때문에 인덱스를 알고 있으면 원소에 직접 접근이 가능해 빠르게 조회할 수 있다.(O(1)) 대신 인덱스는 고정되어야 하고 만약 엘리먼트가 삭제되더라도 빈 공간으로 남겨둬야 한다. → 이는 메모리 낭비를 초래할 수 있고, 엘리먼트가 비었는지 확인하는 로직이 필요하다. 리스트는 인덱스가 없기 때문에 각각의 원소는 다음 원소만 알고 있기 때문에 순차적으로 접근해야 한다. (O(n)) 인덱스가 고정이 아니고 순서 정도의 의미만 지니기 때문에 추가, 삭제가 빠르다.(O(1)) → 하지만 추가 삭제를 위한..
-
Linked ListComputer Science/DataStructure 2019. 11. 19. 00:27
- 선형 자료구조 - 순차적 접근방식 ( O(n) ) - 삽입, 삭제가 빠르다 ( O(1) ) - 다음 노드를 가리키는 주소를 저장할 공간 필요 Linked List는 순차적으로 모인 데이터들의 모음이다. 흔히 각각의 데이터를 Node(노드), 각 노드는 다음 차례의 노드의 reference(주소)를 갖고 있다. 대표적으로 두 가지 유형이 있는데, Singly Linked List: 내 다음 노드(next node)의 주소만을 갖고 있다. Double Linked List: 내 이전(previous)과 다음의 주소를 갖고 있다. Linked List를 사용하기 위해서는 시작과 끝의 주소를 알아야 하는데 이를 head와 tail이라 부른다. Performance Linked List의 대부분의 연산은 O(..