Array

• 배열이라 부르며 논리적 저장순서와 물리적 저장순서가 일치합니다.
• 특정 자료형들이 메모리 공간 상에서 연속적으로 이루어져 있습니다.
• immutable한 특성을 갖고 있습니다.
• 인덱스로 해당 원소에 접근할 수 있으며, 인덱스를 알고있을 경우 O(1)의 시간복잡도로 원소접근이 가능합니다.
• 삭제 또는 삽입 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 shift연산이 필요합니다. 따라서 O(N)
• 메모리 공간활용에 제약이 있습니다.

Linked List

• 데이터 검색시 처음 노드부터 순회해야 합니다. 논리적 저장순서와 물리적 저장순서가 다르기때문이죠. 따라서 탐색의 경우 시간복잡도는 O(N)입니다.
• 메모리 공간 상에서 각 노드들이 연속적으로 이루어져있고, 흩어져있으며 각각의 노드가 자신의 다음 노드위치를 알고있는 형태로 구현됩니다.
• 사용자는 첫번째 위치만 알고 있습니다.
• 어떤 원소를 삽입, 삭제 시 그 원소를 찾기위해 O(N)의 시간복잡도가 발생하고 추가작업을 완료하는 시간까지 O(N)의 시간이 걸립니다.

결국 Linked List는 검색과 삽입, 삭제 과정 모두 O(N)의 시간복잡도를 갖습니다. (특정 원소를 찾아 삽입해야할 경우)

데이터 접근 속도

• Array
  • 인덱스를 사용하여 빠르게 접근하므로 시간복잡도는 O(1)입니다.
  • Random Access가 가능하죠.
• Linked List
  • 특정 원소에 접근하기 위해서는 처음부터 순차적으로 검색하기 때문에 시간복잡도는 O(N)입니다.

데이터 삽입 속도

• Array
  • 데이터를 중간이나 맨 앞에 삽입할 경우 이후 데이터를 Shift해야합니다. 시간복잡도는 O(N)입니다.
• Linked List
  • 중간 삽입없이 맨앞 혹은 맨 뒤만 삽입한다면 O(1)의 시간복잡도를 갖습니다.
  • 그렇지 않은경우 삽입할 위치를 찾고 산입연산을 진행하기 때문에 O(N)의 시간복잡도를 갖습니다.

참고 : Array의 경우 데이터를 삽입하여 모든 공간이 꽉 차게 되면 새로운 메모리 공간을 할당받아 옮겨야 하지만, Linked List는 추가할때마다 동적으로 메모리 공간을 할당받습니다. 때문에 mutable하며, 삽입시 시간복잡도와 상관없이 오버헤드가 줄어 빠른 성능을 보여줍니다.