Array
가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다
단점으로는 삽입 삭제 시 shift 연산을 해야 함으로 O(n)의 시간 복잡도를 갖는다.
Linked List는 이러한 shift 연산을 하지 않기위해 고안된 자료구조이다.
이전 요소와 현재 요소 다음 요소에 대해 refernce 정보로 연결되어 있어 요소 추가, 삭제시 해당 부위에 연결 부분만 수정하면 된다.
하지만 요소를 찾기 위해서는 처음부터 탐색해 나아가야하기 때문에 삽입, 삭제 시 Array와 마찬가지로 O(n)의 시간 복잡도를 갖는다.
결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고, 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖는다. 이렇게 보면 Linked list의 필요성이 느껴지지 않는다. 하지만 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.
ㄱH ㅂrㄹ ㅈr