Pw4ngC0

컬렉션 프레임워크의 핵심 인터페이스

1.List : 순서가 있는 데이터 집합. 데이터 중복 허용

구현 클래스 - ArrayList, LinkedList, Stack, Vector 등

2.Set : 순서가 없는 데이터 집합. 데이터 중복 허용하지않는다.

구현 클래스 - HashSet, TreeSet 등

3.Map : 키(key)와 값(value)의 쌍으로 이루어진 데이터 집합. 순서가 없고, 키의 중복은 허용하지않으며, 값의 중복은 허용한다.

구현 클래스 - HashMap, TreeMap 등

List와 Set의 공통부분을 뽑아 새로운 인터페이스 Collection을 추가로 정의했다.

구현클래스의 특징

List

1.ArrayList : 배열 기반. 데이터의 추가 삭제의 성능이 좋지않다. 임의의 요소에 대한 접근성이 뛰어나다.

2.LinkedList : 연결기반. 데이터의 추가와 삭제에 성능이 좋다. 접근성(탐색)이 좋지않다.

3.Stack : LIFO(Last In First Out) 후입 선출의 특성을 가진다.

4.Queue : LinkedList기반으로 만들어 졌으며 FIFO(First In First Out)의 특성을 가진다.

Set

1.HashSet : HashMap을 이용해서 구현했으며 해싱기법에 의해 데이터가 저장된다.

2.TreeSet :  TreeMap을 이용해서 구현했으며 이진

Map

1.HashMap : 배열과 연결(LinkedList)의 결합된 형태이다. 데이터의 추가, 삭제, 검색 등 모두 띄어나다.

2.TreeMap : 연결(LinkedList)기반으로 만들어졌다. 정렬과 탐색에 적합하다. 기본적으로 데이터들의 key들이 오름차순으로 정렬된다.

Map

Map : 인터페이스로 키(key)와 값(value)을 한쌍으로 가지는 데이터를 저장하는 특징이있다.

         키(key)는 중복을 허용하지 않으며, 값(value)의 경우 중복이 가능하다.

HashMap의 경우 해싱(hasing)기법을 이용하여 데이터를 저장하기 때문에 많은 양의 데이터를 저장하고 있는 경우 검색기능에서 뛰어난 성능을 가진다. 

HashMap은 키(key)와 값(value)를 가지는 Entery 내부클래스를 정의하고 Entry 배열을 선언하여 사용한다.

HashMap에서 key와 value는 모두 Object타입으로 선언되어있다. 그러므로 어떤 객체도 HashMap컬렉션에 저장될 수 있다.

메서드

HashMap() : HashMap객체를 생성

HashMap(int initialcapacity) : initialCapacity크기 만큼의 HashMap을 생성한다.

void clear() : HashMap의 모든 객체 제거

Object clone() : HashMap을 복제해서 반환

boolean containsKey(Object key) : HashMap에 key가 존재하는지 확인

boolean containsValue(Object value) : HashMap에 value가 존재하는지 확인

Set entrySet() : HashMap에 저장된 키와 값을 엔트리(키와 값의 결합)형태로 Set에 저장하여 반환

Object get(Object key) : key에 해당하는 value 반환

boolean isEmpty() : HashMap이 비어있는지 알려준다.

Set keySet() : HashMap의 모든 key를 Set으로 반환

Object put(Object key, Object value) : 지정된 키와 값을 HashMap에 저장

void pushAll(Map m) : Map에 저장된 모든 요소를 HashMap에 저장한다.

Object remove(Object key) : HashMap에서 지정된 키로 저장된 객체를 삭제

Object replace(Object key, Object value) : key에 해당하는 value를 매개변수 value로 교체한다.

boolean replace(Object key, Object oldvalue, Object newvalue) : key와 oldvalue가 일치하는 객체를 새로운 객체 Object newvalue로 교체한다.

int siez() : HashMAp에 저장된 요소의 개수를 반환

Collection values() : HashMap에 저장된 모든 값을 컬렉션 형태로 반환

key를 id, value를 비밀번호로 가정하여 데이터를 저장하고 탐색하였다.

HashMap.put()에서 key가 중복되는 경우 뒤에 저장한값이 덮어쓴다.

Map의 모든 요소들을 출력할때는 HashMap.entrySet()을 통해 Set으로 반환하고 Iterator를 통해 각 요소들에 접근한다.

