[자료구조] Array와 LinkedList의 차이 (인터뷰 대비)

 

💡 1. Array(배열), Array VS ArrayList

 

1. 배열 :  배열은 순차적으로 데이터를 저장하는 자료구조이다.

 

2.크기 : 배열의 크기는 고정길이이므로, 추가적으로 늘릴 수 없다. Array는 초기화 시 메모리에 할당되게 된다.

 

3. 장점 : 데이터의 순서가 있기 때문에, 0부터 시작하는 index가 존재하며, 이 index를 활용해 특정 요소에 대해 접근이 가능하며 조작이 가능한 것이 장점이다.

 

4. 단점 : 데이터의 삽입이나 삭제가 중간에서 이뤄지는 경우, 그 뒤의 모든 요소를 한 칸 앞 당기거나, 밀어줘야 하는 소요가 있으므로 속도적 비용이 요구된다. O(N)

 

5. 사용하면 좋은 경우 : 순서를 보장해줘야 하는 데이터에 대해 사용하면 좋다. index가 의미를 내포할 수 있는 데이터에 대해 사용하면 좋다. 예를 들면 주식 정보가 있다. 주식 차트에 대한 데이터는 중간에 요소가 추가되거나 삭제되지 않고, 날짜별로 주식 가격이 차례대로 측정되어야 하기 때문이다. 

 

6. Java의 Array vs ArrayList

 차이는 '크기'에 있다. 기존의 Array는 고정길이로, 한 번 길이를 할당하면 더 이상 배열의 사이즈를 늘릴 수 없다. 만약 데이터를 더 추가하고 싶다면, 아예 새로운 배열을 할당해서 옮겨주어야 한다는 소요가 있다.

하지만 ArrayList는 다르다. 내부적으로는 배열의 형태로 구현되어있지만, 고정길이가 아닌 가변길이를 채택한 자료구조이다.

 

ArrayList는 객체로, 내부에 ArrayList 내부 배열의 사이즈를 결정하는 capacity 멤버변수가 있다. ArrayList에 자료를 계속해서 추가하면 이 capacity 변수가 자동으로 늘어나게 된다. 설정된 capacity를 넘어선 새로운 변수가 들어오게 된다면, 배열의 크기를 1.5배 증가시키는 로직으로 내부가 구성되어 있다.

 

기본적으로 내부가 배열로 이뤄져있으므로, 새로운 배열에 할당해서 옮겨주어야 한다는 것은 동일하다. 하지만 내부적으로, capacity를 넘어선다면 1.5배 커진 배열을 생성하고, 해당 배열에 copy를 시켜주는 작업을 자동으로 진행해준다는 점에서 굉장히 편리하다.

 

resize operation이 발동이 되는 만큼, 시간 복잡도 측면에서 손해를 볼 수 있다.

 

추가적으로 Array는 원시 자료형과 Object를 모두 저장할 수 있으나, ArrayList는 Object만 저장할 수 있다. 기본형을 저장하는 것은 불가하므로 저장 시 autoboxing에 의해 원시 자료형이 들어가는 것처럼 보인다.

 

💡 2. LinkedList (연결리스트)

 

1. 연결리스트 : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

 

2. 크기 : 크기가 정해져있지 않다.

 

3. 장점 : 각각의 노드는 자기 자신 다음에 어떤 원소가 저장되어 있는지 알기 때문에, 연결을 끊고 다음 노드로 이어주기만 해주면 삭제가 가능하다. 삽입도 마찬가지로, 중간 연결을 끊고 새로운 노드에 각각 연결되도록 설정하면 쉽게 삽입 연산을 실행할 수 있다. O(1)의 시간복잡도로 삭제와 삽입 연산을 진행할 수 있다.

 

4. 단점 : 배열과 다르게 index가 존재하지 않는다. 특정 값을 찾기 위해서는 해당 연결리스트 내부의 원소를 모두 다 뒤져야 하므로 검색에 대한 시간 복잡도는 O(N)이 소요된다.

 

5. 사용하면 좋은 경우 : 중간 데이터의 삽입 삭제가 많은 경우, 자료구조 내부에 몇 개의 데이터를 삽입할 지 모르는 경우 등에 활용하면 좋다.

 

😎 출처

[링크] https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList ([자료구조] Array vs ArrayList)