LinkedList를 알아보기 전에
먼저 배열의 장단점을 알아보자
장점 : 배열은 구조가 간단하고 데이터를 읽는데 걸리는
시간(접근시간, access time)이 짧다.
단점 1 : 크기를 변경하기가 어렵다.
- 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야함.
- 더 큰 배열 생성 2. 복사 3. 참조변경
- 크기변경을 피하기 위해 충분히 큰 배열을 생성하면 메모리가 낭비됨.
단점 2 : 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
- 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
LinkedList는 배열의 단점을 보완
- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)한다.
array는 각 요소가 연속적(객체의 주소가 0x100, 0x104 와 같이 4byte 차이) 그러나 LinkedList는 각 요소가 어디에 있는지 알 수가 없다. (0x200 이후에 0x300, 0x350 과 같이 불연속적이다)
LinkedList 형태의 데이터는 각 하나하나의 객체를 노드라고 하며 객체의 구성요소는
class Node {
Node next; // 다음노드
Object obj; // 데이터
}하나의 개별 요소들을 연결해 놓기 때문에 변경에 유리하다.
데이터의 삭제 : 단 한 번의 참조변경만으로 가능,
객체에 포함된 다음 노드의 주소를 변경만하면 된다. 그 이후 지워진 주소는 Garbage Collector 에 의해 삭제됨
데이터의 추가 : 한번의 Node객체생성과 두 번의 참조변경만으로 가능
배열의 단점을 보완하여 사용하기 위해 만든 것이 LinkedList이다.
LinkedList의 단점
단점 : 링크드 리스트 - 연결리스트, 데이터 접근성이 나쁨
데이터가 불연속적이기 때문에 이동이 많다.
(징검다리처럼 하나하나 넘어가야한다.)
더블리 링크드 리스트(Doubly Linked List) - 이중 연결리스트, 접근성 향상
class Node {
Node next; // 다음 요소
Node Previous; // 이전 요소
Object obj;
}
앞뒤의 이동이 가능해졌지만 한번에 여러개를 이동 할 수는 없다.
더블리 써큘러 링크드 리스트(Doubly Circular Linked List) - 이중 원형 연결리스트
- 더블리 링크드 리스트와 같은 구조이나 인덱스 맨 앞, 뒤에 주소를 연결하여 사용
ArrayList vs LinkedList - 성능 비교
순차적으로 추가/삭제하기 - ArrayList 승
// 큰 차이는 없다, 약 2배~4배차이
// 순서대로 추가하고 삭제하기 때문에 데이터의 이동이 없기때문
비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
// 약 20배 정도의 차이
접근시간(access time) - ArrayList 승
// 압도적으로 빠름
| Collection | 읽기(접근시간) | 추가/삭제 비교 |
|---|---|---|
| ArrayList | 빠르다 | 느리다, 순차적인 추가 삭제는 더 빠름 비효율적인 메모리 사용 -> 성능을 높이고자 배열을 크게 잡아야 하기 때문 |
| LinkedList | 느리다 | 빠르다 데이터가 많을수록 접근성이 떨어짐 |
