Collection Framework

데이터 군을 저장하는 클래스들을 표준화한 설계
컬렉션 Collection :  다수의 데이터. 데이터 그룹
프레임웍 Framework :  표준화된 프로그래밍 방식.





Java.util.LinkedList Class

배열의 단점을 보완하기 위해 고안된 자료 구조.
불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성.




구성

각 요소(Node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

private static class Node<E> {
       E item;
       Node<E> next;
       Node<E> prev;         // Doubly-LinkedList
}

•  array 0x100
0 1 2 3 4
•  LinkedList 0x200
0x200 0x300 0x350 0x370 0x400
0x300 0x350 0x370 0x400 null
0 1 2 3 4




삭제

삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경한다.
단 하나의 참조만 변경하면 되므로 처리 속도가 매우 빠르다.
0x200 0x300 0x370 0x400
0x300 0x370 0x400 null
0 1 3 4




추가

새로운 요소를 생성한 후 추가하고자 하는 위치의 이전 요소의 참조를
새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경한다.
처리 속도가 매우 빠르다.
0x200 0x250 0x300 0x370 0x400
0x250 0x300 0x370 0x400 null
0 5 1 3 4




접근성

이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전 요소에 대한 접근이 어렵다.


•  Doubly-LinkedList
    이중 연결 리스트
    LinkedList의 접근성을 보완한 것.
    참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외는 LinkedList와 동일하다.
    접근과 이동이 쉽기 때문에 LinkedList보다 많이 사용된다.

  -  LinkedList  ex) 0x200
0x200 0x300 0x350 0x370 0x400
0x300 0x350 0x370 0x400 null
0 1 2 3 4
  -  Doubly-LinkedList  ex) 0x200
0x200 0x300 0x350 0x370 0x400
0x300 0x350 0x370 0x400 null
null 0x200 0x300 0x350 0x370
0 0 0 0 0


•  Doubly Circular LinkedList
    이중 원형 연결 리스트
    Doubly-LinkedList보다 접근성을 향상 시킨 것.
    단순히 Doubly-LinkedList의 첫 번째 요소와 마지막 요소를 서로 연결시켰다.
    실제로 LinkedList 클래스는 이름과 달리, 낮은 접근성(accessability)을 높이기 위해 Doubly Circular LinkedList로 구현했다.
0x200 0x300 0x350 0x370 0x400
0x300 0x350 0x370 0x400 0x200
0x400 0x200 0x300 0x350 0x370
0 0 0 0 0




Public constructors
생성자 설명
LinkedList() LinkedList 객체 생성
LinkedList(Collection<? extends E> c) 주어진 컬렉션을 포함하는 LinckedList 객체 생성




Public methods

List 인터페이스를 구현했기 때문에 ArrayList와 내부구현방법만 다를 뿐 제공하는 메서드의 종류와 기능은 거의 같다.
반환타입 메서드 설명
boolean add(E e) 지정된 객체를 LinkedList의 끝에 추가. 성공하면 true
void add(int index, E element) 지정된 위치에 객체 추가
boolean addAll(Collection<? extends E> c) 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가. 성공하면 true
boolean addAll(int index, Collection<? extends E> c) 지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가. 성공하면 true
void addFirst(E e) LinkedList의 맨 앞에 객체 추가
void addLast(E e) LinkedList의 맨 끝에 객체 추가
void clear() LinkedList의 모든 요소를 삭제
boolean contains(Object o) 지정된 객체가 LinkedList에 포함되어있는 지 확인
E element() LinkedList의 첫 번째 요소 반환
E get(int index) 지정된 위치의 객체를 반환
E getFirst() LinkedList의 첫 번째 요소 반환
E getLast() LinkedList의 마지막 요솔 반환
int indexOf(Object o) 지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
int lastIndexOf(Object o) 지정된 객체의 위치(끝부터 역순)를 반환
ListIterator listIterator(int index) 지정된 위치에서부터 시작하는 ListIterator 반환
boolean offer(E e) 지정된 객체를 LinkedList의 끝에 추가. 성공하면 true
boolean offerFirst(E e) LinkedList의 맨 앞에 객체 추가. 성공하면 true
boolean offerLast(E e) LinkedList의 맨 끝에 객체 추가. 성공하면 true
E peek() LinkedList의 첫 번째 요소를 반환
E peekFirst() LinkedList의 첫 번째 요소를 반환
E peekLast() LinkedList의 마지막 요소를 반환
E poll() LinkedList의 첫 번째 요소를 반환하면서 제거
E pollFirst() LinkedList의 첫 번째 요소를 반환하면서 제거
E pollLast() LinkedList의 마지막 요소를 반환하면서 제거
E pop() LinkedList의 첫 번째 요소 제거
void push(E e) LinkedList의 맨 앞에 객체 추가
E remove(int index) 지정된 위치의 객체를 LinkedList에서 제거
E remove() LinkedList의 첫 번째 요소 제거
boolean remove(Object o) 지정된 객체를 LinkedList에서 제거. 성공하면 true
E removeFirst() LinkedList의 첫 번째 요소 제거
boolean removeFirstOccurrence(Object o) LinkedList에서 첫 번째로 일치하는 객체를 제거
E removeLast() LinkedList의 마지막 요소 제거
boolean removeLastOccurrence(Object o) LinkedList에서 마지막으로 일치하는 객체를 제거
E set(int index, E element) 지정된 위치의 객체를 주어진 객체로 변경
int size() LinkedList에 저장된 객체의 수를 반환
Object[] toArray() LinkedList에 저장된 객체를 배열로 반환
T[] toArray(T[] a) LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환




ArrayList vs.LinkedList

•  순차적으로 추가/삭제 (ArrayList의 크기가 충분한 경우)
    작업 속도 :  ArrayList > LinkedList
    만일 ArrayList의 크기가 충분하지 않으면 LinkedList가 더 빠를 수 있다.

•  중간 데이터를 추가/삭제 (데이터가 많을 경우)
    작업 속도 :  ArrayList < LinkedList
    데이터의 개수가 적다면 어느 것을 사용해도 큰 차이가 없다.
컬렉션 읽기(접근시간) 추가/삭제 비고
ArrayList 빠름 느림 순차적인 추가/삭제는 더 빠름. 비효율적인 메모리 사용
LinkedList 느림 빠름 데이터가 많을 수록 접근성이 떨어짐




ArrayList & LinkedList

다루고자 하는 데이터의 개수가 변하지 않는 다면 ArrayList
데이터 개수의 변경이 잦다면 LinkedList

•  조합
    처음에 작업하기 전에 데이터를 저장할 때 ArrayList를 사용한 후
    작업할 때 LinkedList로 데이터를 옮겨서 작업하여 효율을 높일 수 있다.
ArrayList al = new ArrayList(100000);
for(int i = 0; i<100000; i++) al.add(i);

LinkedList ll = new LinkedList(al);
for(int i = 0; i<1000; i++) ll.add(500, "x");




•  참고 서적: 자바의 정석 3판 2