[Java] 자료구조

배열

• 고정 크기 이상의 객체를 관리 할 수 없다.

• 배열의 중간에 객체가 삭제되면 응용 프로그램에서 자리를 옮겨야한다.

컬랙션

• 가변 크기로 객체의 개수를 염려할 필요 없다.

• 컬랙션 내의 한 객체가 삭제되면 컬랙션이 자동으로 자리를 옮겨준다.

컬랙션을 구현한 클래스들

• Java.util 패키지는 컬랙션의 개념을 구현한 핵심적인 다양한 클래스를 제공한다.
  • Vector
  • ArrayList
  • HashTable
  • HashMap
  • LinkedList 등

  [참고] 컬랙션을 구현한 모든 클래스들은 Object를 상속받는 객체들만 요소로 받아들인다. 즉, byte, char short, int, long, float, boudle boolean 등 8 종류의 기본 타입은 원칙적으로 사용할 수 없다.

Vector vs ArrayList

공통점

• List 인터페이스를 구현한 클래스

• 객체들을 삽입, 삭제, 검색 할 수 있는 컨테이너 클래스

• 배열의 길이 제한 단점을 극복

• 아이템 맨 마지막이나 중간에 삽입 할 수 있음.

• 객체수가 많아지면 자동으로 크기 조절

• String, Integer, Person 등 다양한 타입의 객체 삽입 가능

• 요소들은 인덱스로 관리(0부터 시작)

차이점

Vector와 ArrayList의 설명이나 주요 메소드 그리고 동작 결과를 보았을때 큰 차이를 느낄 수 없다. ArrayList를 사용하는것은 굉장이 많이 보았으나, Vector를 사용하는 경우는 거의 본적이 없다고 한다. Vector 클래스는 JDK 1.0 부터 사용해 왔고, ArrayList와 동작하는것이 거의 똑같다. 그러나 기존의 레거시를 위해서 남겨놓는것 같다.

1. 동기화(Synchronize)
   1. Vector 는 한번에 하나의 스레드만 접근 가능하다.
   2. ArrayList는 동시에 여러 스레드가 접근 가능하다.
      1. 여러 스레드가 동시에 접근 하는 경우 개발자가 명시적으로 동기화 코드를 추가해야한다.

2. 스레드 안전 (Thread Safe)
   1. 멀티 스레드 프로그래밍에서 여러 스레드가 동시에 접근이 이루어져도 프로그램이 실행에 문제가 없음을 의미
   2. Vector는 동기화 되어있기때문에 한번에 하나의 스레드만 접근 가능하다 즉, Thread Safe하다.
   3. ArrayList는 동기화 되지 않았기때문에 명시적으로 동기화가 필요한다.

3. 성능
   1. ArrayList는 동기화가 되어있지 않기 때문에 Vector보다 빠르다.

4. 크기증가
   1. Vector는 현재 배열의 크기가 100% 증가
   2. ArrayList는 현재 배열의 크기의 50% 증가

결론

멀티 스레드 환경이 아닌경우 ArrayList를 사용하는것이 바람직하다.

Vector가 동기화 한다는것은 복수의 스레드로부터 추가/삭제가 이루어져도 내부의 데이터 처리는 안전하게 한번아 하나의 스레드만 처리되도록 보장한다는 의미이다. 데이터 처리가 안정적으로 이루어지도록 보장하는 것이다.

단일 스레드의 경우 자동으로 동기화를 보장하는 것이 오히려 성능 저하를 일으킬 수 있기 때문에 동기화를 진행하지 않는 ArrrayList가 더 효율적인 성능을 보장한다고 할 수 있다.

LinkedList 클래스

• ArrayList의 단점을 극복하기 위해 고안되었다.

• 내부적으로 연결리스트를 이용하여 요소를 저장한다.

• 배열은 저장된 요소가 순차적으로 저장된다.

• 저장된 요소가 비 순차적으로 분포되며, 요소 사이를 링크로 연결하여 구성한다.

• List 인터페이스를 상속 받기 때문에 ArrayList와 메소드가 거의 같은 메소드를 사용 할 수 있다.

Single Linked List

• 요소의 저장과 삭제작업이 다음 요소를 가르키는 참조만 변경되어 빠르게 처리된다.

• 현재 요소에서 이전요소로 접근하기 매우 어렵다.

Double Linked List

• 이전 요소를 가리키는 참조도 가지고 있다.

• 이전 요소로 접근하기 용이하다.

정리

