LinkedList 개념과 특징

[LinkedList의 특징]

• 총 길이를 알수 없어서 노드를 순회해야한다.
• 사이클이 발생할 수도 있다.

 

[LinkedList 관련 문제의 특징]

링크드 리스트 문제 중, 링크드 리스트의 head를 리턴해야하는 경우가 있다.

이땐, head 노드를 next로 하는 dummy 노드를 선언해놓고 링크드 리스트에서 여러 작업을 하고, 

dummy.next를 리턴하는 식으로 하면 된다.

 

링크드 리스트의 고난도 문제들은 대부분, next의 방향을 바꿔야할 때가 있다.

방향을 바꾸기 위해선 기존 next를 저장할 temp 노드가 필요하다.

 

여기서 더 나아가, 링크드 리스트의 크기를 알아야 해결할 수 있는 문제들이 있다.

예를 들어, 링크드 리스트의 가운데 노드를 찾아야하는경우, 링크드 리스트에 순환이 있는지 파악해야하는경우 등..

이런 문제들은 투 포인터를 사용하면 해결할 수 있다.

투 포인터를 활용해 문제를 풀면, Stack이나 Deque를 사용해서 푸는것보다 공간복잡도가 더 효율적이다.

투 포인터는 slow 와 fast 이다.

slow는 방향을 따라 노드를 한칸씩 옮겨가며 가리키는 포인터고,

fast는 방향을 따라 노드를 두칸씩 옮겨가며(slow보다 두배 빠르게) 가리키는 포인터이다.

 

 

[LinkedList와 배열 비교하기]

배열과 링크드 리스트 모두 삽입/삭제할 위치를 모르는 경우라면, 위치를 찾기 위한 탐색 시간이 추가되므로 시간 복잡도가 같아질 수 있다. 하지만 두 자료구조는 각각의 구조적 특성으로 인해 삽입과 삭제에서 차이를 보인다.

배열과 링크드 리스트에서 삽입/삭제할 위치를 모를 때의 시간 복잡도

1. 위치를 찾는 과정:
   • 배열에서는 임의 접근이 가능하므로, 인덱스를 통해 삽입/삭제할 위치를 빠르게 찾을 수 있다.
   • 링크드 리스트에서는 특정 위치를 찾기 위해 처음부터 순차 탐색해야 하므로, 위치를 찾는 데 최악의 경우O(N)의 시간이 걸린다.
2. 삽입/삭제 자체의 시간 복잡도:
   • 배열에서 중간 위치에 삽입이나 삭제를 하려면, 찾은 위치 이후의 모든 요소를 이동해야 하므로 삽입/삭제 자체가 O(N)이다.
   • 링크드 리스트에서는 위치를 찾은 후, 노드를 삽입하거나 삭제할 때 포인터만 수정하면 되므로 O(1)의 시간 복잡도로 삽입과 삭제가 가능하다.

종합적인 시간 복잡도 비교

• 배열: 위치를 모를 경우, 위치를 찾는 시간 O(1) + 삽입/삭제 O(N) = O(N).
• 링크드 리스트: 위치를 모를 경우, 위치를 찾는 시간 O(N) + 삽입/삭제 O(1) = O(N).

따라서, 위치를 모르는 경우라면 배열과 링크드 리스트 모두 최종적인 시간 복잡도는 O(N)으로 동일하다.

중요한 차이점

• 잦은 삽입과 삭제가 필요한 경우에는, 링크드 리스트가 포인터만 수정하면 되기 때문에 배열보다 효율적이다.
• 반면, 검색과 임의 접근이 빈번한 경우라면 배열이 더 효율적이다. 배열은 특정 인덱스에 직접 접근할 수 있는 임의 접근 성질이 있기 때문에, 위치를 빠르게 찾을 수 있다.