[JAVA의 정석]LinkedList
이 글은 유튜브 '자바의 정석 - 기초편'을 보고 정리한 글입니다.
📂content
1. 배열의 장단점
⚝ 장점
배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
배열은 연속적이다.
예를 들어, int배열이라고 하면 하나가 4btye이다.
그렇다면 3이라는 데이터를 읽을려고 한다면, 0x100 + 4 * 2를 하면 된다.
즉, 배열주소+ 배열 요소 크기 * 인덱스(n) = 내가 원하는 주소를 알 수 있다.
(-> n+1번째 요소를 알 수 있음. n+1인 이유는 index가 0부터 시작하므로 )
⚝ 단점
1. 크기를 변경할 수 없다.
- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함. (코드로 작성은 못 해도 설명은 해야함. )
① 더 큰 배열 생성
② 기존 내용 복사
③ 참조 변경
2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
- 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 함.
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
비순차적 => 중간에 있는 데이터 같은 것들
2. LinkedList - 배열의 단점을 보완
- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
0x104, 0x108....처럼 데이터가 붙어있다.
● 데이터의 삭제 : 단 한 번의 참조변경만으로 가능
- 각 요소가 어디에 있는지 알 수 가 없다.
- 요소 하나를 `Node`라고 한다. Node 클래스를 보면 Node는 다음 노드이고, Object는 데이터이다.
- 다음 요소(노드)의 주소인 0x300을 저장한다.
- Array(배열)은 상자와 비슷하고, 리스트(List)는 기차와 비슷하다.
● 데이터의 추가 : 한 번의 Node 객체생성과 두 번의 참조변경만으로 가능
● 링크드 리스트(linked list) - 연결리스트. 데이터 접근성이 나쁨
내 다음만 알고 있다. 한 번에 내가 원하는 장소로 갈 수가 없다.
● 더블리 링크드 리스트(doubly linked list) - 이중 연결리스트, 접근성 향상
연결이 2개임. 참조 next와 previous 2개를 가지고 있다.
● 더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트
다른 리스트를 보면 마지막 값이 null이다. 이것을 활용한 것!
3. ArrayList vs LinkedList - 성능 비교
① 순차적으로 데이터를 추가 / 삭제 - ArrayList가 빠름
② 비순차적으로 데이터를 추가 / 삭제 - LinkedList가 빠름
③ 접근시간(access time) - ArrayList가 빠름
인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
✎ 정리
| 컬렉션 | 읽기(접근 시간) | 추가 / 삭제 | 비고 |
| ArrayList | 빠름 | 느림 | 순차적인 추가삭제는 더 빠름. 비효율적인 메모리 사용 (성능을 높이려고 배열을 크게 잡아서) |
| LinkedList | 느림 | 빠름 | 데이터가 많을수록 접근성이 떨어짐 |
📣 comment
ArrayList와 List는 다르다.
이 둘의 가장 큰 차이점은 초기화시 크기가 가변인지 불변인지이다.
ArrayList는 크기가 가변적이지만, List는 크기가 불변이다.
우리가 알고리즘 테스트를 볼 때 주로 사용했던 것은 List이다.
//배열(Array)
int arr = new int[4];
import java.util.ArrayList;
//ArrayList
ArrayList<Integer> list = new ArrayList<>();
출처