ArrayVSList.md

Array(배열)

• 같은 자료형을 가진 데이터를 그룹핑해 효과적으로 관리하는 데이터 스트럭처.
• 메모리에 순차적으로 데이터를 저장한다.
• 인덱스를 이용한 데이터 조회가 빠르다.
• 데이터 크기가 컴파일시 결정되어 크기를 변경할 수 없다.
• 데이터 삭제시 빈 공간으로 남기 때문에 메모리를 낭비할 수 있다.

// java
int[] arr = {1, 2, 3, 4};
// 배열의 삭제 메소드가 존재하지 않음.
arr.length(); // 4
// 0 등 프로그래머가 의미상 삭제하는 코드를 작성하더라도 길이는 4로 고정되어있다.

List(리스트)

• 같은 자료형, 순서가 있는 엘리먼트들의 모임이라는 특징은 배열과 같다.
• 하지만 배열과 다르게 삭제하더라도 빈공간을 허용하지 않는다.
• 순서가 있지만 메모리에 순차적으로 적재되어 있는지 아닌지는 구현된 언어별 라이브러리마다 다른다.
• 리스트에 인덱스는 존재하지만 일반적으로 메모리상 순서의 의미보다는 몇번째 데이터인지를 의미한다.

// java
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 4; i++) {
    list.add(i); // 1, 2, 3, 4 저장
}
list.size(); // 4

list.remove(0); // index 0에 위치한 데이터 삭제
list.size(); // 3

Java에서의 List

ArrayList

• 내부 구현이 Array(배열)로 되어 있다.
• 크기를 동적으로 변경할 수 있지만 내부적으로 배열이기 때문에 변경되는 크기에 따라 배열의 재할당이 일어난다.
• 따라서 인덱스로 인한 조회 성능이 좋으며 삽입, 삭제의 성능이 떨어진다.

LinkedList

• 내부 구현이 Linked List(연결리스트)로 되어 있다.
• 연결리스트란 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식이다.
• 따라서 탐색할때 head 부터 시작하며 O(n) 시간복잡도를 가진다.
• get(index) 메소드가 구현되어 있지만 내부적으로 head부터 탐색하기에 탐색 성능이 떨어진다.
• 삽입, 삭제가 빈번한 경우 사용하는 것이 좋다.

참고

생활코딩 - Data Structure (자료구조) 중 리스트