Array VS LinkedList

Array 

배열은 한 번 정해지면 바꿀 수 없는 정해진 데이터 공간이다. 

 

배열의 장점은 원소에 즉시 접근할 수 있다. ex) array[0]

원소의 순서는 0부터 시작하고 이것을 인덱스라고 한다.

 

단점은 원소를 중간에 삽입/삭제를 할 때 모든 원소를 전부 옮겨야 한다.

배열의 길이 N 만큼 옮겨야 하므로 O(N)의 시간 복잡도를 갖는다.

 

원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 비효율적인 자료구조이다.

 

 

 

LinkedList

링크드리스트는 각 화물칸이 연결 되어있는 화물 열차와 같다.

연결 고리는 포인터와 같고, 각 화물 칸은 노드와 같다.

리스트는 크기가 정해지지 않은 데이터 공간이다.

연결 고리로 이어주기만 하면, 자유자재로 늘어난다.

 

링크드리스트의 장점은 중간에 삽입/삭제를 할 떄 앞 뒤의 포인터만 변경하면 된다.

또한 모든 공간이 차면 맨 뒤의 노드만 추가하면 된다.

따라서 O(1)의 시간 복잡도를 갖는다.

 

단점은 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 하므로 최악의 경우 O(N)의 시간 복잡도를 갖는다.

 

 

 

 

해서 데이터에 접근하는 경우가 빈번하다면 Array를 사용하고

삽입/삭제가 빈번하다면 LinkedList를 사용하는 것을 추천한다.

 

하지만! 파이썬의 배열(list)는 array로 구성되어 있지만 내부적으로 동적 배열이라는 것을 사용해서 append메소드를 사용해 길이를 늘려도 O(1)의 시간 복잡도가 걸리도록 설계했다.

그래서 파이썬의 배열은 링크드리스트로 사용할 수도 있고 배열로도 사용할 수 있게 만든 효율적인 자료구조이다.