링크드 리스트
싱글 링크드 리스트
- 데이터를 순서대로 저장해준다.
- 요소를 계속 추가 가능하다.
💡 노드들은 메모리상에서 여기저기 흩어져있다.
접근연산
O(n) : 무조건 처음부터 살펴봐야한다.
탐색연산
O(n) : 배열과 비슷하며 선형탐색으로 처음부터 하나씩 비교해봐야한다.
삽입/ 삭제 연산
O(1): 레퍼런스만 수정하는 연산으로서 순서에 상관없이 걸리는 시간이 항상 일정하다.
| 연산 | 시간 복잡도 |
| 접근 | O(n) |
| 탐색 | O(n) |
| 삽입 | O(1) |
| 삭제 | O(1) |
하지만! 내가 지우고자 하는 노드를 찾아와야하기 때문에 탐색과 접근 연산이 필요하다 그렇다면 위의 시간 복잡도는 아래와 같이 된다.
| 연산 | 링크드 리스트 |
| 접근 | O(n) |
| 탐색 | O(n) |
| 원하는 노드에 접근 또는 탐색 + 삽입 | O(n+1) |
| 원하는 노드에 접근 또는 탐색 + 삭제 | O(n+1) |
head와 tail의 삽입 삭제 연산
head와 tail 노드는 바로 접근 해서 삽입및 삭제가 가능하기 때문에 O(1+1)의 시간복잡도를 갖지만 이중에서 예외는 tail을 삭제 할때 인데 왜냐면 tail노드의 바로 전 노드를 알아야 삭제가 가능하다. 그렇기에 이 경우에는 O(n+1)의 시간 복잡도를 가진다.
| 연산 | 링크드리스트 |
| 가장 앞에 접근 + 삽입 | O(1+1) |
| 가장 앞에 접근 + 삭제 | O(1+1) |
| 가장 뒤에 접근 + 삽입 | O(1+1) |
| 뒤에서 두 번째 노드 (tail 노드 전 노드) 접근 + 삭제 | O(n+1) |
더블 링크드 리스트
- 싱글 링크드 리스트는 다음 노드에 대한 정보만 가지고 있지만 더블 링크드 리스트는 이전 노드와 다음 노드에 대한 정보 모두를 가지고 있다.
접근 연산 & 탐색 연산
O(n) : 싱글 링크드 리스트와 같이 무조건 처음부터 살펴봐야한다.
삽입 연산 & 삭제 연산
O(1) : 싱글 링크드 리스트와 같이 레퍼런스만 수정하는 연산으로서 순서에 상관없이 걸리는 시간이 항상 일정하다.
| 연산 | 링크드 리스트 |
| 접근 | O(n) |
| 탐색 | O(n) |
| 삽입 | O(1) |
| 삭제 | O(1) |
하지만! 싱글 링크드 리스트와 같이 내가 지우고자 하는 노드를 찾아와야하기 때문에 탐색과 접근 연산이 필요하다 그렇다면 위의 시간 복잡도는 아래와 같이 된다.
| 연산 | 링크드 리스트 |
| 접근 | O(n) |
| 탐색 | O(n) |
| 원하는 노드에 접근 또는 탐색 + 삽입 | O(n+1) |
| 원하는 노드에 접근 또는 탐색 + 삭제 | O(n+1) |
head와 tail의 삽입 삭제 연산
head와 tail 노드는 바로 접근 해서 삽입및 삭제가 가능하기 때문에 O(1+1)의 시간복잡도를 갖는다. 싱글 링크드 리스트와 다르게 예외의 경우가 없다.
⇒ 만약 tail 노드를 삭제 해야한다면 싱글 링크드 리스트보다 더블 링크드 리스트가 효율적이라고 볼수있다.
| 연산 | 싱글리 링크드 리스트 | 더블리 링크드 리스트 |
| 가장 앞에 접근 + 삽입 | O(1+1) | O(1+1) |
| 가장 앞에 접근 + 삭제 | O(1+1) | O(1+1) |
| 가장 뒤에 접근 + 삽입 | O(1+1) | O(1+1) |
| 가장 뒤에 접근 + 삭제 | O(n+1) | O(1+1) |
💡 만약 메모리 공간을 조금이라도 더 효율적으로 쓰고 싶다면 싱글 링크드 리스트는 공간을 더블 링크드 리스트보다 절반 정도 밖에 차지를 안하기 때문에 더 효율적이라고 할수있다.