[Java] 자료구조

리스트 -  ArrayList와 LinkedList 일반적으로 사용

리스트 크기가 작아지면 메모리 용량이 작아지고 크기 지정에 한계가 없다.

배열과의 차이

@Test
public void arrayDefinitions() throws Exception {
    final int[] integers = new int[3];
    final boolean[] bools = {false, true, false, true};
    final String[] strings = new String[] {"one", "two"};

    final Random r = new Random();
    final String[] randomArrayLength = new String[r.nextInt(100)];

    assertEquals(true, bools[1]);
}

배열을 정의하기 위해서는 크기를 지정해야한다.

위 코드는 int 배열을 명시적으로 지정하였고 boolean은 암시적으로 지정하였다.

배열의 원소에는 인덱스 값을 사용하여 직접 접근할 수 있다. 이를 랜덤 접근이라고 한다.

배열이 메모리의 특정 위치에 직접 접근할 수 있으므로 빠르게 접근할 수 있다.

assertEquals(true, bools[1]);

bools의 두번째원소는 true인것을 확인할 수 있다.

배열 전체를 사용 중일 때 원소를 추가하려면 배열 크기를 늘려야 하는데 System클래스 객체의 arrayCopy라는 메소드를 사용해 복사 할 수 있게 된다.

@Test
public void arrayCopy() {
    int[] integers = {1, 2, 3, 4, 5};

    int[] newIntegers = new int[integers.length + 1];
    System.arraycopy(integers, 0, newIntegers, 0, integers.length);
    integers = newIntegers;
    integers[5] = 6;

    assertEquals(6, integers[5]);
}

ArrayList - 리스트의 데이터로 배열을 사용하는 List 인터페이스의 구현

크기를 지정하지 않으면 default값 10으로 생성된다.

배열의 시작 위치나 중간 위치에 새로운 원소를 추가해야한다면 그 뒤에있는 모든 원소는 공간을 만들기 위해 이동해야 한다. 배열의 크기가 클수록 연산량은 점점 늘어날 것이다. 

만약 원소의 개수가 계속 변경이된다면 LinkedList 클래스로 배열을 생성하는 것이 더 적합할 수 있다.

LinkedList - 배열을 이용하지 않고 리스트 안에서 다음 원소를 가르키는 내부 객체를 이용

ArrayList클래스에서 배열 재할당 과정으로 인해 발생하는 손실을 막아준다.

public void linkedDefinitions() {
    LinkedList<Integer> linked = new LinkedList<Integer>();
    //데이터 추가
    linked.add(1);
    linked.add(2);
    linked.add(3);
    //데이터 삭제
    linked.remove(0);
    //데이터 갯수
    linked.size();
    System.out.print(linked);
}

큐(Quere)- First in First out 자료구조를 구현한 자바 인터페이스

3가지 메소드

add => 새 원소를 추가

remove => 오래된 원소를 제거

peek => 가장 오래된 원소를 반환

@Test
public void queueInsertion() {
    final Queue<String> queue = new LinkedList<String>();
    queue.add("first");
    queue.add("second");
    queue.add("third");

    assertEquals("first", queue.remove());
    assertEquals("second", queue.remove());
    assertEquals("third", queue.peek());
    assertEquals("third", queue.remove());
}

트리(Tree) - 부모-자식관계로 이루어지며 계층적 구조, 서로 다른 원소를 많이 나열할 수 있는 자료구조

기본 이진트리를 사용하며 각 원소는 최대 두개의 자식을 갖는다. 정확히 왼쪽과 오른쪽으로 구분한다.

Comparable 인터페이스 타입의 원소를 저장 할 수 있고 Comparator 인터페이스 타입을 이용할 수도 있다.

public class SimpleTree <E extends Comparable> {

    //노드값, 노드의 왼쪽, 노드의 오른쪽 정의
    private E value;
    private SimpleTree<E> left;
    private SimpleTree<E> right;
  public E getValue() {
      return value;
  }

  public SimpleTree<E> getLeft() {
      return left;
  }

  public SimpleTree<E> getRight() {
      return right;
  }
    /**
     *
     * @param toFind 값
     * @param left 왼쪽 노드
     * @param right 오른쪽 노드
     */
    public SimpleTree(E toFind, SimpleTree<E> left, SimpleTree<E> right) {
        this.value = toFind;
        this.left = left;
        this.right = right;
    }

    /**
     * 이진 검색 트리에서 값 찾기
     * @param toFind 찾고자 하는 노드
     * @return
     */
    public boolean search(final E toFind) {

        // 찾는 값이 같다
        if (toFind.equals(value)) {
            return true;
        }

        // 찾는 값이 현재 노드보다 작고 왼쪽 자식 노드가 null이 아니면 왼쪽 검색
        if (toFind.compareTo(value) < 0 && left != null) {
            return left.search(toFind);
        }

        //오른쪽노드가 null이 아니면 오른쪽 노드를 검색해 값을 반환한다.
        return right != null && right.search(toFind);
    }

    public void insert(final E toInsert) {

        // 음수이면 왼쪽에 삽입
        if (toInsert.compareTo(value) < 0) {
            if (left == null) {
                // 노드가 비어있을때
                left = new SimpleTree<E>(toInsert, null, null);
            } else {
                // 노드가 있을때
                left.insert(toInsert);
            }
        } else {
            // 0 이거나 양수이면 오른쪽에 삽입
            if (right == null) {
                // 노드가 비어있을때
                right = new SimpleTree<E>(toInsert, null, null);
            } else {
                // 노드가 있을때
                right.insert(toInsert);
            }
        }
    }
}

테스트 코드 작성

@Test
public void createTree() {
    final SimpleTree<Integer> root = new SimpleTree<Integer>(3, null, null);
    root.insert(5);
    root.insert(8);
    root.insert(10);

    assertTrue(root.search(3));
    assertEquals(Integer.valueOf(10), root.getRight().getRight().getRight().getValue());
}

맵 - 해시라고 하며, 키-값 형태의 저장소 키를 통해 원하는 값을 찾을 수 있음

@Test
public void overwriteKey() {
    final Map<String, String> preferences = new HashMap<String, String>();
    preferences.put("like", "jacuzzi");
    preferences.put("dislike", "steam room");

    assertEquals("jacuzzi", preferences.get("like"));

    //키를 다시 삽입하면 원본 키에 있던 값은 덮어씌운다
    preferences.put("like", "sauna");
    
    assertEquals("sauna", preferences.get("like"));
}

집합 - 중복을 허용하지 않는 순서 없는 객체들의 모음

@Test
public void setExample() {
    final Set<String> set = new HashSet<>();
    set.add("hello");
    set.add("welcome");
    set.add("goodbye");
    set.add("bye");
    set.add("hello");
    
    //중복을 허용하지 않기떄문에 사이즈는 4이다.
    assertEquals(4, set.size());
}