Linked list의 장점
648
投稿した質問数 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
112
2
노션 공유 부탁드립니다.
0
54
2
노션 공유가 안됩니다!
0
148
2
프로세스가 많아질수록 segment table도 많아지는 건가요?
1
65
2
노션 공유가 사라졌습니다.
0
160
2
post 요청
0
50
1
http
0
58
1
mutex, semaphore와 deadllock
0
94
3
실행중인 프로세스는 메모리를 연속적으로? 아니면 불연속적으로 사용하나요?
0
70
1
노션 공유 요청 드립니다.
0
121
1
노션 공유 요청드립니다.
0
82
1
Dynamic Array와 Linked List의 시간복잡도에 대해서..
0
111
1
노션
0
106
1
질문이있습니다 선생님!
0
105
1
질문이있습니다 선생님!
0
95
1
질문이있습니다 선생님!
0
87
1
질문이있습니다 선생님!
0
160
2
질문이있습니다 선생님!
0
147
2
질문이 있습니다 선생님!
1
195
2
질문이 있습니다 선생님!
0
118
1
질문이있습니다 선생님!
0
80
1
질문이 있습니다 선생님!
0
102
1
질문이 있습니다 선생님!
0
85
1
물리적 메모리에 연속적으로 저장하지 않는 이유
0
125
1