[개념] Data Structure/Java Code 기반

Ik·2023년 9월 10일
algorithm
0

Algorithm 

목록 보기
2/18

Java 기본 자료 구조

Array

  • 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

  • 정해진 크기 있으며 초기 크기에서 요소 추가 제거 작업으로 길이 변동 있는 경우 다른 요소들의 이동 필요

    • 추가, 삭제 등 길이 변화에 있어 array 자체 메서드 없음

  • 데이터 연속적으로 순서가 존재하기 때문에 검색(인덱싱) 빠름




ArrayList

  • Array처럼 순서 존재, 하지만 크기는 유연하게 변경 가능
    • LinekdList와 마찬가지로 추가, 삭제 메서드 존재
    • 순서가 정해져 있기 때문에 검색에 용이

내부 로직

  • 배열 아닌척 하는 배열이라 생각하면 이해하기 쉽다
  • 데이터가 연속적으로 저장되어 있기 때문에 Array의 크기 변할 때 모든 데이터의 index 수정 작업 진행

추가

  1. 새로운 크기(추가된 크기) 사이즈의 객체가 할당
  2. 이 전에 쓰던 배열을 새로운 객체의 복사
  3. 특정 index에 요소 추가

삭제

  1. 삭제하는 인덱스 다음 인덱스들을 현재 객체에서 삭제하는 인덱스부터 하나씩 복사하며 값을 옮김
  2. 기존의 객체의 마지막 인덱스를 null 처리
  • List의 크기가 유동적인 경우 시간 복잡도 증가하기에 잘 사용하지 않음




LinkedList

데이터의 추가, 삭제에 많은 시간 할애하는 배열의 단점을 보완하고자 개발

  • 데이터 메모리상에 연속적으로 저장 X

  • 모든 데이터가 독립적으로 데이터 + 포인터 형태로 데이터와 다음 데이터를 가리키는 포인터 형태로 이루어짐

  • 데이터가 연속적으로 저장되어 있지 않기 때문에 리스트의 삽입, 삭제가 자주 이루어지는 경우 용이

    비순차적인 데이터 구조에서 데이터의 참조만 링크가 수정되기 때문에 삽입, 삭제 용이

  • 단 검색에 있어서는 느리다

    비연속적으로 데이터가 저장되어 있기 때문에 링크를 타면서 해당 값을 직접 찾아야된다

  • queue 인터페이스의 구현체 중에 하나




Set

중복 데이터 저장 안하지만 객체 타입 유의해야된다

  • ex) Integer 객체와 String 객체의 1은 각 각 저장 가능

HashSet

  • 검색속도 굉장히 빠름

    • 해싱을 통해 만든 해시 코드를 내부적으로 배열의 인덱스로 활용하기 때문, 별도의 정렬을 거치지 않고도 찾고자 하는 데이터의 인덱스를 해싱을 통해 바로 추출 가능

  • 순서 상관 X, 중복 저장 X

  • 순서 유지해야된다면 Linked HashSet 클래스 사용하면된다

import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args){

        LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();

        set.add(5);
        set.add(7);
        set.add(3);
        set.add(1);

        System.out.println(set);
    }
}

출력

[5, 7, 3, 1]

LinkedHashSet

  • HashSet과 대부분 동일하지만 순서 유지하는 경우의 자료구조
    • 삽입된 순서대로 저장

treeset

이진 탐색 트리(binary search tree)라는 자료구조 형태
정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조

  • 데이터가 정렬된 상태로 이진 검색 트리의 형태로 요소 저장
    • 중복되지 않은 데이터가 순차적(=정렬)으로 저장된다고 생각하면 된다
  • 데이터의 추가, 제거 기본 동작 매우 빠름
    • 순서에 상관없이 저장, 중복된 값 저장 X
  • 순차적으로 저장되어 있는 구조가 아니기에 저장, 삭제의 경우 Linked List보다 더 걸리지만 배열, Linked List에 비해 검색과 정렬 기능이 더 뛰어나다
import java.util.TreeSet;

public class Main {
    public static void main(String[] args){

        TreeSet<Integer> set = new TreeSet<Integer>();

        set.add(5);
        set.add(7);
        set.add(3);
        set.add(1);
        set.add(7);
        set.add(9);
        set.add(5);

        System.out.println(set);
    }
}

