ch 11-7~11 ArrayList Java API 소스 보기

ArrayList

• List 인터페이스 = 순서가 있고, 중복을 허용한다.
• List인터페이스를 구현한 컬렉션 클래스 : 1. ArrayList 2. LinkedList
• ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일
  ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.
• List인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.
• 데이터의 저장공간으로 배열을 사용한다.(배열기반)
  < Vector 클래스의 소스 >
  
• 안에 객체 배열이 존재한다.
• 객체 배열 안에 모든 종류의 객체를 저장할 수 있다.

ArrayList의 메서드

ArrayList() : 기본 생성자
ArrayList(Collection c) : 매개변수로 Collction을 주면, Collection에 저장되어 있는 것을 저장하는 ArrayList를 만들 수 있다. (Collection끼리 변환 할 때 많이 사용
ArrayList(int initialCapacity) : 배열의 길이를 넣어준다. (배열은 한 번 길이를 지정하면 변경불가이므로 저장하려는 개수만큼 배열의 길이를 지정해줘야 한다.)

boolean add(Object o) : ArrayList에 추가하기 위해서 add메서드(객체) 사용 (성공시 true, 실패시 false)
void add(int index. Object element) : add메서드(저장위치) -> 저장위치를 지정해서 ArrayList에 저장
boolean addAll(Collection c) : Collection을 주면, Collection이 주는 요소를 그대로 저장한다.
boolean addAll(int index. Collection c) : 저장위치를 지정해서 Collection이 주는 요소를 그대로 저장

boolean remove(Object o) : 저장한 것을 삭제하기 위해 remove를 사용
Object remove(int index) : 특정 위치에 있는 객체를 삭제할 수 있다.
boolean removeAll(Collection c) : Collection에 있는 객체들을 삭제한다.
void clear() : ArrayList 안에 있는 모든 객체들을 삭제한다.

int indexOf(Object o) : 객체가 몇 번째 있는지 검색 (못 찾으면 -1을 반환)
int lastIndexOf(Object o) : 오른쪽부터 객체를 찾는다.
boolean contains(Object o) : 지정한 객체가 존재하는지 (있으면 true / 없으면 false)
Object get(int index) : 특정 위치에 있는 객체 반환
Object set(int index. Object element) : 특정 위치에 있는 객체를 변경

List subList(int fromIndex. int toIndex) : from 위치 ~to 사이의 객체들을 뽑아서 새로운 list를 만든다.
Object[] toArray() : ArrayList가 가지고 있는 객체 배열을 반환한다.
Object[]toArray(Object[]a) : ArrayList가 가지고 있는 객체 배열을 반환한다.
boolean isEmpty() : ArryaList가 비어있는지 확인
void trimToSize() : 빈 공간을 제거한다.
int size() : ArrayList에 저장된 객체의 개수를 반환한다.

ArrayList에 저장된 객체의 삭제과정 (1/2)

• ArrayList에 저장된 세 번째 데이터(data[2])를 삭제하는 과정. list.remove(2);를 호출
  
  
  
• 삭제할 2의 밑에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.
  
  
• size = 저장된 객체의 개수 (현재는 5)
  
  
• 데이터가 삭제되었으므로 size의 값은 4가 된다.
• 마지막 데이터를 삭제하는 경우, 1의 과정(배열의 복사)은 필요없다.

ArrayList에 저장된 객체의 삭제과정 (2/2)

1.ArrayList에 저장된 첫 번째 객체부터 삭제하는 경우(배열 복사 발생)

• i가 처음에는 0이 되므로 처음에 0을 제거한다.
• 나머지가 올라가면서 i가 1이 되서 2를 제거한다.
• 나머지가 올라가고 i가 2가 되면서 4르 제거한다.
• 배열이 하나씩 올라가므로 다 삭제되지 않는다.
  2.ArrayList에 저장된 마지막 객체부터 삭제하는 경우(배열 복사 발생안함)
  
• 맨 끝에서부터 객체가 제거되므로 배열 복사가 발생하지 않는다.
• 속도가 빠르고 원하는대로 모든 객체가 제거된다.

Java API 소스 보기 - /jdk설치경로/src.zip

• 바로 보기를 원한다면, jdk설치경로 -> src.zip을 더블 클릭 -> java -> util -> Vector.java를 더블 클릭
• 이클립스에서 소스를 보고 싶다면, 소스를 보고 싶은 클래스나 메서드에서 우클릭, Open Declaration을 클릭한다. -> Attach Source를 클릭 -> External Location -> Exteranl File...을 클릭하고 jdk가 설치된 경로를 지정 -> jdk 설치경로 지정 -> src.zip 지정

ch 11-12~14 LinkedList, ArrayList와 비교

LinkedList - 배열의 장단점

• 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.
  
• 배열은 연속적이므로 첫 번째 객체를 읽어오는 것과 마지막 객체를 읽어오는 속도가 같다.
• 만약 세번째 요소를 가지고 온다 하였을 때, 계산식은 주소값+42 (=배열주소+배열요소배열요소의 크기index) -> n+1번째 요소의 주소를 쉽게 계산할 수 있다.
• 단점 1 : 크기를 변경할 수 없다.
  • 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함.
    
    Ex) 6자리의 배열을 읽어오기 위해서는 1. 더 큰 새로운 배열 생성 2. 기존의 데이터 복사 3. 참조 변경
  • 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
