Array

같은 타입의 데이터를 순차적으로 저장하는 선형 자료구조

• 데이터 접근 용이하다.(인덱스로 접근 / Random Access 가능)
• 논리적 저장 순서와 물리적 저장 순서가 일치한다.
• 구조가 간단하여 프로그램 작성이 쉽다.
• 크기를 변경할 수 없다.
• 데이터 삽입/삭제가 어렵다(삽입/삭제 시 원소들의 이동 필요)

시간 복잡도
탐색 : O(1)
마지막에 원소 추가/제거 : O(1)
중간에 원소 추가/제거 : O(N) - 데이터 이동

Array - Java

int[] arr = new Array[10];
int[] number = new int[]{1,2,3};
String[] str = {"hello", "array"};

List

순서를 가진 데이터의 집합을 가리키는 추상자료형

• 동일한 데이터의 중복 입력을 허용한다.
• 빈틈 없는 데이터의 적재
• 구현 방법에 따라 ArrayList, LinkedList로 나뉜다.

ArrayList

Array를 기반으로 구현된 List

• 내부적으로 Array를 사용한다.
• 데이터 접근이 용이하다.(인덱스로 접근)
• 크기를 동적으로 늘릴 수 있다.(설정한 용량 크기를 넘어서면 1.5배로 늘린다.)
• 데이터 삽입/삭제가 느리다.

LinkedList

자료 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결시킨 선형 자료구조

• 불연속적 메모리 공간에 데이터를 저장한다.
• 포인터로 연결되어 있어 데이터 삽입/삭제가 용이하다.
• 데이터 접근이 느리다.(임의 접근이 불가능)
• 포인터를 위한 추가 공간이 필요하다.
• Head(리스트의 첫 번째 노드), Tail(리스트의 마지막 노드)

시간 복잡도
탐색 : O(N)
처음/마지막에 원소 추가/제거 : O(1)
중간에 원소 추가/제거 : O(N) - 데이터 탐색