Array와 Linked List의 차이

이번 게시글에서는 같은 타입의 데이터를 여러개 저장 할 수 있는 자료구조인 Array와 LinkedList에 대해서 내용을 정리해보려고 한다.

Array

• 배열은 메모리에 연속적으로 저장되기 때문에 처음 주소를 알면 다른 데이터도 쉽게 찾아 갈 수 있고, 이를 임의 접근(Random Access)이 가능하다고 표현 한다.
• 인덱스만 알고 있다면 원소 접근의 시간 복잡도는 O(1)이 된다.
• 배열의 원소를 삽입하거나 삭제할 경우에는 다른 원소들의 인덱스를 1씩 옮겨줘야하기 때문에 시간복잡도는 O(n)이 된다.
• 처음 생성시의 크기에서 늘리거나 줄일 수 없다. (크기를 변경하고 싶다면 아예 새로 만들어야 한다.)

LinkedList

• 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하고 이 노드는 자신 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 가지고 있다.
• 연속적으로 데이터가 존재하는 것이 아니기 때문에 특정 데이터를 탐색하기 위해서는 처음 노드부터 순차적으로 탐색해야 한다. 따라서 LinkedList의 원소 접근시 시간복잡도는 O(n)이 된다.
• 원소를 삽입하거나 삭제할 경우에는 해당 자리의 기존 연결을 끊고 가리키는 주소를 새로운 노드로 변경하거나 아예 다음 노드로 연결하면 되기 때문에 시간복잡도는 O(n)로 가능하다. 만약 맨 앞, 맨 뒤에 데이터를 삽입하면 O(1)이 된다.

Array Vs LinkedList

• Array는 연속된 메모리 공간에 존재하고 LinkedList는 메모리 상에서 떨어져 있는 데이터들이 자신의 앞 데이터와 뒤 데이터를 기억하는 형태로 존재한다.
• Array에 저장되어 있는 데이터를 조회 할 때에는 O(1)로 가능하지만 LinkedList는 O(n)이 소요 된다.
• 데이터의 삭입 삭제 속도는 LinkedList의 경우 O(1)이나 탐색에 필요한 시간 때문에 둘 모두 O(n)이 된다.
• Array는 크기가 고정적으로 정해서 사용해야하기 때문에 불필요한 메모리를 차지 할 수 있는 반면에 LinkedList는 필요 할 때마다 메모리를 할당하기 때문에 효율적으로 사용이 가능하다.

참고

https://medium.com/@yk392/what-is-a-linked-list-linked-list-vs-array-92f0db4015cc