ArrayList와 LinkedList차이점
List란?
어떤 순서가 있는 데이터의 집합
배열(Array)과 연결 리스트(Linked List)는 데이터를 저장하고 관리하는 자료구조이다.
1. 메모리 구조
Array List
- 연속된 메모리 공간에 저장되며, 각 요소가 인덱스로 접근 가능하다.
- 배열은 고정된 크기로 선언되기 때문에, 크기를 초과하는 데이터가 들어오면 메모리를 확장할 수 없다.
Linked List
- 노드(Node)와 포인터로 이루어져 있으며, 각 노드는 다음 노드의 주소를 가지고 있다.
- 노드가 메모리 내 비연속적으로 배치되기 때문에, 데이터 크기에 맞춰 동적 확장이 가능하다.
2. 데이터 접근 속도
Array List
- *O(1)**의 시간 복잡도로 인덱스를 통해 빠르게 요소에 접근할 수 있다.
- 예를 들어, 배열의
arr[3]에 접근할 때 3번 인덱스에 바로 접근한다.
Linked List
- *O(n)**의 시간 복잡도로 순차적으로 노드를 따라가야 원하는 데이터에 접근할 수 있다.
- 특정 위치의 데이터를 찾으려면 첫 번째 노드부터 순차적으로 탐색해야 하므로 접근 속도가 느리다.
3. 삽입 및 삭제
Array List
- 중간에 삽입하거나 삭제하려면, 해당 위치 이후의 요소를 한 칸씩 이동시켜야 하므로 O(n)의 시간 복잡도를 가진다.
- 배열의 마지막에 추가하거나 삭제하는 경우는 상대적으로 빠르다.
Linked List
- 중간에 삽입이나 삭제할 때 해당 위치의 포인터만 변경하면 되므로 O(1)의 시간 복잡도로 처리할 수 있다.
- 삽입/삭제할 위치를 찾기 위해 탐색이 필요한 경우 O(n) 시간이 소요되지만, 이미 노드를 알고 있다면 매우 빠르게 삽입/삭제가 가능하다.
4. 메모리 사용량
Array List
- 배열은 선언할 때 고정된 크기로 메모리를 할당하므로, 남거나 부족한 메모리가 발생할 수 있다.
- 배열의 크기를 초과하거나 크기를 줄이려면 새로운 배열을 생성해야 한다.
Linked List
- 연결 리스트는 필요할 때마다 노드를 추가하므로 메모리 효율이 좋다.
- 그러나 각 노드에 데이터와 함께 포인터 공간이 필요하므로, 배열보다 메모리를 더 많이 사용할 수 있다.
5. 예시 코드
Array List 예시
배열은 선언 후 고정된 크기를 가지며, 인덱스를 통해 데이터를 빠르게 접근할 수 있다.
data = []
# append: 평균 O(1)
for i in range(5):
data.append(i)
# 인덱스 접근: O(1)
rint(data[3]) # 3
# 순차 탐색: O(n)
for x in data:
print(x)
# 중간 삽입: O(n)
data.insert(2, 99)
print(data) # [0, 1, 99, 2, 3, 4]
Linked List 예시
연결 리스트는 “collections.deque”를 통해 각 노드가 다음 노드를 가리키도록 구현한다.
# LinkedList/Deque 스타일
dq = deque()
# append / appendleft: O(1)
dq.append(1)
dq.append(2) # 오른쪽 끝에 요소 추가
dq.appendleft(0) # 왼쪽 끝에 요소 추가
print(dq) # deque([0, 1, 2])
# pop / popleft: O(1)
dq.pop() # 오른쪽 끝 요소 제거
dq.popleft() # 왼족 끝 요서 제거
print(dq) # deque([1])
6. Array List과 Linked List의 장단점
| 특성 | 배열(Array) | 연결 리스트(Linked List) |
|---|---|---|
| 메모리 구조 | 연속적 | 비연속적 |
| 접근 속도 | O(1), 빠름 | O(n), 느림 |
| 삽입/삭제 | O(n), 느림 (중간에서 삽입/삭제 시) | O(1), 빠름 (중간에서 삽입/삭제 시) |
| 메모리 사용 효율성 | 고정된 크기, 비효율적일 수 있음 | 필요할 때마다 크기 확장 가능 |
| 추가 메모리 요구 | 추가 메모리 요구 없음 | 각 노드에 포인터 저장을 위한 메모리 요구 |
결론
- Array List : 데이터 접근 속도가 빠르며, 데이터 크기가 고정되어 있고 자주 변경되지 않는 경우 적합하다.
- Linked List : 데이터의 삽입/삭제가 빈번하고, 데이터 크기가 유동적인 경우에 적합하다.
Leave a comment