위 예제는 HashMap의 value가 HashMap인 형태인 경우이다.

해싱과 해시함수

해싱 : 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법

해싱을 구현한 컬렉션 클래스에는 HashSet, HashMap, Hashtable 등잉 있다.

해싱에서는 일반적으로 배열과 링크드 리스트의 자료구조 조합을 사용한다.

TreeMap

TreeMap은 이진검색트리의 형태로 키와 값의 쌍으로 만들어진 데이터를 저장한다.HashMap보다 TreeMap이 검색성능은 더 뛰어나지만 다른 기능들은 대부분 HashMap을 사용하는것이 좋다. 정렬이 필요한경우 TreeMap이 좋다.

TreeMap에 data의 문자들을 저장한다. 해당 문자를 Key로하고 문자의 중복수를 value로 TreeMap에 저장한다.

TreeMap에 의해 Key가 오름차순으로 자동정렬되는것을 볼 수 있다. 이후 TreeMap을 Set으로 변환하고 정렬 기준을 새롭게 주어 중복수가 많은 순으로 저장되게 하였다.

Collections

동기화 컬렉션

멀티 쓰레드 프로그래밍에서 하나의 컬렉션에대해 여러 쓰레드가 동시에 접근하는 경우가 생길 수 있다. 이러한 경우 사용하면 좋은것이 동기화 컬렉션이다. 동기화 컬렉션을 통해 멀티쓰레드 환경에서 컬렉션 동시접근 충돌을 방지할 수 있다.

static Collection synchronizedCollection(Collection c)

static List synchronizedList(List list)

static Set synchronizedSet(Set s)

static Map synchronizedMap(Map m)

static SortedSet synchronizedSortedSet(SortedSet s)

static SortedMap synchronizedSortedMap(SortedMap m)

ex)

List syncList = Collections.synchronizedList(new ArrayList(...));

변경불가 컬렉션(상수 컬렉션)

컬렉션을 변경할 수 없도록 생성할 수 있다. 해당 컬렉션은 읽기전용인 컬렉션이다.

static Collection unmodifiableCollection(Collection c)

static List unmodifiableList(List list)

static Set unmodifiableSet(Set s)

static Map unmodifiableMap(Map m)

static NavigableSet unmodifiableNavigableSet(NavigableSet s)

static SortedSet unmodifiableSortedSet(SortedSet s)

static NavigableMap unmodifiableNavigableMap(NavigableMap m)

static SortedMap unmodifiableSortedMap(SortedMap m)

싱글톤 컬렉션(객체 하나만 저장하는 컬렉션)

static List singletonList(Object o)

static Set singleton(Object o)

static Map singletonMap(Object key, Object value)

한종류의 객체만 저장하는 컬렉션

static Collection checkedCollection(Collection c, Class type)

static List checkedList(List list, Class type)

static Set checkedSet(Set s, Class type)

static Map checkedMap(Map m, Class keyType, Class valueType)

static Queue checked Queue(Queue queue, Class type)

static NavigableSet checkedNavigableSet(NavigableSet s, Class type)

static SortedSet checkedsortedSet(SortedSet s, Class type)

static NavigableMap checkedNavigableMap(NavigableMap m, Class keyType, Class valueType)

static SortedMap checkedSortedMap(SortedMap m, Class keyType, Class valueType)

 한종류의 객체만 저장하는 컬렉션의 경우 제네릭스(Generics)로 충분히 가능할것 같다.

HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이다.

Set의 특징은 중복을 허용하지않으며 순서가 없다는 것이다.

HashSet을 이용하여 컬렉션 내의 중복 요소들을 제거할 수 있다.

메서드

hashSet() :  HashSet객체를 생성하는 생성자이다.

HashSet(Collection c) : 컬렉션 c를 포함하는 HashSet을 생성하는 생성자이다.

HashSet(int initialCapacity) : 주어진 값을 초기 용량으로하는 HashSet객체를 생성한다.

HashSet(int initialCapacity, float loadFactor) : 초기 용량과 load factor를 지정하는 생성자.

load factor는 저장공간을 늘리는 기준 같은것이다. 0.8로 지정하면 기존 저장공간의 80%가 채워졌을 때 해당 저장공간을 두배로 늘린다.

boolean add(Object o ) : 새로운 객체 o를 hashset에 추가한다.

