LinkedList - 배열의 단점 보완

배열의 장점

배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간(access time)이 짧다

연속적이다

 

배열의 단점

1. 크기를 변경할 수 없다

    크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다

    배열의 사이즈를 늘리고 싶다면 더 큰 배열을 생성해야 한다(예시 링크) [더 큰 배열 생성 -> 내용 복사 -> 참조 변경]

    크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비된다

 

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

    데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다

    그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다

 

 

LinkedList - 배열의 단점 보완

배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결한다

 

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

 

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

 

LinkedList의 단점  - 이중 연결 리스트

데이터 접근성이 나쁘다

Doubly linked list - 이중 연결리스트, 접근성 향상
끝 값이 null이다

 

Doubly circular linked list - 이중 원형 연결 리스트

---

ArrayList와 LinkedList 성능 비교

1. 순차적으로 데이터를 추가/삭제: ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제: LinkedList가 빠름

3. 접근 시간(access time): ArrayList가 빠름

    (인덱스가 n인 데이터의 주소 = 배열의 주소 + n(n번쨰 요소) * 데이터 타입의 크기)

 

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠르다 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어진다