LinkedList

배열의 장단점

장점

1. 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧다

 

단점

1. 크기를 변경할 수 없다

크기를 변경해야하는 경우, 새로운 배열을 생성 후 데이터를 복사해야함 (더 큰 배열생성 -> 기존배열내용 복사 -> 참조변경)

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

 

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

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

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

 

 

LinkedList - 배열의 단점을 보완 (크기변경X / 추가삭제 시간 ↑)

> 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결 (link)

데이터의 추가 부분, 방향선 잘못 그어져있으니 유의해서 보자

 

LinkedList (링크드 리스트)

> 연결리스트, 데이터 접근성이 나쁨 (불연속적인 자료들을 다루다보니, 접근성이 나쁨)

doubly LinkedList (더블리 링크드 리스트)

> 이중 연결리스트, 접근성 향상 (앞과 뒤의 참조주소를 저장해두어 링크드리스트보다 접근성 높임)

doubly circular LinkedList (더블리 서큘러 링크드 리스트)

> 이중 원형 연결리스트, 맨 처음에서 끝을 조회하는데 걸리는 접근성을 높여줌

 

ArrayList  vs  LinkedList  성능비교

ArrayList = 배열기반 (연속적)

LinkedList = 연결기반 (불연속적)

 

읽기(접근시간) 우위
ArrayList > LinkedList (LinkedList는 데이터가 많을 수록 접근성이 떨어짐)

 

추가/삭제 우위
LinkedList > ArrayList (순차적인 추가삭제는 ArrayList가 더 빠름)