싱글리 링크드 리스트 연산의 시간 복잡도

 

---

 

싱글리 링크드 리스트의 구조

 

싱글리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자

 

---

 

싱글리 링크드 리스트의 접근 연산

 

링크드 리스트의 접근 연산은 해당 노드에 바로 접근이 불가하다

 

head에서부터 차근차근 다음 노드로 가서 원하는 노드에 접근을 해야 한다

 

인덱스 x에 있는 노드에 접근하려면 head에서부터 x번 가야 한다

 

원하는 노드에 접근하는데 걸리는 시간이 몇 번째 인덱스인지에 비례하는 것이다

 

링크드 리스트 안에 있는 노드의 수를 n이라고 하면

 

마지막 노드에 접근하려면 head에서부터 총 n-1번을 가야 한다

 

그러므로 접근 연산은 최악의 경우 O(n)의 시간 복잡도를 갖는다

 

---

 

싱글리 링크드 리스트의 탐색 연산

 

링크드 리스트의 탐색 연산은 선형 탐색을 이용한다

 

가장 앞에서부터 다음 노드를 하나씩 보면서 원하는 데이터가 있을 때까지 탐색한다

 

최악의 경우는 찾으려는 데이터가 없거나 tail에 있는 경우로

 

이 때는 n개의 노드를 모두 봐야 한다

 

그러므로 탐색 연산은 O(n)의 시간 복잡도를 갖는다

 

---

 

싱글리 링크드 리스트의 삽입, 삭제 연산

 

링크드 리스트의 삽입, 삭제 연산은 삽입, 삭제할 인덱스 주변 노드들의 레퍼런스만 수정하면 된다

 

삽입, 삭제할 노드가 어떤 순서에 있는 노드든 상관없이 걸리는 시간은 변하지 않고 항상 일정하다

 

따라서 삽입, 삭제 연산은 O(1)의 시간 복잡도를 갖는다

 

---

 

정리

 

 

---

 

조금 더 생각해보자

 

삽입, 삭제 연산은 O(1)의 시간 복잡도를 갖지만

 

삽입, 삭제를 하기 위해서는 삽입, 삭제할 특정 노드를 파라미터로 넘겨주어야 한다

 

따라서 삽입, 삭제할 노드를 먼저 탐색, 접근 연산을 통해서 가져와야 한다

 

탐색, 접근 연산은 O(n)의 시간 복잡도를 갖고

 

삽입, 삭제 연산 자체는 O(1)의 시간 복잡도를 가지므로

 

총 O(n+1)의 시간 복잡도를 갖는다

 

즉, 특정 노드에 삽입, 삭제를 하는 연산은 사실상 O(n)의 시간 복잡도를 갖게 된다

 

 

---

 

특수한 경우

 

특정 노드에 삽입, 삭제를 하는 연산은 O(n)의 시간 복잡도를 갖지만

 

그 특정 노드가 head나 tail이면 이야기는 달라진다

 

링크드 리스트는 head와 tail의 정보를 저장하고 있기 때문에

 

head, tail 노드에 한 번에 접근할 수 있다

 

따라서 head, tail에 삽입, 삭제를 하는 경우 

 

head, tail 노드에 한 번에 접근하여 삽입, 삭제를 하는 시간을 고려하면

 

시간 복잡도는 O(1+1) => O(1)이 된다

 

---

 

tail의 삭제 연산

 

위에서 head, tail 노드의 삽입, 삭제 연산은 O(1)이라고 했지만

 

사실 tail 노드의 삭제 연산은 O(1)이 아니다

 

tail 노드를 삭제하기 위해서는 바로 전 노드가 필요하다

 

바로 전 노드에서 연결을 끊어줘야 하기 때문이다

 

삭제할 tail노드의 바로 전 노드에 접근하기 위해서는 O(n-2) => O(n)의 시간 복잡도가 걸린다

 

노드를 삭제하는 연산은 O(1)의 시간 복잡도를 가지므로

 

tail 노드를 삭제하기 위해서는 O(n+1) => O(n)의 시간 복잡도를 가진다

 

---

 

최종 정리

 

 

---