boolean addAll(Collection c) : 주어진 컬렉션 c를 hashset에 추가한다. 컬렉션을 추가할때는 addAll, 객체를 추가할 때는 add 를 사용한다.

void clear() : hashset에 존재하는 모든 요소들을 삭제한다.

Object clone() : HashSet의 복제를 반환한다. 주소복사가 아닌 값복사이다.(얕은 복사)

boolean contains(Object o) : 지정된 객체를 포함하고 있는지 확인한다.

boolean containsAll(Collection c) : 컬렉션 c가 가지고있는 요소들을 hashset이 가지고있는지 확인한다.

객체의 탐색은 contains 컬렉션의 탐색은 containsAll로 가능하다.

boolean isEmpty() : HashSet이 비어있는지 확인한다.

Iterator iterator() : Iterator 객체를 반환한다.

boolean remove(Object o) : HashSet에서 객체  o를 찾아 삭제한다. 성공하면 true, 실패하면 flase

boolean removeAll(Collection c) : HashSet에 존재하는 요소중 모든 Collection c에 존재하는 요소와 일치하는 요소들을 삭제한다.

boolean retainAll(Collection c) : 주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 모두 삭제한다.

int size() : 지정된 객체의 수를 반환한다.

Object[] toArray() : 객체들을 객체배열 형태로 반환한다.

Obect[] toArray(Object[] a) : 저장된 객체들을 주어진 객체배열 a에 넣는다.

Set의 add예시이다. add메소드 사용시 중복된 값들은 false가 리턴되며 Set에 저장되지 않는다.

Interger 1과 String 1은 다르기 때문에 해당 Set에 저장될 수 있다.

사용자 정의클래스의 객체를 Set에 저장할 경우 equals()와 hashCode()를 적절하게 오버라이딩 해주어야 한다. 오버라이딩 해주지 않을경우 같은 속성값을 갖는 객체가 Set에 함께(중복) 저장될 수 있다.

중복된 값은 저장되지 않는 특징을 이용하여 각 합집합, 교집합, 차집합 등을 만들수 있다.

TreeSet

TreeSet은 이진 탐색 트리(Binary Search tree)라는 자료구조 형태로 데이터를 저장하는 컬렉션이다.

Set인터페이스 기반으로 구현했으며 중복 저장은 되지않으며 저장순서를 유지하지 않습니다. 이진 탐색트리 구조형태로 저장되기 때문에 객체 추가 및 저장시 자동으로 정렬됩니다.

메서든 대부분 HashSet메서드와 유사하며 별도로 사용하는 메서드들이 존재합니다.

메서드

Object ceiling(Object o) : 지정된 객체와 같은 객체를 반환. 없는 경우 큰값중 Object o와 가장 가까운 값을 반환

Object floor(Object o) : 지정된 객체와 같은 객체를 반환. 없는 경우 작은값중 Object o와 가장 가까운 값을 반환

Comparator comparator() : TreeSet의 정렬기준(Comparator)를 반환한다.

NavigableSet descendingSet() : TreeSet에 저장된 요소들을 역순으로 정렬하여 반환한다.

SortedSet headSet(Object toElement) : 지정된 객체보다 작은 값의 객체들을 반환한다.

SortedSet tailSet(Object fromElement) : 지정된 객체보다 큰 값의 객체들을 반환한다.

SortedSet subSet(Object fromElement, Object toElement) : 범위검색(fromElement와 toElement 사이)의 결과를 Set형태로 반환한다.

Object first() : 정렬된 순서에서 첫번째 객체를 반환한다. 일반적으로 가장 작은 객체이다.  

Object last() : 정렬된 순서에서 가장 큰값을 반환한다. 일반적으로 가장 큰 객체이다.

Object pollFirst() : TreeSet의 첫번째 요소

Object pollLast() : TreeSet의 마지막 번째 요소

TreeSet()의 경우 이진탐색 트리 자료구조를 가지기 때문에 값 삽입과 동시에 정렬이 된다.

문자열 TreeSet

subSet메서드를 통해 정렬된 Set을 잘라서 반환할수 있습니다.

Arrays

Java에서 제공하는 Arrays클래스에는 배열을 다루는데 유용한 많은 메서드들을 정의하고 있다.

메서드

