LinkedList
배열 장점
- 배열은 구조가 간단하고 데이터 접근 시간 (access time) 이 짧다.
- 순차적 데이터 추가 (끝에서 추가) 와 삭제 (끝에서 삭제) 가 빠르다.
배열 단점
- 크기 변경 불가
- 크기 변경할 경우 새로운 배열 생성 후 데이터 복사
- 미리 큰 배열을 생성하면 메모리 낭비
- 비순차적인 데이터 추가, 삭제 시간이 많이 걸린다. (중간 지점 부터)
![](https://velog.velcdn.com/images/iseon_u/post/7e379fb3-3f17-40f0-9ef8-5474cb822dcc/image.png)
LinkedList - 배열의 단점을 보완
- 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결 (link)
- 변경에 유리하다.
- 데이터 삭제는 단 한번의 참조 변경으로 가능
- 데이터 추가는 한번의 Node 객체 생성과 두 번의 참조 변경만으로 가능
![](https://velog.velcdn.com/images/iseon_u/post/680d8789-21fe-4319-ae68-cf274f5afaeb/image.png)
class Node {
Node next;
Object obj;
}
LinkedList - 단점
- 연결 리스트, 데이터 접근성이 나쁘다.
- 노드는 다음 노드 위치만 알기 때문에 배열처럼 한번에 이동 불가
- 이전 노드도 알 수 없다.
Doubly linked list
- 이중 연결 리스트, 접근성 향상
- 앞 뒤로 이동 가능
class Node {
Node next;
Node previous;
Object obj;
}
![](https://velog.velcdn.com/images/iseon_u/post/bc5e21b8-94f3-4d89-b346-b18e9d736d84/image.png)
Doubly circular linked list
- 이중 원형 연결 리스트
- 이중 연결 리스트의 null 값에 처음과 끝을 연결
ArrayList vs. LinkedList 성능 비교
- 순차적으로 데이터 추가 / 삭제 - ArrayList 빠름
- 비순차적으로 데이터 추가 / 삭제 - LinkedList 빠름
- 접근 시간 - ArrayList 빠름
컬렉션 | 읽기 (접근 시간) | 추가 / 삭제 | 비고 |
---|
ArrayList (배열 기반) | 빠르다 | 느리다 | 순차적인 추가 / 삭제 빠름 |
비효율적 메모리 사용 | | | |
LinkedList (연결 기반) | 느리다 | 빠르다 | 데이터가 많을수록 접근성 떨어진다. |