LinkedList - 배열의 장단점

배열에 저장 공간이 부족해서 새로운 배열을 만들때 어떻게 해야되나요?

물어보면

첫번째. 더 큰 배열을 만들고

두번째. 기존 내용을 복사하고

세번째. 참조를 변경해야 됩니다.

즉, 배열은 크기를 변경할 수 없고, 추가 삭제 시간이 오래 걸린다.

이 문제를 해결 한 것이 LinkedList 이다.

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
• 데이터의 삭제 : 단 한번의 참조변경만으로 가능
• 데이터의 추가 : 한번의 Node객체 생성과 두번의 참조변경만으로 가능

LinkedList - 이중 연결 리스트

• 링크드 리스트 - 연결리스트, 데이터 접근성이 나쁨 다음요소는 바로 갈수 있지만, 바로 3번째 4번째 ... 등등을 뛸 수 없다. 돌다리 건너듯이 건너야 한다. 이걸 데이터 접근성이 나쁘다고 한다.
  

이것을 보완 한게 이중 연결 리스트이다.

이걸 사용함으로써 두번째 노드에서 첫번째로 노드로 가는게 가능해 지는 것이다.

그전 단계의 노드로 갈 수 있게 되었다.

이중 연결 리스트를 더 보완한 것이 이중 원형 연결 리스트이다.

ArrayList 와 LinkedList 성능 비교

1. 순차적으로 데이터를 추가 / 삭제 - ArrayList 가 빠름
2. 비순차적으로 데이터를 추가 / 삭제 - LinkedList 가 빠름
3. 접근시간 - ArrayList 가 빠름

ArrayList 는 배열 기반이고,LinkedList 는 연결 기반이라고 말할 수 있다.

Reference
남궁 성 지음, 『자바의 정석』, 도우출판.