자료구조 간략 설명

컬렉션 프레임워크를 살펴보기 전에 자료구조에 대해 간략히 짚고 넘어가자.

ArrayList vs LinkedList

ArrayList : 물리적으로 주소가 붙어있는 구조. 자료에 대한 수정이 많지 않을 때 유리하다.
LinkedList : 물리적으로 떨어져있지만 논리적으로 연결되어있는 구조. 자료에 대한 수정이 많을 때 유리하다.

Stack vs Queue

Stack : 후입선출 방식 (LIFO: Last Insert First Out) 으로 자료를 저장하는 자료구조 가장 늦게 들어온 자료가 가장 먼제 삭제됨
Queue : 선입선출 방식 (FIFO: First Insert First Out) 으로 자료를 저장하는 자료구조 가장 먼저 들어온 자료가 가장 먼저 삭제됨

Hash

key에 대한 주소나 위치가 지정되어 있는 자료구조. 산술연산이 가능.

Binary tree

이진 자료구조.

Collection Framwork

프로그램 구현에 필요한 자료구조와 알고리즘을 구현해 놓은 라이브러리
java.utils에 구현되어 있다.
Collection Interface + Map Interface

Collection Interface

인터페이스	순서	중복	구현 클래스
List 인터페이스	O	X	ArrayList, Vector, LinkedList, Stack, Queue
Set 인터페이스	X	O	HashSet, TreeSet

List Interface

Collection Interface의 하위 인터페이스
객체를 순서에 따라 저장하고 관리하는데 필요한 메소드가 선언되어 있다.
배열의 기능을 구현
하위 클래스 : ArrayList, Vector, LinkedList

ArrayList, Vector

객체 배열 클래스
Vector : java 2 부터 제공된 클래스, 멀티 쓰레드 프로그램에서 동기화 지원
일반적으로는 ArrayList를 많이 사용

ArrayList vs LinkedList

ArrayList : 논리적순서, 물리적순서가 동일, i번째 위치 접근이 빠르다.
LinkedList : 논리적순서는 순차적이지만, 물리적으로 순차적이지 않을 수 있다. 자료 추가 및 삭제에 유리

linkedList의 구조

linkedList의 메커니즘

Stack, Queue

Stack : LIFO

Stack

ArrayList로 Stack구현하기

class MyStack{
  private ArrayList<String> arrayStack = new ArrayList<String>();

  public void push(String data){
    arrayStack.add(data);
  }

  public void pop(){
    int len = arrayStack.size();
    if(len == 0){
      System.out.println("스택이 비었습니다.");
      return null ;
    }
    return arrayStack.remove(len-1);
  }
}

Queue : FIFO

Stack

Iterator interface

Set interface를 보기 전에 Iterator 인터페이스에 대해 먼저 알아보자.
Collection의 객체를 순회하는 인터페이스이다.
Collection 객체를 Iterator 객체화 하기 : Iterator ir = anyCollectionObj.iterator();
Iterator 객체의 Method

메소드	설명
boolean hasNext()	이후에 요소가 있는지 체크, 요소가 있다면 true반환
E next()	다음 요소를 반환

Set Interface

Collection 하위 인터페이스
중복 허용하지 않음
순서 없음 -> iterator로 순회
하위 구현 클래스로는 HashSet, TreeSet이 있다.

HashSet

중복을 허용하지 않으므로, 객체의 동일함 여부를 알기 위해 equals(), hashCode()메소드를 재정의 해야 한다.

TreeSet

객체의 정렬에 사용되는 클래스
오름차순(Default), 내림차순(비교메소드가 반대 부호를 반환하도록 한다)으로 정렬 가능
내부적으로 이진검색트리(binary search tree)로 구현되어 있음
이진 검색 트리에 자료가 저장될 때 비교하여 저장될 위치를 정함
객체 비교를 위해 Comparable/Comparator 인터페이스를 구현해야 함.

Comparable
- treeSet의 원소를 String으로 잡을 시, String클래스에 이미 Comparable인터페이스가 구현되어 있어, 객체를 넣기만 해도 treeSet내부에서 정렬이 된다.
- Comparable인터페이스가 구현되어 있지 않으면, treeSet이 어떤 순서로 객체를 저장해야할지 모르기 때문 에 에러가 발생한다. comapareTo 를 재정의 해주면 된다.
Comparator
- compare메소드를 재정의 해주면 된다.

Map Interface

key-value 쌍 구조로 되어있고 key는 중복되지 않는다.
검색을 위한 자료구조
내부적으로 hash방식으로 구현 됨
객체의 유일성함의 여부를 알기 위해 equals(), hashCode()메소드를 재정의 한다.

HashMap, HashTable

Map 인터페이스를 구현한 하위 클래스중 가장 일반적으로 사용하는 클래스
HashTable 클래스는 java2부터 제공된 클래스이고, Vector처럼 동기화 제공
pair자료를 쉽고 빠르게 관리 가능

TreeMap

key 객체를 정렬하여 key-value를 pair로 관리하는 클래스
key를 Comparable, Comparator인터페이스 구현하여 사용