Linked list의 장점
654
작성한 질문수 2
선생님 안녕하세요. Linked list의 시간 복잡도에서 질문이 있습니다.
Linked list는 이론상 삽입 삭제가 O(1)이고, 실제 구현해보면 조회의 과정이 필요하기 때문에 O(n) 이라는 점 잘 이해했습니다.
그러면 Array가 Linked list에 비해
조회는 빠르고 (O(1) vs O(n))
삽입 삭제는 동일하며 (O(n))
주소를 저장 할 필요가 없어 동일한 양의 데이터를 저장시 필요한 메모리도 적습니다. (Array가 꽉 찼다고 가정)
이러면 결국 Linked list를 써야하는 경우가 얼마만큼의 데이터가 들어올지 예측을 할 수 없을 때 말고 다른 경우가 있나요??
감사합니다.
답변 1
1
안녕하세요 준환님.
linked list는 어떻게 구현하냐에 따라서 무궁무진한 활용도가 있습니다.
트리나, 그래프 같은 다른 자료구조를 구현하는데 사용할 수 도 있고,
특정 상황에서는 삽입삭제를 O(1)으로 지속적으로 사용할 수 도 있습니다.
current_node를 활용해서, 한 번 삽입삭제 했던 위치를 계속 가리키고 있음으로써, 실질적인 O(1)가 될 수 있습니다.
또한, deque 자료구조의 경우 (queue강의에서 설명해드릴텐데) linkedlist로 구현하는게 일반적입니다.
질문에 대한 답이 됐을까요~?
또 궁금하신점 있으시면 언제든지 질문주세요
노션 접근이 안됩니다 ㅠㅠ
0
120
2
노션 공유 부탁드립니다.
0
58
2
노션 공유가 안됩니다!
0
152
2
프로세스가 많아질수록 segment table도 많아지는 건가요?
1
72
2
노션 공유가 사라졌습니다.
0
163
2
post 요청
0
56
1
http
0
64
1
mutex, semaphore와 deadllock
0
97
3
실행중인 프로세스는 메모리를 연속적으로? 아니면 불연속적으로 사용하나요?
0
72
1
노션 공유 요청 드립니다.
0
124
1
노션 공유 요청드립니다.
0
87
1
Dynamic Array와 Linked List의 시간복잡도에 대해서..
0
115
1
노션
0
110
1
질문이있습니다 선생님!
0
109
1
질문이있습니다 선생님!
0
99
1
질문이있습니다 선생님!
0
93
1
질문이있습니다 선생님!
0
163
2
질문이있습니다 선생님!
0
152
2
질문이 있습니다 선생님!
1
198
2
질문이 있습니다 선생님!
0
124
1
질문이있습니다 선생님!
0
88
1
질문이 있습니다 선생님!
0
109
1
질문이 있습니다 선생님!
0
91
1
물리적 메모리에 연속적으로 저장하지 않는 이유
0
133
1