YEJIN LEE

“Keep turnin’ the pages”

2 minute read

List implementation 리스트 구현

✏️ArrayList

  • 가변크기의 배열을 구현한 컬렉션 클래스
  • java.util.ArrayList
  • 삽입과 삭제가 어려움 (스레드 간에 동기화를 지원하지 않기 때문)

  • 비순차 접근이 쉬움

  • method
    • Object get(int index) : 리스트 내의 요소 위치 리턴
    • Object set(int index, Obj element) : 인덱스 위치의 요소를 수정
    • void add(int index, Obj element) : 인덱스 위치에 요소 삽입
    • Object remove(int index) : 인덱스 위치의 요소 삭제
    • void ensureCapacity() : 많은 요소를 추가하기 전에 리스트 용량을 늘림

✏️LinkedList

  • List 인터페이스를 구현한 클래스
  • java.util.LinkedList
  • 요소들을 양방향으로 연결하여 관리
  • 삽입과 삭제가 쉬움
  • 노드에 요소를 저장
  • 각 노드는 다음 노드와 링크되어 있음

  • 순차 접근이 편함 (random access는 어려움)

  • method

    • listIterator() : Listiterator는 iterator를 상속받아 여러 기능을 추가한 클래스로 기능적으로만 본다면 ArrayList의 업그레이드 버전.
      배열로 친다면 다차원 배열, 양방향을 지원(hasPrevious())

    • add() : 요소 추가

    • remove() :　마지막으로 리턴된 요소 삭제

    • void addFirst(Object o) / void addLast(Object o) : 맨 앞/뒤 위치에 요소를 추가

    • Object getFirst() / Object getLast() : 맨 앞/뒤 위치의 요소를 리턴

    • Object removeFirst() / Object removeLast() : 맨 앞/뒤 위치의 요소를 삭제

Set

✏️HashSet

  • Set(집합) : 클래스로써 객체를 중복해서 저장할 수 없고 순차적으로 저장X

  • HashSet : 요소의 검색과 추가가 매우 빠름. 비선형 구조 -> 순서 없음, 인덱스 없음

  • Hashing : 수많은 데이터를 테이블 형식에 대응(mapping) 시켜 저장할수 있도록 만든 데이터 관리 기법

  • hashCode() : 메소드를 호출하여 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교하여 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않음

  • 문자열을 HashSet에 저장할 경우, 같은 문자열을 갖는 String객체는 동일한 객체로 간주되고 다른 문자열을 갖는 String객체는 다른 객체로 간주되는데, 그 이유는 String클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열일 경우 hashCode()의 리턴 값을 같게, equals()의 리턴 값은 true가 나오도록 했기 때문임

✏️TreeSet

  • HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않음

    • 이진 탐색 트리(Binary Search Tree) 구조
      • 추가와 삭제에는 시간이 걸리지만, 정렬과 검색에는 높은 성능
      • 이진탐색 트리의 형태로 데이터를 저장하므로 기본적으로 Nature ordering을 지원하며 생성자의 매개변수로 Comparator 객체를 입력하여 정렬 방법을 임의로 지정해 줄 수 있음

Map Interface

  • key와 value를 하나의 쌍으로 묶어 저장하는 컬렉션 클래스를 구현하는데 사용됨

  • 키는 중복될 수 없지만, 값은 중복을 허용

  • 중복된 키와 값을 저장하면 기존 값은 사라지고 마지막 값이 저장

  • key-value 쌍을 다루기 위해 내부적으로 Entry 인터페이스를 정의

  • method

    • Object put (k, v) : 키와 값 쌍을 맵에 저장
    • Object get (key) : 지정된 키의 값 리턴, 없으면 null 리턴
    • Object remove (key) : 지정된 키와 키의 값을 모두 삭제
    • Boolean containsKey (key) :지정된 키를 포함하고 있으면 true 리턴
    • Boolean containsValue (value) : 지정된 값에 일치하는 키가 있으면 true
    • int size () : 맵에 포함된 요소의 개수 리턴
    • boolean isEmpty() : 맵이 비어있으면 true 리턴

✏️HashMap

  • 맵의 성질을 그대로 가지며 Hashing을 사용하기 때문에 많은 양의 데이터를 검색하는데 성능이 높음

  • 해시 함수를 통해 키와 값이 저장되는 위치를 결정하므로 순차적으로 저장X

✏️TreeMap

  • 이진 트리 기반 맵 컬렉션

  • TreeSet은 값만 저장, TreeMap은 기와 값이 저장된 맵, Entry 저장

  • 객체를 저장하면 자동 정렬, 이때 키는 저장과 동시에 자동 오름차순 정렬, 숫자 타입일 경우에는 값으로 문자열 타입일 경우 유니코드로 정렬

  • hashmap 보다 비교적 성능이 떨어짐 (저장할 때 정렬하므로 오래 걸림)

  • 정렬된 상태로 맵을 유지해야 하거나 정렬된 데이터를 조회해야 하는 검색이 필요한 경우 사용

You may also enjoy