[자료구조] Array vs LinkedList

Array

• 가장 기본적인 자료구조

• 같은 타입의 변수들을 일렬로 정렬해 놓은 구조

• 논리적 저장 순서와 물리적 저장 순서가 일치 => 인덱스(index)로 해당 원소(element)에 접근 가능

• 찾고자하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근 가능

• 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조, 배열의 크기는 한 번 정하면 변경 불가

• 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다.

• 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용)
  - 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다.

• 삭제 또는 삽입의 과정에서는 해당 원소를 삭제/삽입 후 해당 원소보다 큰 인덱스를 갖는 원소들을 shift 해야 함 => 비용 발생 (시간복잡도 O(n))
  -메모리는 Array가 선언될 때 (컴파일할 때) Stack 영역에 할당한다.

LinkedList

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식
• 즉,연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 (포인터를 사용하여 연결)
• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억 -> 이 부분만 수정하면 삭제/삽입을 O(1)만에 해결 가능
• 탐색을 해야하는 경우, Array와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문에 리스트를 순회해야하므로 시간복잡도 O(n)
• Tree 구조의 근간이 되는 자료구조
• 메모리는 새로운 노드가 추가될 때 (Runtime) Heap 영역에 할당

ArrayList

• 크기가 가변적이다.
• 내부적으로 배열을 사용(인덱스 이용) -> 접근 속도 빠름
• add(), remove()를 통해 추가/삭제 가능
  - 단, 데이터 추가/삭제 시 메모리를 재할당하기 때문에 속도가 배열보다 느림
  

Array vs ArrayList vs LinkedList

• Array : index로 빠르게 값을 찾는 것이 가능
• LinkedList : 데이터의 삽입 및 삭제가 빠름
• ArrayList : 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림