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