[자바의정석] ch 11-12 LinkedList - 배열의 장단점

 

🤔 LinkedList 배열의 장단점

 

✅ 장점

✔ 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

 

✅ 단점

✔ 크기를 변경할 수 없다.

크기를 변경해야 할 경우 새로운 배열을 생성 후 데이터를 복사해야 함.

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

✔ 비순차적인(중간에 데이터 넣는 것) 데이터의 추가, 삭제에 시간이 많이 걸림.

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

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

 

🤔 LinkedList - 배열의 단점을 보완

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

✔ 데이터의 삭제 : 단 한 번의 참조 변경만으로 가능

LinkedList 데이터의 삭제

✔ 데이터의 추가 : 한번의 Node 객체 생성과 두 번의 참조변경만으로 가능

 

 

🤔 LinkedList - 이중 연결 리스트

✔ 링크드 리스트(linked list) - 연결리스트, 데이터의 접근성이 나쁨.

(접근성이 나쁨 : 첫 번째에서 다섯 번째로 한 번에 이동 불가)

✔ 이중 연결 리스트, 접근성 향상!!

출처 : 자바의 정석 남궁성T 강의

앞뒤로 이동 가능함으로써 접근성 향상

But, 아직도 첫번째 -> 다섯 번째 한번에 이동은 불가!! ❌

 

 

이를 다시 보완한 것!

🤔 Doubly Circular Linked List - 이중 원형 연결리스트

출처 : 자바의 정석 남궁성T 강의

맨 뒤에서 맨 앞으로 이동 가능

 

 

 

 

// 링크드 리스트
class Node {
    Node next;
    Object obj;
}

// 이중 연결 리스트
class Node {
    Node next;
    Node previous;
    Object obj;
}

 

 

✅ 정리

✔ 순차적으로 데이터 추가/삭제 - ArrayList 가 빠름.

✔ 비순차적으로 데이터 추가/삭제 - LinkedList가 빠름.

✔ 접근 시간(Access Time) - ArrayList가 빠름.

 

💡 LinkedList 사용이유

==> 비순차적(list 중간)인 데이터 추가/삭제시 사용하려고!!