컬렉션 프레임워크

0.Collection(list, set 조상)
1.List(순서 o , 중복 허용)
2.set (순서 x , 중복 x)
3.Map(키와 밸류값, 키는 중복 허용 x 밸류는 허용)

0.collection

1. List

• vector
• ArrayList
• LinkedList
  

2.Set

• HashSet
• treeSet
  

3.Map

• HashMap
• treeMap

List- ArrayList

1. ArryaList는 기존의 vector을 개선한 것으로 Vector와 구현원리와 기능적 측면에서 같다.

2. ArrayList는 object배열을 이용해서 데이터를 순차적으로 저장한다.(=모든 종류의 객체를 담을수 있다.)

3. 공간 부족= 큰배열 생성해서 기존꺼 복사.(늘릴수 없다)

4. 공간을 여유롭게 잡는다.

5. 변경이 많은 작업에는 취약하다.

(오류는 무시해 주세요)

=변수 i를 증가시켜가면서 삭제하면(앞에서 부터 삭제 하면), 한요소가 삭제될때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 해야 하기 때문에 올바른 결과를 얻을 수 없다. 그래서 뒤 부터 삭제시작한다.

remove()

-지정된 위치 삭제하고 반환한다.
-삭제 할 객체의 바로 아래에 있는 데이터를 한칸씩 위로 복사해 삭제할 객체를 덮어쓰는 방식으로 처리한다.

remove(2)

• System.arrayCopy(data, 3, data , 2 ,2)
• 데이터가 한칸씩 위로 이동하였으므로 마지막 데이터는null
  -data[size-1] =null
• 데이터가 삭제 되어 데이터 개수가 줄었으므로 size값을 1감소시킨다
  size--;

삭제

• 끝부터 삭제
• 중간 = system.arraycopy 덮어씌우기

List-linkedList

배열

-장점-

• 데이터를 읽어 오는데 걸리는 시간이 빠르다.

-단점-

• 크기를 변경할수 없어서 새로운 배열생성후 복사해야 한다.
• 마지막에서 부터 삭제하는 것은 빠르지만 중간에서 데이터를 추가/삭제 하면 빈자리를 만들기 위해 다른 데이터들을 복사 해서 이동해야한다.

링크드리스트

이러한 배열의 단점을 보안하기 위해 linkedList 고안 되었다.

1.자신과 연골된 다음 요소에 대한 참조(주소값)와 데이터로 구성되있다.

2.그래서 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.(추가/삭제가 쉽다)

더블 링크드 리스트

링크드 리스트가 이동방향이 단방향이여서 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

더블 링크드 리스트는 이전 요소에 대한 참조가 가능 하도록 한 양방향 이다.

더블 써큘러 링크드 리스트

더블 링크드 리스트의 접근성을 보다 향상시킨 것이다. 단순히 더블 링크드 리스트의 첫번쨰 요소와 마지막 요소를 서로 연결 시킨 것이다.

ArryaList VS linkendlist

ArrayList
1.초기 공간을 넉넉히 잡아준다. 공간이 부족해서 새로운 배열을 만들고 복사하고 번거롭기 떄문이다.

2.뒤에서 부터 삭제는 빠르지만 / 중간에서 부터 삭제를 하면 느리다

linkedList

1.중간에서 삭제해도 빠르게 문제없다.

->.순차적으로 추가/삭제하는 경우에 ArryList가 linkendlist보다 빠르다

->중가 데이터를 추가/삭제하는 경우는 linkedlist가 더 빠르다.

배열 vs linkedlist

배열 은 각 요소들이 연속적으로 메모리상에 존재하기 떄문에 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 바로 읽어 올수있다.

linkedlist는 불연속적으로 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 그래서 데이터의 개수가 많아 질수록 데이터를 읽어오는 시간이 오래 걸린다.

※데이터의 개수가 변하지 않는 경우면 Arraylist, 변경이 많으면 linkedlist

Stack과 queue

사진에서 보시다시피 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO 구조 이고 큐는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO 구조로 되어있다.

스택과 큐 구현 WITH 컬렉션클래스

1.순차적으로 데이터를 추가/삭제 하는 스택에는 Arraylist가 적합하고 큐는 데이터를 꺼낼 떄 항상 첫 번쨰 데이터를 삭제하므로 추가/삭제가 쉬운 linkedlist가 적합하다.

※ 자바에서 스택을 stack클래스로 구현하여 제공 하고 있지만 큐는 Queue인터페이스로 만 정의 해놓았다. 그러므로 Queue인터페이스를 구현한 클래스들을 사용하면 되겠다.

연습

스택과 큐는 많이 안써봐서 직접 만들어 봤다.

Priority Queue

=Queue 인터페이스 구현체중의 하나로 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 특징이 있다. (null은 저장 안됌)

=저장공간으로 배열을 사용하며 각 요소를 힙 이라는 자료구조의 형태로 저장한다.

운선순위는 숫자가 작을수록 높은것이다

Dequeue

Queue = 한쪽끝으로만 추가/삭제 가능하다
Dequeq(덱 or 디큐) = 양쪽 끝에 추가/삭제 가능

Dequeq 조상은 Queue이며, 구현체로는 linkedList가 있다.

덱은 마치 스택과 큐를 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고 큐로도 사용할수도 있다.