copyOf(), copyOfRange() : 배열 전체 또는 일부를 복사하여 새로운 배열을 만든후 반환한다.

fill(), setAll() : 배열의 모든 공간을 지정한 값으로 채운다. setAll 의경우 배열을 채우는데 사용할 인터페이스 또는 람다식 식을 지정해 줄 수 있다.

sort() : sort는 배열을 정렬할 때 사용한다. 

binarySearch() : 정렬된 배열에서 특정 값을 검색할때 사용한다.

equals(),deepEquals() : 배열에 저장된 요소를 비교할때 사용한다. 다차원 배열에서는 deepEquals()를 사용한다. 

toString(), deepToString() : 배열에 저장된 요소들을 출력해줄때 사용한다. 다차원배열의 경우 deepToString()을 사용한다.

asList(Object... a) : 배열을 List로 반환한다. asList가 반환한 List의 크기는 변경이 불가능하고 크기를 변경해야한다면

                          List list = new ArrayList(Arrays.asList(1,2,3,4,5)) 등으로 생성하는것이 좋다.

Comparator & Comparable

comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있다.

Comparable : 기본 정렬기준을 구현하는데 사용.

Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용

상속받은 클래스에서 Comparartor 인터페이스의 compare() 또는 Comparable인터페이스의 compareTo() 메소드를 구현하여 정렬기준을 만든다. 

역순으로 정렬할 경우  *-1을 해주면된다.

Iterator, ListIterator, Enumeration 모두 컬렉션에 저장된 요소들에 접근하는데 사용되는 인터페이스이다.

Iterator

컬렉션에 저장된 요소들을 읽어오는 방법을 표준화 하였다. 컬렉션에 저장된 요소들에 접근하는 기능을 가진 Iterator 인터페이스를 정의하고, Collection인터페이스에 Iterator를 반환하는 iterator()를 정의한다.

iterator() 메서드는 Collection인터페이스에 정의된 메서드로 Collection 인터페이스의 자손인 List와 Set에도 포함되어있다. 

Iterator 메서드

boolean hasNext() : 읽어올 다음 요소가 존재하는지 확인한다. 있으면 true, 없으면  false

Object next() : Iterator를 다음요소로 이동시켜 다음요소를 읽어온다. hasNext()로 다음요소가 존재하는지 확인하고 사용하는것이 좋다.

void remove() : next()로 읽어 온 요소를 삭제한다.

사용예시

iterator 생성자를 통해 ArrayList에 대한 iterator를 생성해서 가져온다. 이후 hasNext()와 next를 이용해 요소들에 하나씩 접근하여 출력한다.

Enumeration

Enumeration은 컬렉션 프레임워크가 만들어지기 전에 사용하던 것으로 Iterator의 구버전이라고 생각하면 된다.

Enumeration 메서드

boolelan hasMoerElements() : 읽어올 다음 요소가 존재하는지 확인한다. Iterator의 hasNext()메서드와 같다.

Object nextElement() : 다음 요소를 읽어온다. Iterator의 next()와 같다.

ListIterator

Iterator를 상속받아 기능을 추가한것으로 ArrayList, LinkedList와 같이 List인터페이스를 구현한 컬렉션에서만 가능하다.

ListIterator 메서드

void add(Object o) : 컬렉션에 새로운 객체 o를 추가한다.

boolean hasNext() : 읽어올 다음 요소가 존재하는지 확인한다.

boolean hasPrevious() : 읽어올 이전 요소가 존재하는지 확인한다.

Object next() : 다음요소를 읽어온다. 사용하기 전에 hasNext()로 다음요소가 존재하는지 확인하고 사용하는것이 좋다.

Object previous : next()와 반대로 이전요소를 읽어온다. previous()를 호출하기 전에 hasPrevious()를 호출해서 읽어올 요소가 있는지 확인하고 사용하는것이 좋다.

int nextIndex() : 다음 요소의 index를 반환한다.

int previousIndex() : 이전 요소의 index를 반환한다.

void remove() : next(), previous() 호출 이후 사용하는 메서드로  next(), previous()메서드로 읽어온 객체를 삭제한다.

void set(Object o) : next(), previous() 호출 이후 사용하는 메서드로  next(), previous()메서드로 읽어온 객체를 o로 변경한다.

remove 사용예시

while문 내부를 보면 next()메서드를 통해 다음요소에 접근한 후 remove()를 호출하는 것을 알 수 있다.

