[자료구조]싱글 링크드 리스트(단순 연결 리스트)의 시간 복잡도

싱글 링크드 리스트(단순 연결 리스트) 연산들의 시간 복잡도를 알아 보자.

 

접근 시간 복잡도

• 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 된다
• 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 가야된다.
• 최악의 경우 시간 복잡도 : O(n)

 

탐색 시간 복잡도

• 배열을 탐색할 때와 같은 방법으로 구한다.
• 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 데이터를 찾는다.
• 이를 선형 탐색이라고 한다.
• 링크드 리스트안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막 노드에 있는 최악의 경우 n개의 노드를 다 봐야한다.
• 최악의 경우 시간 복잡도 : O(n)

 

삽입 / 삭제 시간 복잡도

• 삽입, 삭제는 그냥 삽입, 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만 수정한다.
• 그러므로 이 연산들이 실행되는데 걸리는 시간은 특정 값에 비례하지 않고 항상 일정하다.
• 따라서 시간 복잡도 : O(1)

반응형

현실적인 삽입 / 삭제 시간 복잡도

• 삽입과 삭제는 현실적으로 특정 노드를 넘겨줘서 이 노드 다음 순서에 데이터를 삽입/ 삭제한다
• head와 tail노드를 제외한 나머지 노드들은 탐색이나 접근 연산을 통해서 가지고 와야한다.
• 현실적인 삽입/삭제 시간 복잡도 = 원하는 노드에 접근/탐색 + 삽입/삭제 = O(n+1)

 

삽입/삭제 연산 특수 경우 시간 복잡도

• head와 tail노드와 관련있는 삽입이나 삭제연산들은 시간복잡도가 O(1)
• head와 tail노드로 접근/탐색하는 시간도 있으니 현실적으로 시간 복잡도는 O(1+1)이다.
• 단 tail노드를 접근 + 삭제 할때는 시간 복잡도가 O(n+1)이다. 
• 이유는 tail 노드를 삭제하기 위해서는 바로 전 노드가 필요하다. 이 노드를 찾으려면 head 노드에서 n - 2번 다음 노드로 가야 된다. 접근하는데 O(n - 2), 그러니까 O(n)의 시간 복잡도가 걸린다. 접근한 노드에서 다음 노드를 삭제하는 건 O(1)이 걸리니까 tail 노드 전 노드에 접근해서 tail 노드를 삭제하는 건 O(n+1), 결국 O(n)이다.

연산	링크드 리스트 시간 복잡도
접근	O(n)
탐색	O(n)
삽입	O(1)
삭제	O(1)
원하는 노드에 접근/탐색 + 삽입	O(n + 1)
원하는 노드에 접근/탐색 + 삭제	O(n + 1)
가장 앞에 접근 + 삽입	O(1 + 1)
가장 앞에 접근 + 삭제	O(1 + 1)
가장 뒤에 접근 + 삽입	O(1 + 1)
뒤에서 두번째 노드(tail노드 전 노드)접근 + 삭제	O(n + 1)