자바 스터디 4회차 - ArrayList, LinkedList, Stack & Queue, 인터페이스 Queue 사용 방법 / 컬렉션 프레임워크(2)

ArrayList!

• Vector를 개선한 것으로 구현원리와 기능은 동일 (두 클래스의 차이는 동기화! 벡터는 자체적으로 동기화 처리)
• 저장순서 유지, 중복 허용
• 데이터의 저장공간으로 배열을 사용

 

ArrayList의 메서드! 는 책으로 보자

 

ArrayList의 추가와 삭제

 

추가

1. 삭제할 데이터의 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어씀
2. 데이터가 모두 한 칸씩 위로 이동하였으므로 마지막 데이터는 null로 변경
3. 데이터가 삭제되어 데이터의 개수(size)가 줄었으므로 size의 값을 1 감소시킴

**마지막 데이터를 삭제하는 경우, 1의 과정(배열 복사)은 필요 없음

 

삭제

1. ArrayList에 저장된 첫 번째 객체부터 삭제하는 경우(배열 복사 발생, remove(0)부터 삭제할 때)
2. ArrayList에 저장된 마지막 객체부터 삭제하는 경우(배열 복사 발생 X, 빠름)

 

LinkedList!

 

배열의 장단점

장점

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

단점

• 크기 변경 불가 (크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함)
• 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
  (데이터 추가, 삭제를 위해 다른 데이터를 옮겨야 함
  순차적인 데이터 추가(끝에) 삭제(끝부터)는 빠름)

*** 배열의 저장 공간이 부족할 때

더 큰 배열 생성 -> 기존 내용 복사 -> 참조 변경

 

LinkedList 특징과 장점

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link, 기차) 
• 데이터의 삭제 - 단 한 번의 참조변경만으로 가능, 변경에 유리함
• 데이터의 추가 - 한 번의 Node 객체 생성과 두 번의 참조변경만으로 가능

LinkedList 단점

• 연결된 리스트. 데이터 접근성이 나쁨

더블리 링크드 리스트 (doubly linked list) - 이중 연결리스트, 접근성 향상 (이전과 다음, 앞 뒤로 움직일 수 있게 연결)

 

더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트 (맨 처음 요소와 맨 끝 요소를 연결, 티비 채널 생각하기)

 

ArrayList vs LinkedList 성능 비교

1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름
2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
3. 접근시간(access time) - ArrayList가 빠름

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

 

 

스택과 큐(Stack & Queue)

스택 (Stack) - LIFO 구조, 마지막에 저장된 것을 제일 먼저 꺼냄 (Last In First Out, 밑이 막힌 상자, 책 쌓기, ArrayList)

스택은 클래스, 객체 생성 가능

 

큐 (Queue)  - FIFO 구조, 제일 먼저 저장한 것을 제일 먼저 꺼냄 (First In First Out, 양끝이 뚫린 상자, 줄 서기, LinkedList)

큐는 인터페이스 취급, 객체 생성 불가

 

add, remove, element- 예외 발생 / romover는 try-catch문

offer, poll, peek - 예외 발생 X / offer은 if문

.

 

Stack과 Queue의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

큐의 활용 예 - 최근사용문서, 인쇄작업 대기 목록, 버퍼(buffer)

 

인터페이스를 구현한 클래스 찾기 - 인터페이스 Queue를 사용하는 방법

1. Queue를 직접 구현

2. Queue를 구현한 클래스 사용 - Java API 

Queue 인터페이스를 구현한 클래스 목록, 익숙한거 쓰자 / Queue q = new LinkedList();