[Jungle] Week1. 연결리스트와 배열의 시간 복잡도

연결리스트(Linked List) & 배열(Array)

배열의 시간 복잡도

Access - O(1)

n번째 인덱스에 해당하는 값 찾기 -> 원하는 값이 어딨는지 알고 있다면 빠르다.

Find - O(N)

순차 검색 - 원하는 값 찾을 때까지 하나하나 확인

Insertion / Deletion - O(N)

특정 인덱스에 데이터를 삽입, 삭제하기 위해 기존의 데이터를 옮기는 작업이 필요하다.
최악의 경우) 맨 처음 인덱스에 데이터를 삽입하기 위해서는 모든 데이터를 뒤로 옮겨야 한다.
그러나, 배열의 마지막에 데이터를 삽입/삭제하려면 O(1)의 시간 복잡도

연결 리스트의 시간 복잡도

Access - O(N)

인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 간다. 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 간다.

Find - O(N)

가장 앞 노트부터 다음 노드를 하나씩 보면서 원하는 데이터를 찾는다.(선형 탐색)
찾으려는 데이터가 마지막 노드에 있는 경우 n개의 노드를 다 봐야 한다.

Insertion / Deletion - 최악의 경우: O(N)

처음 노드에 넣는 경우에는 O(1)

Linked list 맨 앞쪽에 요소를 삽입하려면 O(1), 그러나 마지막 인덱스에 요소를 삽입하려면 마지막 노드 검색 O(N) + 삽입 O(1)

Array는 검색이 빠르지만, 삽입/삭제 느림
LinkedList는 검색 느림, 삽입/삭제 빠름

참고)
https://moonsu.tistory.com/58
https://velog.io/@grinding_hannah/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Big-O-%ED%91%9C%EA%B8%B0%EB%B2%95-%EB%A7%81%ED%81%AC%EB%93%9C-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List