자바의 정석 ch11-12~14 LinkedList

12 LinkedList - 배열의 장단점

장점

• 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다. 연속적이어서 간단한 계산으로 주소를 쉽게 얻을 수 있다.

단점

1. 크기를 변경할 수 없다. (실행중에)
   -크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사 해야 함. (더 큰 배열 생성 후, 복사해서 참조 변경을 해야 한다.)
   -크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
2. 비 순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
   -데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
   -그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

배열의 단점을 보완

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

LinkedList - 이중 연결 리스트

linked list

• 연결 리스트. 접근성이 나쁨. 첫번째 요소는 그 다음 요소만 알고 있고 그 다음 다음 요소는 알지 못해서 배열처럼 한번에 접근이 불가능 하다.

class Node {
	Node next;  // 다음요소
    Object obj;
}

doubly lined list

• 이중 연결 리스트. 접근성 향상

class Node {
	Node next;	   // 다음 요소
    Node previous; // 이전 요소
    Object obj;
}

doubly circular linked list

• 이중 원형 연결 리스트. 마지막 요소를 맨 앞에 연결 해 놓고, 맨 첫번째 요소를 맨 끝에 연결 해 놓는다.

ArrayList / LinkedList 성능 비교

1. 순차적으로 추가 / 삭제 하기 : ArrayList가 빠름
2. 비순차적으로 추가 / 삭제 하기 : LinkedList가 빠름
3. 접근 시간 테스트 : ArrayList가 빠름

• ArrayList
  : 배열 기반의 자료 구조. 순차적인 추가 삭제는 더 빠름. 비효율적인 메모리 사용.
• LinkedList
  : 연결 기반의 자료 구조. 데이터가 많을수록 접근성이 떨어짐.