Vector와 ArrrayList 그리고 LinkedList는 모두 같은 동작을 구현하는 클래스이며 List 인터페이스를 상속 받아서 거의 비슷한 메소드를 사용한다. 사용방법과 동작 결과는 큰 차이는 없지만 내부 동작은 다르다.

Vector와 ArrayList의 차이점은 동기화 차이이다. 단일스레드 작업시 동기화가 필요없다면 ArrayList를 사용하는것이 성능적인 면에서 용이하다.

HashTable 클래스

Java.util 패키지에 포함되어있고, Key, Value 쌍으로 구성되며 특정 값에 매핑 시키는 테이블 기능을 제공한다. 키와 값이 모두 객체로만 사용가능하며 int, char등과 같은 기본 데이터 타입은 불가능하다.

Stack 클래스

Java.util 패키지에 포함되어있고, Stack 자료구조를 사용하고자 할때 쓴다.

Stack st = new Stack();
st.push("0");
st.push("1");
st.push("2");

while (st.empty())
{
	var = num = st.pop()
}

• empty() : stack이 비어있는지 알려줌

• pop() : stack의 맨위에 저장된 객체를 꺼냄.

• peek() : pop()과 달리 stack 에서 객체를 꺼내지 않음.

• push() : stack에 객체 item 을 저장

• search() : 주어진 객체를 찾아서 그 위치를 반환, 못찾으면 -1을 반환

Queue 클래스

Java.util 패키지에 포함되어있고, Queue 자료구조를 사용하고자 할때 쓴다.

• add() : 객체를 추간하다. ( 저장공간이 부족하면 illegalStateException) 발생

• remove() : 객체를 꺼내 반환. 비어있다면 (NosuchElementException) 발생

• element() : 삭제 없이 요소를 읽어옴비어있다면 ( NosuchElementException) 발생

• offer() : Queue에 객체를 저장

• poll() : 객체를 꺼내서 반환 ( 비어있다면 null을 반환 )

• peek() : 삭제없이 요소를 읽어온다. ( Queue가 비어있다면 null을 반환 )

PriorityQueue

Queue 인터페이스 구현체중 하나로, 저장한 순서와 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다. null을 저장하면 NullpointerException일 발생한다. PriorityQueue는 저장공간을 배열을 사용하여, 각 요소를 힙(heap)이라는 자료구조 형태로 저장한다.

객체를 저장하면 각 객체가 크기를 비교 할 수 있는 방법을 제공해야한다. 배열에 저장된 순서와 실제 순솨가 다른 것은 PriorityQueue가 각 요소를 힙이라는 자료구조 형태로 저장한 것이라서 그렇다.

Deque(Double-Ended Queue)

Queue의 변형으로, 한쪽 끝으로만 추가/삭제 할 수 있는 Queue와 달리, Deque는 양쪽 끝에서 추가/삭제가 가능하다. Deque의 조상은 Queue이며, 구현체로는 ArrayDeque와 LinkedList등이 있다.

• addFirst() : 앞쪽에 엘리먼트를 삽입한다. 용량초과시 예외 발생

• offerFirst() : 앞쪽에 엘리먼트를 삽입한다. 삽입된경우 true리턴 그렇지 않다면 false 리턴

• addLast() : 덱의 마지막 쪽에 엘리먼트를 삽입한다.

• add() : addLast()와 동일

• offerLast() : 덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입되면 true가 리턴이 된다.

• removeFirst() : 덱의 앞쪽에서 엘리먼트를 하나 뽑아서 제거한다. 덱이 비어있다면 예외가 발생하낟.

• pollLast() 덱의 마지막 쪽에서 엘리먼트를 하나 뽑는다. 없다면 null을 반환한다.

• remove() : removeFirst()와 동일

• poll() : pollFirst() 와 동일

class TestClass {
    
    public static void main(String[] args) throws InterruptedException {
      
        System.out.println("Stack!!");
        Deque<String> stack = new ArrayDeque<>();
        stack.addFirst("Element1");
        stack.addFirst("Element2");
        stack.addFirst("Element3");
        System.out.println(stack.removeFirst());
        System.out.println(stack.removeFirst());
        System.out.println(stack.removeFirst());
      
        System.out.println("Queue!!");
        Deque<String> queue = new ArrayDeque<>();
        queue.addFirst("Element1");
        queue.addFirst("Element2");
        queue.addFirst("Element3");
        System.out.println(queue.removeLast());
        System.out.println(queue.removeLast());
        System.out.println(queue.removeLast());
    }
}

참고자료

• https://jroomstudio.tistory.com/4

Uploaded by N2T