배열
- 연속된 데이터를 저장하는 자료구조
- 인덱스와 대응하는 데이터를 저장하며, 인덱스는 첫번째로부터 상대적인 위치를 표현
- 검색(조회) 연산은 빠르지만, 추가/삭제 연산이 느리다.
배열 생성하기
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| value | 월 | 화 | 수 | 목 | 금 | 토 | 일 |
위와 같은 배열을 자바에서 생성하자면
String[] week = {"월", "화", "수", "목", "금", "토", "일"};
System.out.println(week[0]); // 출력: 월
System.out.println(week[6]); // 출력: 일길이는 7 이지만 인덱스 번호는 6까지 존재한다.
배열의 길이와 인덱스 번호가 다른 이유
배열의 길이는 배열이 저장할 수 있는 요소의 총 개수를 나타낸다.
인덱스 번호는 배열의 각 요소에 접근하기 위한 위치를 나타내며, 0부터 시작한다.
따라서 인덱스 번호는 0에서 시작하여 배열의 길이보다 하나 작은 값까지 존재하게 된다.
여기서는, 길이가 7인 배열이지만 인덱스 번호는 0부터 6까지 존재한다.
이는 배열의 첫번째 요소에 접근할 때는 인덱스 0을 사용하고, 마지막 요소에 접근할 때는 인덱스 (길이-1)을 사용한다.
배열의 특징
1. 고정된 크기: 배열은 생성 시 크기가 고정되며, 한 번 생성된 배열의 크기는 변경할 수 없다.
따라서 배열의 크기를 신중하게 결정해야 한다.
2. 연속된 메모리 공간: 배열은 연속된 메모리 공간을 차지한다.
이러한 특성 때문에 인덱스를 이용한 접근이 매우 빠르며, 시간 복잡도가 O(1)이다.
3. 빠른 검색: 배열은 인덱스를 통해 빠르게 요소에 접근할 수 있어 검색(조회) 연산이 빠르다.
4. 느린 추가/삭제: 배열의 중간에 요소를 추가하거나 삭제하는 경우,
해당 요소 이후의 모든 요소를 이동시켜야 하기 때문에 시간 복잡도가 O(n)으로 느리다.
5. 동일한 데이터 타입: 배열은 동일한 데이터 타입의 요소들만 저장할 수 있다.
예를 들어, 정수형 배열은 정수만, 문자열 배열은 문자열만 저장할 수 있다.
6. 인덱스를 이용한 접근: 배열의 각 요소는 인덱스를 통해 접근할 수 있으며, 인덱스는 0부터 시작한다.
리스트
- 연속적으로 데이터를 저장하는 자료구조
- 각 요소는 노드로 구성되며, 노드는 데이터와 다음 노드를 가리키는 포인터를 포함
- 추가/삭제 연산이 빠르지만, 검색(조회) 연산이 느리다.
리스트 생성하기
| Node | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Value | A | B | C | D |
위와 같은 리스트를 자바에서 생성하자면
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
System.out.println(list.get[0]); // 출력: A
System.out.println(list.get[1]); // 출력: B
System.out.println(list.get[2]); // 출력: C
System.out.println(list.get[3]); // 출력: D
}
}리스트의 각 노드는 다음 노드를 가리키는 포인터를 가지며, 마지막 노드는 null을 가리킨다.
리스트의 특징
1. 동적인 크기: 리스트는 동적으로 크기를 조절할 수 있으며, 요소를 추가할 때마다 크기가 늘어난다.
2. 링크를 통한 연결: 리스트의 각 요소(노드)는 다음 요소를 가리키는 포인터를 포함하며, 이를 통해 연결된다.
3. 빠른 추가/삭제: 리스트의 중간에 요소를 추가하거나 삭제하는 경우, 포인터만 수정하면 되므로 시간 복잡도가 O(1)이다.
(요소를 찾는 과정 제외)
4. 느린 검색: 리스트는 순차적으로 탐색해야 하므로 특정 요소에 접근하기 위해서는 시간 복잡도가 O(n)이다.
5. 다양한 데이터 타입: 리스트는 다양한 데이터 타입의 요소를 저장할 수 있다. 각 노드가 포인터를 통해 연결되므로 데이터 타입에 구애받지 않는다.
6. 인덱스가 없음: 리스트는 배열과 달리 인덱스를 통해 요소에 접근할 수 없으며, 노드를 순차적으로 탐색해야 한다.
리스트의 활용
- 요소의 추가/삭제가 빈번하게 일어나는 경우
- 데이터의 순서가 중요하고, 순차적으로 탐색이 필요한 경우
- 메모리 공간을 효율적으로 사용하고자 하는 경우
리스트는 배열에 비해 검색이 느리지만, 동적인 크기와 빠른 추가/삭제 연산 덕분에 많은 상황에서 유용하게 사용될 수 있습니다.
이러한 특성 때문에 다양한 데이터 구조와 알고리즘에서 기본적인 구성 요소로 사용됩니다.
