자료형 - Array / ArrayList / LinkedList

Array

선형 자료구조(Data Structure)중 하나로

동일한 타입의 연관된 데이터를 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료 구조

 

장점

• 연속된 메모리 공간에 요소를 저장하므로, 메모리 공간의 효율적 사용 가능
• 행렬같은 다차원 데이터 표현 가능
• 배열은 인덱스를 사용 > 빠른 접근이 가능(인덱스를 알고 있으면 상수 시간(O(1))에 접근할 수 있음)

단점

• 배열 중간에 요소를 삽입하거나 삭제하려면 해당 위치 이후의 요소들을 모두 이동시켜야 하므로 O(n)의 시간 복잡도를 가짐 > 성능 저하 초래
• 배열이 가진 정적 크기의 한계를 극복하기 위해 사용하는 것이 ArrayList
• 생성할 때 크기를 정하고 이후에 변경할 수 없음 > 미리 필요한 데이터의 양을 예측해서 배열을 생성해야 함

 

ArrayList

Array(배열)와 List(리스트)의 장점을 합친 것

 

특징

1. 동적 크기 조정 : 내부적으로 배열을 사용, 요소를 추가하거나 삭제할 때 필요에 따라 크기를 동적으로 조정할 수 있음(크기 제한 없이 유연하게 요소 관리 가능)
2. 제네릭 타입 : 제네릭을 사용하여 요소의 타입 지정 가능 > 타입 안정성 제공+잘못된 타입의 요소 추가 방지
3. 요소 접근 : 인덱스를 사용해 빠르게 요소에 접근 가능
4. 요소 추가와 삭제 : 요소를 추가하거나 삭제하는 메서드를 제공( add(), remove() )→내부적으로 요소를 이동시키는 작업을 처리
5. 반복과 순회 : for 반복문 / Iterator를 사용하여 요소를 반복하고 순회
6. 기타 기능 : ArrayList는 다양한 메서드를 제공하여 요소의 검색, 정렬, 복사, 부분 리스트 생성 등의 기능을 수행할 수 있음( 예: contains() -> 특정 값이 리스트에 있는지 확인)

배열에 비해 크기 조정과 요소 추가/삭제가 효율적인, 유연성과 편리성을 제공하는 자료구조

 

요소의 추가/삭제 작업이 빈번하게 발생하는 경우에는 성능이 저하될 수 있으며, 특정 위치의 요소에 접근할 때는 배열보다 느릴 수 있음

 

요소의 순차적인 접근이 주로 필요한 경우에 ArrayList를 활용하는 것이 적합

 

LinkedList

노드(객체)끼리 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조

>인접 객체를 체인처럼 연결해서 관리함

 

데이터의 추가와 삭제가 매우 빠름

 

특정 인덱스에 있는 요소에 접근하기 위해서는 리스트를 처음부터 순회해야 하므로 접근 속도가 느림

 

 

ArrayList vs. LinkedList

ArrayList는 내부적으로 데이터를 배열로 저장 > 이로 인해 인덱스를 통한 데이터 접근이 매우 빠르지만,

배열의 크기를 조정해야 하는 데이터 추가 및 삭제 작업 시에는 속도가 느림

 

따라서, 데이터의 추가 및 삭제가 빈번히 일어나는 경우에는 LinkedList를

데이터의 인덱스를 통한 접근이 주로 일어나는 경우에는 ArrayList를 사용하는 것이 좋음