Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 완탐
- 유니온파인드
- Union Find
- 그리디
- 코딩테스트
- DFS
- 코드트리
- 트러블슈팅
- JUnit
- SWEA
- BFS
- Spring
- 다익스트라
- SSAFY
- 코딩테스트실력진단
- 알고리즘
- 기본유형
- 그래프
- 다시보기
- 싸피
- 완전탐색
- 자바
- 부분수열의합2
- 알고리즘기본개념
- DP
- 코테
- Java
- JPA
- database
- 백준
Archives
- Today
- Total
HwangHub
[가벼운 고민] linked list에서 순서에 관계없이 노드를 추가할라면 어디에 추가하는게 가장 효율적인가? 본문
CS-STUDY/자료구조 & 알고리즘
[가벼운 고민] linked list에서 순서에 관계없이 노드를 추가할라면 어디에 추가하는게 가장 효율적인가?
HwangJerry 2023. 11. 7. 14:47일반적으로 linked list의 중간에 삽입하는건 번거롭다는 것은 우리가 쉽게 알고 있다.
그렇다면 "연결리스트에서 순서 관계 없이 노드를 추가하는 효율적인 위치는 양 끝이다." 라는 명제는 참일까?
그렇지 않다.
연결 리스트의 크기가 n개라고 했을 때, 리스트의 tail노드 위에 붙이기 위해서는 tail 노드를 가리키는 포인터가 있지 않은 이상 n번의 탐색을 통해 tail 노드를 찾아야 할 것이다. 이 과정에서 불필요한 오버헤드가 발생한다. FIFO 구조라면 불가피하게 이렇게 해야 하겠지만 '순서 관계 없이'라는 조건이라면 head 노드의 앞에 붙이는 것이 가장 효율적이다.
이처럼 항상 자료구조를 이해하여 그 연산의 비용을 고려하며 생각해야 한다.
'CS-STUDY > 자료구조 & 알고리즘' 카테고리의 다른 글
자바로 알고리즘 시작하기 1 - 알고리즘 왜 하나요? (0) | 2024.01.07 |
---|---|
BST의 시간복잡도 O(log N) 증명하기 (1) | 2024.01.07 |
다이나믹 프로그래밍 (0) | 2023.10.18 |
그리디 알고리즘 (1) | 2023.10.09 |
Shorten-Time Techniques : LR 테크닉 (0) | 2023.10.09 |
Comments