🧑💻
LinkedList와 Array는 서로 많이 비교가 되곤 한다. 그렇다면 이 둘에 대해 알아보자!
먼저, Array는 파이썬의 리스트인데, Array가 가지고 있는 값에 대한 접근이 쉬운 자료구조이다. 하지만 삽입이 어렵다는 단점이 있다.
Array는 파이썬의 리스트이기 때문에 이 포스트에서 편의상 배열 Array를 리스트라고 칭하겠다. 그렇다면 리스트의 원소를 조회하는 것의 시간 복잡도를 생각해보자. 리스트의 특정 값에 접근을 하기 위해서는 그 값에 대한 인덱스 번호를 알고 있으면 바로 접근이 가능하다. 그렇기 때문에, 위와 같이 list [3]으로 list의 원소 4에 접근이 가능해진다. 이는 시간 복잡도가 O(1)이 되므로, 접근이 굉장히 빠르다는 의미이다. 이 리스트는 삽입이 어렵다는 단점이 있다고 했는데, 그 이유는 아래와 같다.
해당 list는 인덱스 번호가 0부터 5까지인 리스트이다. 4번째 줄에서 없는 인덱스 번호인 6에 접근을 하여 7을 저장하려고 하니 'index out of range' 범위 밖 인덱스에 할당한다는 에러 문구가 뜨는 것을 볼 수 있다. 이렇듯 리스트는 공간이 차 있으면(기존 인덱스에는 가능!) 더 이상 삽입이 어려워진다. 이때는 새로운 메모리 공간을 할당받지 않는다면 저런 에러 문구를 구경할 수 있을 것이다.
다음은 LinkedList, 연결 리스트이다. 연결 리스트는 Array처럼 파이썬에서 제공하는 내장 함수가 있는 것이 아니기 때문에 직접 구현이 필요한 자료구조이다. 이는 말 그대로 리스트가 연결된 형태를 띠고 있는데, 각 리스트를 연결하는 구조이기 때문에 만약 모든 공간이 다 찼더라도 맨 뒤에 하나를 동적으로 추가하면 된다. 하지만, 연결 리스트는 리스트(Array)와 반대로 값에 접근하는 것에 있어서는 리스트보다는 비효율적이다.
이유를 설명하면, 연결 리스트는 각자의 데이터를 담고 있는 공간이 따로 있고 그 공간끼리 서로 고리로 연결이 되어있는 방식이기에 값에 접근을 하기 위해서는 최대 N번을 수행해야 원하는 값에 접근이 가능할 것이다. 그래서 연결 리스트에서 특정 값에 접근을 하기 위해서는 시간 복잡도를 O(N)으로 나타낼 수 있다. 그렇다면 이제 연결 리스트를 어떻게 파이썬에서 구현할지 살펴보도록 하겠다.
🧑💻
리스트(Array)와 연결 리스트에 대해 알아보았다. 어떤 것이 좋다는 없지만 용도에 따라 더 좋은 것은 있다. 만약, 데이터에 접근하는 경우가 빈번하다면 Array를 사용하고, 삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋을 것이다.
