2024. 7. 24. 01:19ㆍ코테/자료구조
배열
배열은 같은 자료형의 변수로 이루어진 구성 요소가 모인 것을 말하는 "선형 자료구조"입니다.
리스트
리스트는 다양한 자료형의 변수로 이루어진 구성 요소가 모인 것을 말하는 "선형 자료구조"입니다.
배열과 리스트의 차이
| 특성 | 배열 | 리스트 |
| 크기 | 고정된 크기 | 가변 크기 |
| 메모리 할당 | 연속된 메모리 할당 | 비연속된 메모리 할당 |
| 데이터 타입 | 동일한 데이터 타입 | 다양한 데이터 타입 |
| 접근 속도 | 빠른 인덱스 접근(O(1)) | 순차적 접근(O(n)) |
| 삽입 및 삭제 | 비용이 큼(O(n)) | 최소(O(1)), 최대(O(n)) |
1. 크기
배열은 선언 시에 크기가 고정됩니다.
배열 선언 시에 크기를 명시적으로 지정해줘야 하고 한 번 설정된 크기는 변경할 수 없습니다.
int[] array = new int[5]; // 크기가 5인 배열 생성
array[0] = 1;
array[1] = 2;
array[2] = 3;
array[3] = 4;
array[4] = 5;
반면에 리스트는 필요에 따라서 크기를 동적으로 변경할 수 있습니다.
리스트에 요소를 제거하거나 추가할 때마다 자동으로 크기가 조절됩니다.
import java.util.ArrayList;
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 요소를 계속 추가할 수 있습니다.
list.add(6); // 리스트의 크기가 자동으로 증가합니다.크기가 동적으로 조정되기 때문에 초기 크기를 정확하게 예측할 필요가 없습니다.
따라서, 필요한 만큼만 메모리를 사용할 수 있기 때문에 효율적입니다.
2. 메모리 할당
첫번 째 정수의 주소값이 1000이고, 정수의 크기가 4byte라고 가정했을 때 위와 같이 데이터가 저장됩니다.
이처럼 배열에서 각 데이터는 연속적인 메모리 위치에 저장됩니다.
연결 리스트는 배열과 다르게 데이터가 순차적으로 저장될 필요가 없습니다.
.
리스트는 노드라는 것으로 이루어져 있습니다.
노드는 data와 다른 노드의 주소값인 link로 이루어져 있습니다.
사진과 같이 주소값이 4700인 노드에는 해당 노드와 연결된 노드의 주소값인 4800이 있습니다.
그리고 마지막 노드에는 연결된 노드가 없기 때문에 link가 Null입니다.
첫번 째 노드의 주소를 알면 모든 노드에 연결될 수 있습니다.
그래서 첫번 째 노드를 알기 위해서 포인터(여기서는 Head라고 부름)가 필요합니다.
이렇게 각각의 노드에 데이터와 다음 노드를 연결해 주는 주소값을 가지고 있기 때문에 메모리의 무작위적인 위치(비연속적인 메모리 위치)에 저장됩니다.
3. 데이터 타입
배열은 선언 시 지정한 데이터 타입의 요소들로만 구성됩니다.
모든 요소는 동일한 데이터 타입을 가져야 하며, 이는 배열의 타입 안정성을 보장합니다.
모든 요소가 동일한 타입이기 때문에 메모리 할당과 관리가 효율적입니다.
반면 리스트는 다양한 데이터 타입의 요소들을 저장할 수 있습니다.
이는 리스트의 유연성을 높이며, 여러 타입의 데이터를 같은 리스트에 저장할 수 있게 해 줍니다.
추가로, 리스트는 제네릭을 사용하여 데이터 타입을 지정할 수 있으며, 다양한 타입의 객체를 저장할 수 있습니다.
제네릭을 사용하지 않으면 Object 타입으로 모든 객체를 저장할 수 있습니다.
4. 접근 속도
접근 속도는 특정 요소에 접근하는 데 걸리는 시간을 의미합니다.
배열과 리스트의 접근 속도는 크게 다릅니다.
배열의 접근 속도는 O(1), 상수시간으로 배열의 모든 요소가 메모리의 연속적인 공간에 있으므로 인덱스를 사용해서 직접적으로 접근할 수 있기 때문입니다.
반면, 리스트의 접근 속도는 O(n), 선형시간으로 리스트의 처음부터 끝까지 순차적으로 탐색해야 합니다.
리스트는 메모리상으로 비연속적으로 있으므로 노드의 포인터를 하나씩 따라가며 요소에 접근해야 하기 때문입니다.
5. 삽입 및 삭제
배열에서 요소를 삽입할 때는 삽입 위치 이후의 모든 요소를 한 칸씩 이동시켜야 합니다.
이 작업은 삽입 위치 이후 모든 요소를 움직여야 하므로 최악의 경우 O(n)의 시간이 소요됩니다.
삭제의 경우 배열은 데이터가 연속적으로 있다는 데이터의 무결성을 지켜야 하므로
삭제한 위치 이후의 모든 요소를 왼쪽으로 한 칸씩 이동시켜야 합니다.
리스트는 삽입해야 하는 위치를 알 경우 해당 위치의 노드를 찾아서 새로운 노드를 연결하면 되므로 O(1)의 시간이 소요됩니다. 하지만, 삽입할 위치를 찾아야 하는 경우에는 O(n)입니다.
삭제도 이와 마찬가지로 위치를 알 경우 O(1), 위치를 탐색해야 하는 경우에는 O(n)입니다.
ArrayList와 LinkedList
리스트는 다양한 데이터 구조를 포함하는 일반적인 용어입니다.
데이터를 순서대로 저장하는 저장하는 구조를 의미하며, 여러 가지 방식으로 구현될 수 있습니다.
자바의 리스트를 구현하는 클래스는 두 가지 주요 타입이 있습니다.
ArrayList
배열을 기반으로 하며, 연속적인 메모리 블록에 데이터를 저장합니다.
빠른 인덱스 접근이 가능하지만, 삽입과 삭제는 비효율적일 수 있습니다.
LinkedList
노드를 사용하여 비연속적인 메모리 공간에 데이터를 저장합니다.
각 노드는 데이터와 다음 노드에 대한 참조를 포함합니다.
즉, ArrayList는 연속적 메모리 할당을 사용하고, 빠른 인덱스 접근을 제공하는 배열을 기반으로 하는 동적 배열입니다.
그리고 LinkedList는 비연속적 메모리 할당을 사용하고, 효율적인 삽입과 삭제를 제공하는 동적 배열입니다.
LinkedList의 종류
- Single Linked List : Linked List의 기본형을 말하며, 탐색이 노드가 가리키는 한쪽 방향으로만 수행됩니다.
- Doubly Linked List: 정방향 및 역방향으로 탐색이 가능합니다.
- Circular Linked List: 마지막 노드가 첫 번째 노드와 연결됩니다.