(Ch11) 1.3 LinkedList ~ 1.6 Arrays
LinkedList
앞서 본 배열(ArrayList)는 구조가 간단한고 데이터를 읽어오는데 걸리는 시간(access time)이 빠르다는 장점을 가지고 있다. 하지만 배열의 크기를 변경하거나 순차적으로 데이터에 접근하지 않는 경우 시간이 오래걸린다는 단점이 존재한다. 이러한 단점을 보완하기 위해 Linked List가 고안되었다. 모든 데이터가 연속적으로 연결되어있는 배열과 다르게 linked list는 불연속적인 데이터를 서로 연결하였다는데 차이점이 존재한다. 그렇기에 각각의 요소(node)는 다음 요소에 대한 참조(주소값)과 자신의 데이터값으로 구성되어 있다.
class Node {
Node next; // 다음 요소의 주소값
Object obj; // 현재 요소의 데이터값
}기존의 배열이 가지고 있던 수정과 삭제시 배열의 크기가 변하는 상황에서 다음 요소의 주소값만 변경하여 단점을 해결하였다. LinkedList는 단방향 연결만 이루어지기 때문에 이전 요소에 접근을 용이하기 위해 양방향으로 연결한 doulby linked list를 만들었다. 기존 LinkedList에서 이전 요소에 대한 주소값만을 추가한 것이다.
기존의 배열의 문제점을 해결하기 위해 LinkedList와 doubly linked list를 만들었지만 상황에 따라 적절한 자료구조를 선택하는 것이 필요하다. 순차적으로 추가/삭제가 이루어지는 경우에는 ArrayList가 LinkedList보다 빠르고, 중간 데이터를 추가/삭제 하는 경우에는 LinkedList가 더 우수한 성능을 보여준다.
Stack and Queue
Stack은 LIFO(Last in First out)방식을 사용하는 자료구조이다. 즉, 저장(push) 순서와 추출(pop) 할 때의 순서가 반대라고 생각하면 된다. Queue는 FIFO(First in First out) 방식을 사용하여, 저장(offer) 순서와 추출(poll)하는 순서가 동일하다.
각각의 자료구조를 구현하기 위해서 어떠한 Collection 클래스를 사용하는 것이 좋을까? 순차적으로 데이터를 추가/삭제 하는 Stack은 ArrayList와 같은 배열 기반의 클래스가 적절하지만, Queue의 경우 항상 첫번째 저장된 데이터를 삭제하기 때문에 배열 크기의 변화가 일어난다. 따라서 LinkedList로 구현하는 것이 바람직하다.
Stack과 Queue를 활용하는 예시는 다음과 같다.
Stack : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
Queue : 최근사용문서, 인쇄작업 대기목록, 버퍼(Buffer)
PriorityQueue and Deque
Queue, Stack 인터페이스를 활용하여 구현체들 중 몇개를 살펴보자.
PriorityQueue의 경우 저장한 순서에 관계없이 우선순위가 높은 값부터 추출하게 된다. Null을 저장할 경우 NullPointerException이 발생한다. 저장공간으로 배열을 사용하며, 각 요소를 heap이라는 자료구조 형태로 저장한다.
Deque(Double-Ended Queue)는 기존 Queue가 저장과 추출의 방향성이 정해져 있던 것에서 확장하여 양쪽에서 저장과 추출이 일어날 수 있도록 기능을 확장한 것이다. 각각의 방향에서 저장/추출하는 기능은 Queue와 Stack을 적절히 조합하여 구현하여야 한다.
| Deque | Queue | Stack |
|---|---|---|
| offerLast() / 끝에서 저장 | offer() | push() |
| pollLast() / 끝에서 삭제 | - | pop() |
| pollFirst() / 앞에서 삭제 | poll() | - |
| peekFirst() / 앞에 있는 요소 리턴 | peek() | - |
| peekLast() / 끝에 있는 요소 리턴 | - | peek() |
Iterator, ListIterator, Enumeration
Iterator, ListIterator, Enumeration은 Collection에 저장된 요소를 접근하는데 사용되는 인터페이스이다.
Iterator는 컬렉션 프레임워크에서 컬렉션에 저장된 요소를 읽어오는 표준화된 방법으로 각 요소에 접근하는 기능을 가진 인터페이스이다. Collection인터페이스에는 Iterator(Iterator를 구현한 클래스의 인스턴스)를 반환하는 iterator()를 정의하고 있다.
Enumeration은 컬렉션 프레임워크가 만들어지기 전에 사용하던 Iterator의 구버전이다. 호환성을 위해서 남겨놓은 것이기 때문에 Iterator를 사용하는 것이 바람직하다.
ListIterator는 Iterator를 상속받아 기능을 추가한 것으로, 단방향 접근만 가능하던 Iterator에 반해 ListIterator는 양방향 접근이 가능하다.
Arrays
Arrays클래스에는 배열을 다루는데 유용한 메소드가 정의되어 있다. 같은 기능의 메서드가 배열의 타입만 다르도록 오버로딩되어 있기 때문에 많아보일 수 있다.
toString() : 일차원 배열의 요소들 출력
copyOf()/cpoyOfRange() : 배열의 복사
fill()/setAll() : 배열 채우기
sort() : 배열의 정렬
binarySearch() : 배열의 검색
equals() : 배열의 비교
deepToString() : 다차원 배열에서 모든 요소 출력
Reference