iterator가 작동한 original의 모든 요소들이 삭제되었다.

Stack

스택 : 마지막에 저장한 데이터를 가장먼저 꺼내는 LIFO(Last In First Out)구조

Stack은 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.

메서드

boolean empty() : Stack이 비어있는지 알려ㅜㄴ다.

Object peek() : Stack의 맨위에 저장된 객체를 반환. pop()과 달리 데이터를 객체에서 꺼내지는 않는다.

Object pop() : Stack의 맨위에 저장된 개개체를 꺼낸다.

Object push(Object o) : Stack에 객체 o를 저장한다.

int search(Object o) : Stack에서 객체 o의 위치를 반환한다. Stack에 존재하지 않으면 -1반환

스택은 수식괄호검사, 웹브라우저의 뒤로/앞으로 등에 사용된다.

Queue

 큐 : 처음에 저장한 데이터를 가장먼저 꺼내어 삭제하게되는 FIFO(First In First Out)구조로 되어있다. 큐는 한방향으로 넣고 한방향으로 빼는 파이프와 같은 구조로 되어있다.

Queue는 꺼낼때 항상 첫번째 저장된 데이터를 삭제한다.

배열기반 컬렉션 클래스에서는 데이터를 꺼낼때마다 빈공간을 채우기위해 데이터 복사가 발생하므로 비효율적이다. 

Queue는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는것이 더 적합하다.

메서드

boolean add(Object o) : Queue에 객체 o를 추가한다.

Object remove() : Queue에서 객체를 삭제 반환한다.

Object element() : 삭제없이 요소를 읽어온다.

boolean offer(Object o) : Queue에 객체 o를 저장한다.

Object poll() : Queue에서 객체를 꺼내서 반환한다.

Object peek() : 삭제없이 요소를 읽어온다.

Queue는 인터페이스이다. 그러므로 사용하기 위해서는 Queue인터페이스를 상속받아 구현되어있는 LinkedList클래스를 사용한다.

Queue는 최근사용문서, 버퍼 등에 사용된다.

Priority Queue

Queue인터페이스의 구현체중 하나로, 저장한 순서에 상관없이 우선순위(priority)가 높은 순서대로 꺼내는 특징있다.

PriorityQueue는 저장공간으로 배열을 사용하며 heap 자료구조의 형태를 가진다.

poll을 통해 Priority Queue에 저장된 객체들을 꺼낼경우 우선순위 순서대로 꺼내진다.

ArrayList

ArrayList는 List인터페이스를 조상으로 갖는 클래스이며 Object배열을 이용하여 데이터를 순차적으로 저장한다.

배열에 순차적으로 저장되며 배열에 더이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성하여 기존에 저장되어있던 데이터들을 복사하여 새로운 배열에 저장한다.

ArrayList의 메서드

생성자

ArrayList() : 크기가 10인 ArrayList를 생성한다.

ArrayList(Collection c) : 주어진 컬렉션이 저장된 ArrayList를 생성한다.

ArrayList(int initialCapacity) : 지정된 초기용량을 갖는 ArrayList를 생성한다.

추가

boolean add(Object o) : ArrayList의 마지막에 객체를 추가한다. 성공하면 true를 반환한다.

void add(int index, Object element) : index위치에 element객체를 저장한다. index와 index이후에 저장되어있던 객체들은 한칸씩 뒤로 이동한다.

boolean addAll(Collection c) : 주어진 컬렉션의 모든 객체를 저장한다.

boolean addAll(int index, Collection c) : index위치부터 컬렉션을 저장한다.

삭제

void clear() : ArrayList를 비운다. ArrayList에 존재하는 모든 객체들 삭제

Object remove(int index) : index위치에 존재하는 객체를 삭제한다. index 이후에 존재하는 객체들은 한칸씩 앞으로 이동한다.

boolean remove(Object o) : o와 일치하는 객체를 찾아 제거한다. 성공하면 true 실패하면 false

boolean removeAll(Collection c) : 컬렉션 c에 저장된 객체들과 일치하는 모든 객체들을 제거한다.

boolean retainAll(Collection c) : 컬렉션 c에 저장된 객체들과 일치하는 객체들만 남겨두고 다른 객체들은 모두 삭제한다.

검색