출력

[1, 3, 5, 7, 9]




map

hashmap

  • TreeMap과는 다르게 key 순서 랜덤하게 저장

  • hashtable(구 버전)도 hashmap(신 버전)과 똑같음

  • 해싱 알고리즘으로 검색 속도 매우 빠름

    • Key - Value 형태 => 검색에서 O(1)의 시간 복잡도 발생
      • 인덱스는 Key 값의 해시 코드(해싱 작업을 거친 결과)
    • Array보다 검색 빠르다

  • 중복 키 불가

import java.util.HashMap;

public class Main {
    public static void main(String[] args){

        HashMap<String,Integer> map = new HashMap<String,Integer>();

        map.put("a", 1);
        map.put("c", 3);
        map.put("b", 2);
        map.put("z", 2);
        map.put("h", 2);
        map.put("l", 2);

        for (String s : map.keySet()) {
           System.out.println(s);
        }
    }
}

출력

a
b
c
h
z
l

treemap

  • HashMap과 다르게 key를 기준으로 정렬되어 저장

  • 키와 값을 한 쌍으로 데이터를 이진 검색 트리 형태로 저장

    • 정렬 후 저장하기에 O(logn) 시간 복잡도 가짐

  • 중복 키 저장 불가

import java.util.TreeMap;

public class Main {
    public static void main(String[] args){

        TreeMap<String,Integer> map = new TreeMap<String,Integer>();

        map.put("a", 1);
        map.put("c", 3);
        map.put("b", 2);
        map.put("z", 2);
        map.put("h", 2);
        map.put("l", 2);

        for (String s : map.keySet()) {
           System.out.println(s);
        }
    }
}

출력

a
b
c
h
l
z











기본 자료 구조 응용한 자료 구조

Stack

  • 후입선출, LIFO(Last In First Out)
import java.util.Stack;

public class Main {
    public static void main(String[] args){

        Stack<Integer> stack = new Stack<Integer>();

        stack.add(1);
        stack.add(4);
        stack.add(65);
        stack.add(9);
        System.out.println(stack);
        stack.pop();
        System.out.println(stack);

    }
}

출력

[1, 4, 65, 9]

[1, 4, 65]




QUEUE

특징

  • 선입선출, FIFO(First In Frist Out)
import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args){

        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(4);
        queue.add(65);
        queue.add(9);
        System.out.println(queue);
        queue.poll();
        System.out.println(queue);

    }
}

출력

[1, 4, 65, 9]

[4, 65, 9]




deque

  • Stack, Queue 합친 기능

    • 자료 구조의 맨 앞, 맨 뒤에 데이터 추가, 삭제 작업 모두 가능

  • Queue보다 빠른 소요시간

    • queue의 경우 데이터의 추가, 삭제 시에 인덱스 포인터가 모두 수정된다

      del, pop -> O(N), 모든 index 수정

    • deque의 경우 인덱스 수정하지 않음

      del, pop -> O(1), 맨 앞 or 맨 뒤 원소만 제거

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args){

        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Integer> linkedList = new LinkedList<>();

        deque.add(1);
        System.out.println(deque);
        deque.addFirst(4);
        System.out.println(deque);
        deque.add(4);
        System.out.println(deque);
        deque.pop();
        System.out.println(deque);
        deque.pollLast();
        System.out.println(deque);

        System.out.println("======================");

        linkedList.add(1);
        System.out.println(linkedList);
        linkedList.addFirst(4);
        System.out.println(linkedList);
        linkedList.add(4);
        System.out.println(linkedList);
        linkedList.pop();
        System.out.println(linkedList);
        linkedList.pollLast();
        System.out.println(linkedList);

    }
}

pop(), poll() 모두 가장 선두 데이터 리턴 후 삭제

출력

두 경우 모두

[1]

[4, 1]

[4, 1, 4]

[1, 4]

[4]




Priority Queue

  • 우선순위 큐

  • 일반적인 큐의 경우 가장 빨리 들어온 것이 기준이지만 Priority Queue의 경우 해당 기준을 선정할 수 있다

    • ex) 가장 무거운 경우의 순으로 출력 등











ref

profile
Ik
이전 포스트

[개념] Algorithm, Data Structure

다음 포스트

[개념] Tree, 트리

0개의 댓글