[보완중] [JAVA 자료구조] Array(배열) / List / Map / Set 개념, 특징, 예제

보완중..Map, Set

 

배열이 리스트고 리스트가 배열인냥 생각한 적이 있었다...

헷갈리게 느껴지는 이 친구들을 정확히 개념만 정리해보았다.

 

▶Stack 나무쌓기 / Queue 줄서기 ( cf) Heap 옷더미 )

Stack은 보통 Array와 List로 구현한다.

Queue는 보통 List 중에서도 LinkedList로 구현한다.

 

cf) Set과 Map은 Stack이나 Queue와는 다른 종류의 컬렉션이다.

Stack과 Queue는 선형 자료구조로서,

아이템들의 추가와 제거에 대한 특정 규칙(예:후입선출 또는 선입선출)을 따르는 구조이다.

반면, Set과 Map은 아이템들의 유일성 또는 키-값 관계를 강조하는 구조이다.

 

==>

Stack :후입선출
- Array: 배열을 사용하여 스택을 구현하는 경우, 크기가 고정되어 있기 때문에 스택의 크기를 미리 알고 있어야 합니다. 이로 인해 동적으로 크기를 변경할 수 없어 일부 상황에서는 제한적일 수 있습니다.
- List (특히 ArrayList): 리스트를 사용하여 스택을 구현하면 동적으로 크기를 조절할 수 있습니다. ArrayList와 같은 동적 배열 기반의 리스트는 내부 배열의 크기를 자동으로 조절해 주기 때문에 이를 이용한 스택 구현은 더 유연합니다.

Queue : 선입선출
- LinkedList: LinkedList는 더블 엔디드 큐(Deque)로도 사용될 수 있기 때문에, 큐의 앞과 뒤에서 모두 삽입과 삭제 연산을 효율적으로 수행할 수 있습니다. 따라서 LinkedList는 자바에서 큐를 구현할 때 널리 사용되는 방법 중 하나입니다.
또한, Java의 java.util 패키지에서는 Stack 클래스와 Queue 인터페이스, 그리고 이를 구현하는 여러 클래스 (LinkedList, ArrayDeque 등)를 제공하고 있습니다. 따라서 직접 배열이나 리스트를 사용하여 스택이나 큐를 구현할 필요가 없는 경우도 많습니다.

 

▶자료구조 안에 Stack과 Queue도 포함되는 개념인데 

왜 Java Collection에는 Stack과 Queue가 없고

Array와 List를 통해서 구현하는 걸까? 

(▶Java Collection이라는 것 자체가 자료구조들을 미리 구현해놓은 클래스인데..! 왜 Stack과 Queue는 없지?

(자바가 엄선해놓은 세트이기 때문에 자바 컬렉션 프레임워크라고도 부름))

==>

실제로 자바의 컬렉션 프레임워크에는 Queue 인터페이스가 포함되어 있습니다. 그래서 Queue를 통해 여러 종류의 큐를 구현할 수 있습니다. (PriorityQueue, LinkedList 등). 그리고 Deque는 양방향 큐로, 스택과 큐 두 가지 역할을 모두 할 수 있습니다.

컬렉션 프레임워크 내에는 스택과 큐의 개념이 포함되어 있으며, 이를 위한 효율적인 구현체도 제공하고 있습니다. Stack 클래스가 여전히 존재하는 것은 주로 역사적인 이유와 이전 코드와의 호환성 때문입니다.

 

 

▶Stack과 Queue를 Array나 List로 구현하는 이유는 대체 무엇일까?

→ 유연성과 편의성 때문이다.

자바에서는 Stack과 Queue를 직접적으로 구현하는 클래스인 Stack과 Queue를 제공하지만,

이들 클래스는 일부 기능이나 확장성에 제약이 있을 수 있다.

유연성과 다중 구현 지원, 기능 확장 및 성능, 코드 재사용 및 호환성, 표준화를 할 수 있기에 Array나 List로 구현한다.

 

 

▶각각의 개념 & 특징 & 예제

 

1) Array(배열) : 동일한 타입의 변수들을 연속된 메모리 공간에 저장하는 데이터 구조.

배열의 각 요소는 인덱스에 의해 참조된다. 배열은 고정된 크기를 가지며, 한번 크기가 정해지면 변경할 수 없다.

int[] numbers = new int[5];  // 크기가 5인 정수 배열 선언
numbers[0] = 1;  // 첫 번째 요소에 1 할당
numbers[1] = 2;  // 두 번째 요소에 2 할당
numbers[2] = 3;  // ...
numbers[3] = 4;
numbers[4] = 5;

//이 때 numbers배열은 [1, 2, 3, 4, 5]로 초기화된다.

//또한 배열은 한번에 선언하면서 값을 할당할 수도 있다.
int[] numbers = {1, 2, 3, 4, 5};

//이러한 특성으로 배열은 빠른 임의접근을 제공한다.
//즉, 인덱스를 통해 배열의 특정 요소에 빠르게 접근할 수 있다.

 

2) List : 순서가 있는 요소의 집합으로, 중복된 요소를 포함할 수 있다.

자바의 List는 java.util패키지의 List인터페이스를 기반으로 하는데,

이는 여러 구현체들을 가지고 있다.

가장 일반적인 구현체는 ArrayList와 LinkedLIst이다.

 

특징

1. 요소의 인덱스에 따라 순서가 유지된다.

2. 중복된 요소를 포함할 수 있다.

3. 동적으로 크기가 조절된다.

 

import java.util.ArrayList;
import java.util.List;

//ArrayList 사용 예시
public class ListExample {
    public static void main(String[] args) {
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add("Date");
        fruits.add("Apple");  // 중복 요소 추가

        //인덱스를 사용해 특정 위치의 요소에 접근
        String firstFruit = fruits.get(0); //"Apple"
        //크기 확인
        int size = fruits.size();

        //요소가 포함되어 있는지 확인
        boolean containsApple = fruits.contains("Apple"); //true
    }
}

 

 

3) Map : key와 value 쌍으로 이루어진 컬렉션. 키는 중복될 수 없으나, 값은 중복될 수 있다.

HashMap

 

 

 

4) Set : 순서를 유지하지 않으며 중복을 허용하지 않는 컬렉션

HashSet