boolean contains(Object o) : ArrayList에 객체 o가 존재하는지 확인한다. 존재한다면 true 반환

Object get(int index) : index에 저장된 객체를 반환한다.

int indexOf(Object o) : 객체 o 와 일치하는 객체를 찾아 해당 객체의 index를 반환한다.

int lastIndexOf(Object o) : indexOf와 같은기능을 수행하지만 lastIndexOf는 ArrayList의 마지막부터 앞쪽으로 객체를 탐색한다.

변경

Object set(int index, Object element) : index위치에 element를 저장한다.

외의 메서드

Object clone() : ArrayList를 복사한다.

void ensureCapacity(int minCapacity) : ArrayList의 용량이 최소한 minCapacity가 되도록 한다.

boolean isEmpty() : ArrayList가 비어있는지 확인한다.

Iterator iterator() : ArrayList의 Iterator객체를 반환

ListIterator listIterator() : ArrayList의 ListIterator를 반환

ListIterator listIterator(int index) : ArrayList의 index부터 시작하는 Iterator 반환

int size() : ArrayList에 저장된 객체의 수를 반환

void sort(Comparator c) : 정렬기준 c로 ArrayList를 정렬

List subList(int fromIndex, int toIndex) : fromIndex부터 toIndex사이에 저장된 객체를 반환한다.

Object[] toArray() : ArrayList에 저장된 모든 객체들을 객체배열로 반환한다.

Object[] toArray(Object[] a) : ArrayList에 저장된 모든 객체들을 객체배열 a에 담아 반환한다.

void trimToSize() : 빈공간, 공백을 지워 용량을 크기에맞게 줄인다.

ArrayList에서 삭제연산시 for문에서 변수 i를 증가시키는 식으로 삭제를 할경우 원하는 결과를 얻기 어려울 수 있다.

왜냐하면 ArrayList에 존재하는 객체를 삭제할경우 해당 빈칸을 삭제한 index의 이후 객체들이 빈칸을 채우기 때문이다.

삭제연산을 해야할경우 마지막요소부터 앞으로 순서대로 탐색하며 삭제하는 것이 좋다.

LinkedList

배열의 단점

1.크기를 변경이 불가능하다.

-크기 변경이 불가능하기 때문에 더 큰크기의 새로운 배열을 생성하여 값을 복사하애야한다.

-충분히 더 큰 크기의 배열을 생성하는 과정에서 메모리가 낭비된다.

2.비순차적 데이터의 추가 및 삭제에 시간이 많이걸린다.

-배열의 중간에 데이터를 추가하면 빈공간을 만들기 위해 다른 데이터들을 복사하여 이동시켜야한다.

-배열의 중간에 데이터를 삭제하면 빈공간을 채우기 위해 다른 데이터들을 복사하여 이동시켜야한다.

배열을 단점을 보완하기 위해 링크드 리스트(Linked List)라는 자료구조가 생성되었다.

링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있다.

링크드 리스트는 각요소들은 자신과 연결된 다음 요소에 대한 주소와 데이터로 구성되어있다.

링크드리스트에서의 삭제와 추가는 간단하다. 삭제의 경우 삭제하고자하는 노드의 이전노드가 다음노드로 삭제할노드의 다음노드를 가리키면 연결은 유지되면서 노드삭제가 가능하다.

추가 또한 노드를 생성하고 생성한 노드의 이전노드가 다음노드로 생성한노드를 가리키게하면되고 기존에 가리키던 다음노드를 생성된 노드가 가리키면 된다.

위의 그림은 단방햔 링크드리스트이지만 이전노드를 가리키는 더블링크드 리스트도 있다.

더블링크드 리스트는 단방향 링크드리스트와 다르게 이전노드에 대한 접근도 간편하다.

자바의 LinkedList클래스는 더블링크드 리스트 구조로 구현되어있다. 또한 Queue인터페이스와 Deque인터페이스를 구현하도록 되어있다.

LinkedList의 메서드

생성자

LinkedList() : LinkedList객체 생성

LinkedList(Collection c) : 컬렉션 c를 포함하는 LinkedList생성

추가

boolean add(Object o) : 객체 o 를 LinkedList의 끝에 추가한다. 성공하면 true, 실패하면 false

void add(int index, Object element) : index 위치에 element 객체를 추가

