Ch11-12~14. LinkedList
0. 목차
Chapter11. 컬렉션 프레임웍
Ch11 - 12. LinkedList
Ch11 - 13. LinkedList의 추가와 삭제
Ch11 - 14. ArrayList와 LinkedList의 비교
Ch11 - 12. LinkedList
▶ 배열의 장점
▷ 배열은 구조가 간단
▷ 데이터를 읽는 데 걸리는 시간(접근 시간, access time)이 짧음
▶ 배열의 단점1 : 크기 변경
▷ 실행 중 배열의 크기 변경 불가
- 실행 중 배열의 크기를 변경해야 하는 경우
- ① 새로운 배열 생성
- ② 데이터 복사
- ③ 참조 변경
- ① 새로운 배열 생성
▷ 실행 중 크기 변경이 불가하다고 충분히 큰 배열을 생성하면, 메모리 낭비
▶ 배열의 단점2 : 비순차적 데이터의 추가/삭제
▷ 비순차적(중간에)인 데이터를 추가/삭제 하면 시간이 많이 걸림
- 중간에 데이터 추가/삭제 하는 경우
- 다른 데이터를 복사하고 옮겨야 함
- 다른 데이터를 복사하고 옮겨야 함
▷ 그러나 순차적인(끝에) 데이터 추가/삭제는 빠름
▶ LinkedList란?
▷ 배열의 단점을 보완하기 위한 것
▷ 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)
-
배열 : 연속적
-
LinkedList : 불연속적
class Node { Node next; // next Node 주소를 갖고 있음, 어디를 next로 가야할 지 아는 것 Object obj; // 데이터 }
Ch11 - 13. LinkedList의 삭제와 추가
▶ LinkedList 데이터 삭제
▷ 한 번의 참조 변경으로 삭제 가능
▷ 즉 변경에 유리
▶ LinkedList 데이터 삽입
▷ 한 번의 Node 객체 생성 + 두 번의 참조 변경으로 삽입 가능
▷ 즉 변경에 유리
▶ LinkedList의 단점
▷ linkedlist : 연결리스트, 데이터 접근성이 나쁨
class Node {
Node next;
Object obj;
}
▷ doubly linkedlist : 이중 연결리스트, 접근성 향상, java 구현
class Node {
Node next; // 다음 →
Node previous; // 이전 ←
Object obj;
}
▷ doubly circular linkedlist : 이중 원형 연결리스트
Ch11 - 14. ArrayList와 LinkedList의 비교
▶ 순차적 추가/삭제
▷ ArrayList speed > LinkedList speed
- ArrayList : 배열 생성해서 index[n]에 착착 추가
- LinkedList : 객체 하나 하나 생성해서 연결시킴
▶ 비순차적 추가/삭제
▷ ArrayList speed < LinkedList speed
- ArrayList : index[n]에 있는거 하나 씩 복사하면서 추가/삭제
- LinkedList : 객체와 객체 참조 변경 후 다시 연결
▶ 접근 시간(access time)
▷ ArrayList speed > LinkedList speed
- ArrayList :
인덱스가 n인 데이터의 주소 = 배열의 주소 + (n × 데이터 타입의 크기)
index[n]에서 데이터 주소를 구하기 쉬움 → 주소 찾아서 달라하면 접근 끝 - LinkedList :
한 객체 씩 다 방문