[Java] 6-1강 - Collection Framework 1 (List - ArrayList, Vector, LinkedList, Stack & Queue)

1. List

0) List

[1] 원소간 중복을 허용 (allows duplicate elements)

[2] 순서가 있고 (ordered collection)

 

1> Hierarchy of interfaces

2> Interface List<E>에 정의된 Method

 

1) ArrayList

interface implement는 여러 개 할 수 있고

상속(extends)은 하나만 받을 수 있습니다. 

 

0> Hierarchy of interfaces

※ ArrayList 소스코드 내부를 보면 Object array인 instance variable이 존재한다.

1> <example 1>

type variable로 primitive를 사용할 수 없습니다.

(그래서 int대신에 Integer를 사용합니다.)

-> (그래서 Integer의 값을 표현하기 위해서 valueOf라는 메소드를 사용합니다.)

[1] ArrayList의 크기를 10으로 설정 

[2] add 메소드로 6개의 원소를 추가

[3] subList : ~까지의 원소들로 다시 ArrayList를 만듭니다.

[4] (Collections와는 다릅니다.) 정렬

[5] A.containsAll(B) : A가 B를 contain하고 있는가? (집합간의 포함 관계를 묻는다.)

[6] E set (int index, E element) : 특정 index의 원소를 element로 바꾼다.

[7] A.retainAll(B) : A의 원소 중 B에 해당하는 것만 남기고 제거한다. (A와 B의 교집합)

[8] boolean contains(Object o) : instance인 collection이 o를 가지고 있는가?

 

2> <example 2>

[1] 1이 아니라 10인 이유는 넉넉하게 메모리를 미리 주기 위해서입니다.

 

2) Vector

[1] size : vector의 원소 개수

[2] capacity : 이 vector는 몇 개의 원소를 넣을 수 있는가?

 

vector는 synchronized하다. (한 번에 1개 thread만 접근 가능하다.)

3> <exmple 3> 

[1] Vector의 capacity를 5로 설정 후 1, 2, 3을 추가

[2] 빈 공간을 제거

[3] capacity가 6보다 작다면 6까지 증가시킨다. 

[4] size가 7보다 작다면 7까지 증가시킨다. (null element라는 element를 억지로 만들어서 size 증가시킨다.)

=> capacity가 7보다 작다면 2배 증가시킨다.

[5] size를 0으로 만들고 capacity는 그대로이다.

 

 

cf> ArrayList, Vector, LinkedList는 List interface를 implement한다.

=> 다만 ArrayList, Vector, LinkedList는 각각 구현방식이 다릅니다. (성능 차이 생김)

=> ArrayList는 memory가 연속적인 형태로 element를 저장됩니다.

 

 

3) LinkedList

각 element마다 다음 element에 대한 reference(link)를 저장하고 있습니다.

=> memory는 비연속적인 형태로 element를 저장

1> Add & Delete

[1] add는 새로운 instance를 만들고 그 양 옆의 reference를 만듭니다.

[2] delete는 reference를 다음 element로 update하면 됩니다.

 

2> type of LinkedList

[1] basic linked list (singly linked list)

[2] doubly linked list 

뒤에서 앞으로 오는 접근성이 좋습니다.

[3] doubly circular linked list

 

3> accessing data

ArrayList는 data까지 바로 접근이 가능하지만 

LinkedList는 data까지 접근하려면 그 앞의 node를 모두 거쳐서 가야합니다.

 

<example 1>

[1] System.currentTimeMillis() : 현재 시간 기록

 

4) Stack & Queue

1> Stack

top에 push하고, top에서 pop

[1] peek : top의 원소를 보기만 하는 것

[2] search : 해당 object의 위치를 return

 

2> Queue

back에 add하고, front에서 poll

[1] poll : front의 원소를 return하고 제거

[2] peek : front의 원소를 return

[3] element : front의 원소를 return (원소가 없으면 null을 return)

[4] add : 원소를 back에 넣는다. + 원소를 넣을 공간이 있는지 return

[5] offer : 원소를 넣을 공간이 있는지 return

 

3> Priority Queue

priority를 기준으로 원소가 먼저 제거됩니다.

heap 구조로 element를 정리합니다.