LinkedList 클래스

[배열의 장점]

1. 구조가 간단하다.

2. 연속적이기 때문에 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

 

[배열의 단점]

1. 크기를 변경할 수 없다.

- 크기 변경을 해야 할 경우, 새로운 배열을 생성하고 데이터를 복사해야 한다..

- 크기 변경을 피하기 위해 큰 배열을 생성하면 메모리가 낭비된다.

2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

- 배열 중간에 요소를 추가, 삭제하려면 다른 데이터를 옮겨야 한다.

- 순차적인 데이터 추가(맨 끝에), 삭제(맨 끝부터)는 매우 빠르다.

 

[LinkedList, 링크드 리스트]

1. 배열의 단점(크기 변경 불가, 긴 데이터 추가/삭제 시간)을 보완한 자료구조이다.

2. 불연속적으로 존재하는 데이터를 연결한 리스트이다.

3. 장점: 데이터 변경에 유리하다.

- 데이터 삭제: 단 한 번의 참조변경만으로 가능하다.

- 데이터 추가: 한 번의 Node객체 생성과 두 번의 참조변경만으로 가능하다.

4. 단점: 데이터가 많을수록 접근성이 나쁘다.

- 배열처럼 불연속적으로 존재하는 것이 아니기 때문에 Node객체를 다 지나가 봐야 내가 찾는 데이터를 찾을 수 있다.

5. 단점을 보완한 링크드 리스트

- 더블리 링크드 리스트(doubly linked list): 이중 연결리스트. 링크드 리스트의 접근성 향상

- 더블리 써큘러 링크드 리스트(doubly circular linked list): 이중 원형 연결리스트. 마지막과 처음을 연결 시킴

 

---

[쿠키글] ArrayList(배열 기반 자료구조)와 LinkedList(연결 기반 자료구조) 성능 비교

순차적 데이터 추가/삭제: ArrayList가 더 빠르다.

비순차적 데이터 추가/삭제: LinkedList가 더 빠르다.

접근시간: ArrayList가 더 빠르다.