[자료구조] Array & ArrayList & LinkedList

 

📍Array(배열)

Array

• 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조. index와 값의 쌍으로 구성
• index는 값에 대한 유일무이한 식별자(마치 주민번호)( 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가짐)
• 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1))
• 연속된 메모리의 공간으로 이루어져 있다.
• 배열은 선언과 동시에 크기를 지정하며 배열의 크기를 바꿀 수 없다.

장점

• 인덱스를 통한 검색이 용이함.
• 연속적이므로 메모리 관리가 편하다.

단점

• 크기가 고정되어 있기 때문에 어떤 엘리먼트가 삭제되면, 삭제된 상태를 빈 공간으로 남으므로 삽입/삭제 연산에 불리함.
• 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다.
• 컴파일 이후 배열의 크기를 변동 할 수 없다.

📍List

List

• 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함
• 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 불연속적으로 메모리 공간을 차지.
• 포인터를 통한 접근

장점

• 포인터를 통하여 다음 데이터의 위치를 가르켜고 있어 삽입/삭제의 용이.
• 동적이므로 크기가 정해져 있지 않다.
• 메모리의 재사용 편리
• 불연속적이므로 메모리 관리의 편리

단점

• 검색 성능이 좋지 않다.
• 포인터를 통해 다음 데이터를 가르키므로 추가적인 메모리 공간 발생.

✔️ 배열 vs 리스트 정리

• 배열 : 데이터의 크기가 정해져 있고, 추가적인 삽입 삭제가 일어 나지 않으며 검색을 필요로 할 때 유리.

• 리스트 : 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.

---

Java에서 기본형(int, boolean, String, char) 또는 인스턴스를 리스트로 저장하는데는 보통 배열을 사용한다. 하지만 배열은 선언시에 크기를 정해줘야 하므로, 동적으로 요소의 추가나 삭제 등이 불가능하다는데 그 단점이 있다. 만약 배열의 원소를 추가하거나 삭제하려면, 직접 새로운 배열을 선언해주어서 카피하는 식으로 사용해야한다. 지속적으로 데이터를 변경해야되는 알고리즘 문제나, 어떤 프로그램의 구현에서 이는 꽤나 큰 불편함으로 다가온다.

 

이러한 불편함을 해소시켜주는 것이 List 인터페이스를 상속하여 구현된 ArrayList와 LinkedList 클래스이다. 이 둘은 모두 Collections 객체의 일종이다. 이 두 가지 리스트는 동적으로 사용할 수 있어 새로운 값의 추가나 제거가 유용하여 기본 배열의 단점을 커버해준다.

 

Java List Collection

• List는 Collection 인터페이스를 확장한 자료형으로 동일한 데이터의 중복 입력이 가능하며 순차적이고 다량의 데이터를 입력할 때 주로 사용합니다. 종류는 Vector, Arraylist, Linkedlist가 있습니다.

📍ArrayList

• 일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴 수 있다는 점에서 차이점이 있다.
• ArrayList는 내부에서 처음 설정한 저장 용량(capacity)가 있다. 설정한 저장 용량 크기를 넘어서 더 많은 객체가 들어오게 되면, 배열 크기를 1.5배로 증가시킴.
• 배열을 이용해 리스트를 구현한 것
• 접근이 빠름(순차 x) 하지만 데이터 추가와 삭제가 느림
• 동적으로 사용하기 힘듬(자바의 경우 자동으로 사이즈를 키워서 관리한다. → Dynamic Array)

📍LinkedList

• 노드 간에 연결(link)을 통해서 리스트로 구현된 객체이다.
• 다음 노드의 위치 정보만 가지고 있으며 인덱스를 가지고 있지 않기 때문에 탐색시 순차접근만 가능 (노드 탐색 시 시간이 많이 소요될 수 있음)(randomAccess 불가능)
• 노드 추가/삭제는 위치정보의 수정만으로 가능하기 때문에 성능이 좋음
• LinkedList는 ArrayList와는 달리 List 인터페이스를 구현한 AbstractList를 상속하지 않고 AbstractSequentialList를 상속한다.

---

🌐 참고 링크

[ 자료구조 ] 배열(Array) vs 리스트(List) - 특징, 차이

[자료구조]Array와 List(그리고 Java List)

[Java] Array와 List 상황별 성능 비교

[Java] ArrayList, LinkedList 차이