1. LinkedList 배열의 장단점
- 장점
- 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
- 단점
- 크기를 변경할 수 없다.
- 크기변경을 위해서는 아래와 같이 3단계 작업을 해야 한다.
- 더큰 배열을 생성
- 기존 데이터를 복사한 뒤
- 참조를 변경해주어야 한다.
- 크기 변경을 피하기 위해 충분히 큰 배열을 생성하게되면, 메모리가 낭비된다.
- 비순차적인(=중간 데이터) 데이터의 추가, 삭제에 시간이 많이 걸리게 된다.
- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다.
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
2. LinkedList 배열의 단점 보완
- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
참조: https://www.nextree.co.kr/content/images/2021/01/jdchoi_20140225_arrayvslinkedlist11.png
- 데이터의 삭제: 단 한 번의 참조변경만으로도 가능하다.
- 삭제할 때 중간에 삭제를 했다해도 머리와 꼬리만 다시 이어붙어주면 되기 때문이다.
- 데이터의 추가: 한 번의 Node 객체 생성과 두 번의 참조 변경만으로도 가능
- 추가하는 데이터의 앞에 있는 노드 뒤에 있는 노드의 참조만 변경해주면 되기 때문에 2번의 참조 변경이 필요
3. LinkedList의 단점
- 데이터 접근성이 나쁘다.
- 배열의 경우엔 어디에 뭐가 존재하는지 아는데 링크트 리스트의 경우엔 바로 뒤 데이터만 알기 때문에 한 번에 이동하기 어려움
- 이런 데이터 접근성이 떨어지는 것을 보완하기 위해 나타난 것이 더블리 링크드 리스트(Doubly Linked List)
출처: https://user-images.githubusercontent.com/30790184/63559933-dcaf1380-c58e-11e9-819a-c82236d44e0d.jpeg
- 이중 원형 연결리스트(doubly circular linked list)
출처: https://media.geeksforgeeks.org/wp-content/uploads/Circular-doubly-linked-list.png
4. ArrayList VS LinkedList 성능 비교