• 단점 2 : 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
  • 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.
  • 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

LinkedList - 배열의 단점을 보완

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)
  
• 배열은 각 요소가 연속적이다. (=객체가 붙어있다. / 0의 주소값이 0x100이면, 1은 0x104, 2는 0x108)
• 데이터의 삭제 : 단 한 번의 참조변경만으로 가능
  
• 링크드 리스트는 불연속적이다.(=객체가 붙어있지 않아 어디 있는지 알 수 없다)
• 노드의 위에 있는 수는 다음 요소(노드)의 주소로 예를 들어 다음 값(next)이 0x300 / 값(data)가 0이라면, 0x300을 저장

class Node {
	Node next;	// 하나의 주소값에 있는 주소값과 값을 모두 Node라 한다. / 자신의 다음 노드가 어디 있는지 찾아갈 수 있는 참조 변수를 가지고 있다.
    Object obj; // Node에 저장된 데이터
}

• 연결만 바꾸면 값을 삭제하거나 추가 할 수 있기 때문에 변경에 유리하다.
• 데이터의 추가 : 한 번의 Node 객체 생성과 두 번의 참조변경만으로 가능
  
• LinkedList는 배열의 단점(1. 크기변경 불가 / 2. 추가와 삭제 시간이 오래 걸린다.)을 보완하기 위해 나왔다.
• LinkedList는 하나하나 연결된 구조로 불연속적인 존재다.

LinkedList - 이중 연결 리스트

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

class Node {
	Node next;	
    Object obj; 
}

• 배열은 연속적이라 다른 요소에 한 번에 접근할 수 있다. 그러나 LinkedList는 불연속적이므로 다음 요소로 바로 접근하는 것은 가능하나, 다른 요소에 바로 접근하는 것은 불가하다.
• 더블리 링크드 리스트(doubly linked list) - 이중 연결리스트, 접근성 향상
  

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

• 이중 연결리스트는 서로 근접한 요소를 앞뒤로 접근할 수 있도록 하였다.
• 한번에 다른 요소로 접근하는 것은 불가능하다.
• 더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트
  
• 맨 처음 요소를 맨 마지막 요소와 연결하고, 맨 마지막 요소 역시 맨 처음 요소와 연결시켰다.
• 맨 처음 요소에서 맨 마지막 요소로 이동할 때 4번 이동해야할 거리가 1번 이동할 거리로 줄었다.
• 이중 원형 연걸리스트는 맨 앞과 맨 마지막 요소가 접근 가능하지만, 아직 배열보다 불편하다는 단점이 있다.

ArrayList vs LinkedList - 성능 비교

Ex)

• 순차적으로 데이터를 추가/삭제 : ArrayList가 빠르다. (LinkeList는 새로운 객체를 하나 만들어야 하는 반면, ArrayList는 저장공간에 값을 넣기만 하면 되기 때문에)
• 비순차적으로 데이터를 추가/삭제 : LinkedList가 빠르다. (중간에 추가/삭제)
• 접근시간(access time) : ArrayList가 빠르다.
• 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기
  
• ArrayList = 배열기반의 자료구조 / LinkedList = 연결기반의 자료구조