Array vs Linked List
배열이란?
배열은 연관된 데이터를 모아서 관리하기 위해서 사용되는 데이터 타입입니다. 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리할 수 있습니다.
위의 예시를 보면 크기가 4인 과일에 대한 배열이 있습니다.
사과, 바나나, 포도, 수박은 배열에 저장된 값이고(Value) 그리고 밑에 있는 숫자들은 Value를 식별하는 Index입니다. 배열의 값을 찾기 위해 Index를 사용합니다!
그렇기 때문에 찾고자 하는 element의 인덱스 값을 알고 있다면 Big-O(1)에 해당 element로 접근할 수 있습니다. 즉 random access가 가능하다는 장점이 있습니다.
random access란? - 인덱스 번호를 이용해서 빠르게 접근하는 것 임의 접근이라고 표현합니다.
배열의 한계
배열로 모든 것을 해결할 수는 없습니다.
만약 Index 2의 값을 삭제한다면 어떻게 될까요?
Index 2 원소에 접근하여 삭제를 완료한뒤(O(1)), 빈 공간을 채우기 위해서 삭제한 element보다 큰 인덱스를 갖는 원소를 shift해줘야 하는 비용이 발생하고 이 경우의 시간 복잡도는 O(n)이 됩니다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 됩니다.
삽입의 경우도 마찬가지입니다. 만약 첫번째 자리에 새로운 원소를 추가하고자 한다면 모든 원소들의 인덱스를 1 씩 shift 해줘야 하므로 이 경우도 O(n)의 시간을 요구하게 됩니다.
연결 리스트란?
위의 그림을 보시면 연결 리스트는 자료를 가진 Data 와 다음 노드를 연결하는 Link 로 이루어진 노드로 이루어져 있습니다.
배열과 달리 필요한 만큼 메모리를 동적으로 할당 받아서 만드는 특징을 가지고 있습니다.
그리고!
위의 배열의 한계점을 해결하기위한 자료구조가 바로 연결 리스트입니다!
각각의 노드들은 자기 자신 다음에 어떤 노드인지만을 기억하고 있습니다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수있습니다.
연결 리스트의 한계
하지만 연결 리스트에도 문제가 있습니다. 원하는 위치에 삽입을 하고자 하면 원하는 위치를 찾는 과정에 있어서 첫번째 원소부터 다 확인을 해봐야 하는 것입니다.
배열과 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문입니다.
그래서 삽입하고 정렬하는 것과 마찬가지입니다. 이 과정 때문에 어떠한 원소를 삭제 또는 추가하고자 했을 때 그 원소를 찾기 위해서 O(n)만큼의 시간이 추가적으로 발생하게 됩니다.
결국 linked list 자료구조는 search 에도 O(n)의 time complexity 를 갖고 삽입, 삭제에 대해서도 O(n)의 time complexity 를 갖습니다. 그렇다고 해서 아주 쓸모없는 자료구조는 아니기때문에 우리가 학습하는 것입니다. 이 Linked List 는 Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러납니다.