boolean addAll(Collection c) : 컬렉션 c의 모든 요소들을 LinkedList에 추가. 성공하면 true, 실패하면 false

boolean addAll(int index, Collection c) : index위치에 컬렉션 c의 모든 요소들 추가. 성공하면 true, 실패하면 false

boolean offer(Object o) : 객체 o를 LinkedList의 끝에 추가한다.

void addFirst(Object o) : 객체 o를 LinkedList 맨앞에 추가

void addLast(Object o) : 객체 o를 LinkedList 맨뒤에 추가

boolean offerFirst(Object o) : 객체 o를 LinkedList 맨앞에 추가

boolean offerLast(Object o) : 객체 o 를 LinkedList 맨뒤에 추가

void push(Object o) : addFirst()와 동일하다.

삭제

void clear() : LinkedList의 모든 요소를 삭제한다.

Object remove(int index) : index의 객체를 LinkedList에서 삭제한다.

boolean remove(Object o) : 객체 o를 LinkedList에서 제거한다.

boolean removeAll(Collection c) : Collection c에 존재하는 객체들과 일치하는 요소들을 모두 삭제한다.

boolean retainAll(Collection c) : Collection c에 존재하는 객체들과 일치하는 요소들만 남겨두고 나머지는 삭제한다.

Object poll() : LinkedList의 첫번째 요소를 반환. 제거한다.

Object remove() : LinkedList의 첫번째 요소를 제거한다.

Object pollFirst() : LinkedList의 첫번쨰 요소를 반환하면서 제거

Object pollLast() : LinkedList의 마지막 요소를 반환

Object pop() : removeFirst()와 동일하다.

Object removeFirst() : 첫번째요소를 제거한다.

Object removeLast()  : 마지막요소를 제거한다.

boolean removeFirstOccurrence(Object o) : LinkedList에서 첫번째로 일치하는 객체를 제거한다.

boolean removeLastOccurrence(Object o) : LinkedList에서 마지막으로 일치하는 객체를 제거한다.

탐색

boolean contains(Object o) : 지정된 객체가 LinkedList에 포함되어있는지 알려줌

boolean containsAll(Collection c) : 지정된 컬렉션의 모든 요소가 포함되어있는지 알려줌

Object get(int index)  : 지정된 위치의 객체를 반환

int IndexOf(Object o) : 지정된 객체가 저장된 위치를 반환

Object peek() : LinkedList의 첫번째 요소 반환

Object getFirst() : LinkedList 첫번째 요소 반환

Object getLast() : 마지막 요소반환

Object peekFrist() : LinkedList의 첫번째 요소 반환

Object peekLast() : LinkedList 첫번째 요소 반환

ArrayList, LinkedList 비교

1.순차적으로 추가/삭제 하는 경우 ArrayList가 더 빠르다.

2.중간 데이터를 추가/삭제 하는 경우 LinkedList가 더 빠르다.

3.데이터의 개수가 많아질수록 데이터를 읽어오는 시간은 불연속적인 LinedList가 더 오래걸린다.

컬렉션 프레임웍 : 데이터 군을 저장하는 클래스들을 표준화한 설계

컬렉션 프레임웍은 컬렉션, 다수의 데이터를 다루는데 필요한 다양한 클래스들을 제공해준다. 또한 인터페이스와 다형성을 이용한 객체 지향적 설계를 통해 사용법을 익히기에도 편리하고 재사용성이 높은 코드를 작성할 수 있다.

컬렉션 프레임웍의 핵심 인터페이스

컬레션 프레임웍에서 컬렉션 데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다.

1.List : 순서가 있는 데이터 집합. 데이터의 중복을 허용한다.

2.Set : 순서를 유지하지 않는 데이터의 집합. 데이터의 중복을 허용하지 않는다.

3.Map : 키(key)와 값(value)의 쌍으로 이루어진 데이터의 집합. 순서는 유지되지않으며, 키는 중복을 허용하지 않는다. 값은 중복을 허용한다.

인터페이스 List와 Set을 구현한 컬렉션 클래스들은 많은 공통부분이 있어, 공통된 부분을 다시 뽑아 Collection인터페이스로 정의할 수 있었지만 Map인터페이스는 전혀다른 형태로 컬렉션을 다룬다.

Collection인터페이스

List와 Set의 조상 Collection인터페이스의 메소드

boolean add(Object o), boolean addAll(Collection c) : 지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가한다.

