더블리 링크드 리스트 연산의 시간 복잡도

더블리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 더블리 링크드 리스트의 접근, 탐색 연산 더블리 링크드 리스트의 접근, 탐색 연산은 싱글리 링크드 리스트의 접근, 탐색과 똑같다 head 노드부터 하나씩 다음 노드로 가면서 원하는 위치에 접근하거나 원하는 데이터를 가진 노드를 찾는다 시간 복잡도는 리스트의 길이 n에 비례하므로 O(n)을 갖는다 더블리 링크드 리스트의 삽입, 삭제 연산 삽입 연산의 경우 특정 노드가 주어졌을 때, 특정 노드의 앞과 뒤 노드의 레퍼런스만 바꿔주면 된다 링크드 리스트의 길이와 상관없이 항상 일정한 시간이 걸리므로 시간 복잡도는 O(1)을 갖는다 삭제 연산도 마찬가지로 레퍼런스만 바꿔서 연결만 끊어주면 되므로 링크드 리스트의 길이와 상관없이..

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

싱글리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 싱글리 링크드 리스트의 접근 연산 링크드 리스트의 접근 연산은 해당 노드에 바로 접근이 불가하다 head에서부터 차근차근 다음 노드로 가서 원하는 노드에 접근을 해야 한다 인덱스 x에 있는 노드에 접근하려면 head에서부터 x번 가야 한다 원하는 노드에 접근하는데 걸리는 시간이 몇 번째 인덱스인지에 비례하는 것이다 링크드 리스트 안에 있는 노드의 수를 n이라고 하면 마지막 노드에 접근하려면 head에서부터 총 n-1번을 가야 한다 그러므로 접근 연산은 최악의 경우 O(n)의 시간 복잡도를 갖는다 싱글리 링크드 리스트의 탐색 연산 링크드 리스트의 탐색 연산은 선형 탐색을 이용한다 가장 앞에서부터 다음 노드를 하나씩 보면..