알고리즘 개선
일반적으로 단일 연결 리스트에서 중간 삽입과 삭제를 생각해보면 O(n)의 시간 복잡도를 가지고 있는 걸 알 수 있습니다.
하나의 노드는 바로 다음의 노드와 연결되어 있기 때문에 원하는 위치까지 탐색하려면 n 번의 탐색 횟수가 필요하기 때문이죠.
세타 시간
"세타"는 시간 복잡도의 대략적인 상한을 의미하는 표기법으로, Big-O와 유사하지만 더 정확하게 시간 복잡도를 나타낼 수 있다고 합니다. Big-O는 상한을 나타내는 반면, 세타는 상한과 하한을 모두 나타냅니다.
이번 포스팅에서 의미하는 세타 시간 복잡도로의 개선은 최악의 경우에서도 선형 시간 내에 연산이 수행된다는 것을 의미합니다.
예를 들어, 단일 연결 리스트에서 중간에 새로운 노드를 삽입하는 경우, 최악의 경우 시간 복잡도는 O(n)이 됩니다. 그러나, 리스트를 순회하지 않고도 삽입 위치를 빠르게 찾을 수 있는 알고리즘을 사용한다면, 시간 복잡도를 O(n)보다 빠른 세타로 줄일 수 있습니다.
세타로 만드는 방법은 여러 가지가 있다고 하지만, 일반적으로는 리스트 내에서 노드를 찾을 때 이진 검색을 사용하거나, 리스트를 일정한 크기의 블록으로 나누어 각 블록의 시작 노드와 끝 노드를 기록해 두어 블록 단위로 검색하는 방법 등이 있습니다. 이러한 알고리즘을 사용하면, 최악의 경우에서도 시간 복잡도가 선형 시간 내에 수행된다고 합니다
이중 연결 리스트 적용
이번 포스팅을 정리하면서 생각한 점은 단일 연결 리스트가 아닌 이중 연결 리스트로 코드를 구현하는 방법입니다.
이중 연결 리스트는 각 노드가 다음 노드와 이전 노드의 포인터를 모두 가지고 있기 때문에, 양방향 탐색이 가능합니다. 따라서 중간 노드에 대한 삽입 및 삭제가 적어도 세타 시간 안에 수행될 수 있습니다.
과정
중간 삽입
- 새로운 노드를 생성합니다.
- 새로운 노드의 다음 포인터를 중간에 삽입할 위치의 다음 노드로 설정합니다.
- 새로운 노드의 이전 포인터를 중간에 삽입할 위치의 이전 노드로 설정합니다.
- 중간에 삽입할 위치의 이전 노드의 다음 포인터를 새로운 노드로 설정합니다.
- 중간에 삽입할 위치의 다음 노드의 이전 포인터를 새로운 노드로 설정합니다.
중간 삭제
- 중간에 삭제할 노드의 이전 노드를 찾습니다.
- 중간에 삭제할 노드의 다음 노드를 찾습니다.
- 중간에 삭제할 노드의 이전 노드의 다음 포인터를 중간에 삭제할 노드의 다음 노드로 설정합니다.
- 중간에 삭제할 노드의 다음 노드의 이전 포인터를 중간에 삭제할 노드의 이전 노드로 설정합니다.
- 중간에 삭제할 노드를 삭제합니다.
위의 방법을 통해 중간 삽입과 삭제를 세타 시간 안에 구현할 수 있게 코드를 개선할 수 있습니다. 그러나 이중 연결 리스트의 구현은 단일 연결 리스트보다 복잡하며, 단순히 생각해도 역방향으로 향하는 리스트를 하나 더 만들어야 해 메모리를 더 많이 차지하게 됩니다.
