JAVA 자료구조 복습 1

게시 2024/03/19

By Hyechan Bang 5 분읽는 시간

서론

이 포스트는 코딩 테스트를 위해 수강했던 알고리즘 강의를 복습하며 정리한 내용입니다.

자료구조

대량의 데이터를 효율적으로 관리하기 위한 구조이다.

데이터의 특성에 맞춰서 어떤 구조를 사용하는지에 따라 코드의 효율이 달라진다.

대표적인 자료구조들로는 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등이 있다.

배열(Array)

여러개의 데이터를 나열하여 순서대로 구성한 데이터 구조이다.

같은 종류의 데이터를 효율적이고 순차적으로 저장할 수 있다.

배열의 크기를 미리 정하고 생성하기 때문에, 빠르게 특정 위치에 접근이 가능하지만 정해진 개수를 벗어나는 데이터 추가 / 삭제는 어렵다.

배열 생성

빈 배열 생성

  
  // 5칸의 Integer 배열을 생성한다.
  Integer[] myArray = new Integer[5];
  myArray[0] = 10;

배열 생성 시 값 대입

  
  Integer[] myArray1 = {1, 2, 3, 4};
  Integer myArray2[] = {4, 3, 2, 1};

  System.out.println(myArray1[2]);

다차원 배열 생성

  
  // 3차원 배열
  Integer[][][] myArray3 = {
      {
          {1, 2, 3},
          {4, 5, 6}
      },
      {
          {7, 8, 9},
          {10, 11, 12}
      }
  }

Arrays 클래스를 활용하면 다양한 기능들을 사용할 수 있다.

  
  import java.util.Arrays;

  Integer[] myArray1 = {1, 2, 3, 4};

  System.out.println(Arrays.toString(myArray1));

문자열 배열 활용해보기

  
  String[] stringArray = {"Test", "Hello World", "Nice"};

  Integer count = 0; 

  // T 를 가진 문자열 카운팅
  for (Integer i = 0; i < stringArray.length; i++){
      if(stringArray[i].indexOf("T") >= 0){
          count++;
      }
  }

배열(ArrayList)

길이가 가변적인 배열이다.

생성

List 인터페이스 / ArrayList 클래스 둘다 사용 가능

  
  List<Integer> myList1 = new ArrayList<Integer>();
  myList1 = new LinkedList<Integer>(); // 요런것도 가능
  ArrayList<Integer> myList2 = new ArrayList<Integer>();
  ArrayList<Integer> myList3 = new ArrayList<>(); // JDK 1.7 부터

메서드

CRUD 관련 기능들

  
  import java.util.ArrayList;

  ArrayList<Integer> myList1 = new ArrayList<Integer>(); // Integer 데이터 전용

  myList1.add(1);
  myList1.add(2);

  System.out.println(myList1.get(0)); // 1

  myList1.set(0, 5); // 0번 인덱스 5로 세팅
  System.out.println(myList1.get(0)); // 5

  myList1.remove(0); // 0번 인덱스 삭제
  System.out.println(myList1.get(0)); // 2

  System.out.println(myList1.size()); // 길이 1

큐(Queue)

입구와 출구가 하나뿐인 자료구조

FIFO(First In First Out), LILO(Last In Last Out) 방식이다. 먼저 들어온 값부터 나간다. 멀티 태스킹을 위한 프로세스 스케쥴링 방식 구현에 많이 사용된다.(자세한 내용은 운영체제를 공부하자)

출처 : https://www.geeksforgeeks.org/queue-data-structure/

데이터의 입력은 enqueue, 출력은 dequeue 라고 부른다.

enqueue 메서드 : add, offer
dequeue 메서드 : poll, remove

생성

  
import java.util.LinkedList;
import java.util.Queue;

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

메서드

  
myQueue.add(1);
myQueue.offer(2);

System.out.println(myQueue); // [1, 2]

myQueue.poll();
System.out.println(myQueue); // [2]

myQueue.remove();
System.out.println(myQueue); // []

연습

ArrayList 클래스를 활용해 enqueue, dequeue 를 구현한 queue 클래스를 만들어보자.

dequeue 시 데이터가 없으면 null 을 return 해주자.

Generic 타입을 활용해보기

  
public class MyQueue<T> {
    private ArrayList<T> queue = new ArrayList<T>();

    public void enqueue(T item){
        queue.add(item);
    }

    public T dequeue(){
        if(queue.isEmpty()){
            return null;
        }
        return queue.remove(0);
    }
}

스택(Stack)

데이터와 입력과 출력이 한쪽에서만 가능한 구조.

FILO(First In Last Out), LIFO(Last In First Out) 구조이다.

컴퓨터 내부의 프로세스 구조의함수 동작 방식이다.

출처 : https://www.geeksforgeeks.org/stack-data-structure/

데이터의 입력과 출력에 push, pop 메서드를 사용한다.

구조가 단순해 저장/읽기가 빠르지만 스택의 크기를 미리 정해야 한다.(빠른 성능을 위해 보통 배열 구조를 활용해 구현하기 때문)

생성, 메서드

  
import java.util.Stack;

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

myStack.push(1);
myStack.push(2);
myStack.push(3);

System.out.println(myStack.pop()); // 3
System.out.println(myStack.pop()); // 2
System.out.println(myStack.pop()); // 1

연습

ArrayList 로 Stack 기능 구현해보기

  
public class MyStack<T> {
    private ArrayList<T> stack = new ArrayList<T>();

    public void push(T item){
        stack.add(item);
    }

    public T pop(){
        if(stack.isEmpty) return null;
        return stack.remove(stack.size()-1);
    }
}

JAVA, 자료구조

java 자료구조