void clear() : Collection의 모든 객체를 삭제한다.

boolean contains(Object o) , boolean containsAll(Collection c) : 지정된 객체(o)또는 Collection의 객체들이 Collection에 포함되어있는지 확인한다.

boolean equals(Object o) : 동일한 Collection인지 비교한다.

int hashCode() : Collection의 hash code를 비교한다.

boolean isEmpty() : Collection이 비어있는지 확인한다.

Iterator iterator() : Collection의 Iterator를 얻어서 반환한다.

boolean remove(Object o) : 지정된 객체를 삭제한다.

boolean removeAll(Collection c) : 지정된 Collection에 포함된 객체들을 삭제한다.

boolean retainAll(Collection c) : 지정된 Collection에 포함된 객체만 남기고 다룬 객체들은 Collection에서 삭제한다.

Colection에 변화가 생길경우 true반환 변화 없으경우 false반환

int size() : Collection에 저장된 객체의 개수를 반환한다.

Object[] toArray() : Collection에 저장된 객체배열을 Obejct[]로 반환한다.

Object[] toArray(Object[] a) : 지정된 배열에 Collection의 객체를 저장해서 반환한다.

List인터페이스

List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용한다.

List인터페이스의 메서드, Collection인터페이스에서부터 상속받은것은 제외

void add(int index, Object element), boolean addAll(int index, Collection c) : 지정된 위치(index)에 객체(element) 또는 컬렉션에 포함된 객체들을 추가한다.

Object get(int index) : 지정된 위치(index)에 있는 객체를 반환한다.

int indexOf(Object o) : 지정된 객체의 위치(index)를 반환한다.

int lastIndexOf(Object o) : 지정된 객체의 위치(index)를 반ㄴ환한다. List의 마지막 요소부터 역방향으로 찾는다.

ListIterator listIterator(), ListIterator listIterator(int index) : List의 객체에 접근할 수 있는 ListIterator를 반환한다.

Object remove(int index) : 지정된 위치(index)에 있는 객체를 삭제하고 삭제된 객체를 반환한다.

Object set(int index, Object element) : 지정된 위치(index)에 객체(element)를 저장한다. 객체를 변경할떄 사용한다.

void sort(Comparator c) : 지정된 비교자(comparator)로 List를 정렬한다.

List subList(int fromIndex, int toIndex) : 지정된 범위에 있는 객체를 반환한다.

Set인터페이스

Set인터페이스는 중복을 허용하지 않고 순서도 유지되지않는 컬렉션 클래스를 구현하는데 사용된다.

메서드는 Collection메서드와 일치한다.

Map인터페이스

Map인터페이스는 키(key)와 값(value)을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다. 키는 중복될 수 없지만 값은 중복을 허용한다. 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게된다.

Map 인터페이스 메소드

void clear() : Map의 모든 객체를 삭제한다.

boolean containsKey(Object key) : 지정된 key객체와 일치하는 Map의 key객체가 있는지 확인한다.

boolean containsValue(Object value) : 지정된 value객체와 일치하는 Map의 value객체가 있는지 확인한다.

Object get(Object key) : 지정한 key객체에 대응하는 value객체를 찾아서 반환한다.

Set entrySet() : Map에 저장되어 있는 key-value쌍을 Map.Entry타입의 객체로 저장한 Set으로 반환한다.

boolean equals(Object o) : 동일한 Map인지 비교한다.

int hashCode() : 해시코드를 반환한다.

boolean isEmpty() : Map이 비어있는지 확인한다.

Set keySet() : MAp에 저장된 모든 key객체를 반환한다..

Object put(Object key, Object value) : Map에 value객체를 key객체에 연결(mapping)하여 저장한다. 객체를 삽입할 때 사용한다.

void putAll(Map t) : 지정된 Map의 모든 key-value쌍을 추가한다.

Object remove(Object key) : 지정한 Key객체와 일치하는 kecy-value객체를 삭제한다.

int size() : Map에 저장된 key-value 쌍의 개수를 반환한다.

Collection values() : Map에 저장된 모든 value객체를 반환한다.

values()메서드의 반환타입은 Collection이고, keySet()메서드에서는 반환타입이 Set이다. Map인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection타입으로 반환하고, 키(key)는 중복을 허용하지 않기 때문에 Set타입으로 반환한다.