README.md

 

❒ Description

---

자료구조가 무엇이고, 어떤 것들이 있는지 큰 틀을 알아보자.

 

 

 

❒ 자료구조란?

---

 

 

 

 

❒ 선형자료 구조

데이터 구조가 선형이라는 것은 데이터 구조를 구성하는 요소들이 서로 인접해
순차적인 방식으로 정렬되어 있음을 뜻한다.

---

1. 배열 

 

---

2. 연결 리스트

연결 리스트는 데이터 엘리먼트의 선형 집합이지만 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다.

이는 순서대로 저장되는 배열과의 가장 큰 차이점으로, 대신 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며,

연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다. 

탐색	O(n)
추가, 삭제, 추출	O(1)

 

자바의 연결 리스트는 이중 연결 리스트이기 때문에 삽입,추출이 양방향으로 가능하다. 

 

---

3. 스택

스택은 가장 나중에 삽입된 엘리먼트가 가장 먼저 처리되는 후입 선출(LIFO)로 처리되는 추상자료형이다.

추상자료형이란?
자료형의 연산을 정의한 것으로, 실제 구현 방법은 명시하지 않는다.

 

스택을 연결리스트로 구현해보자.

public class MyNode {
    private int item;
    private MyNode next;
}

public class MyStack {
   private MyNode last;
    
    public void push(int item) {
    	this.last = new MyNode(item, this.last);
    }
    
    public int pop() {
    	int item = this.last.item;
        this.last = this.last.next;
        return item;
    }
}

 

자바에서 Stack을 선언할 때 다음과 같이한다.

Deque<Integer> stack = new ArrayDeque<>();

 

Stack 클래스를 사용하지 않는 이유는, Stack 클래스는 CPU 코어가 하나밖에 없던 시절에 나온 자료형으로,

모든 작업에 Lock이 수행되는 Vector라는 자료형을 기반으로 하기 때문이다. 그래서 위와 같이 Deque로 구현하며,

Deque는  Stack의 모든 연산을 포함하고 있다. 실제 구현체로는 LinkedList 또는 ArrayDeque로 가능하다.

추가적으로 Thread-Safe가 필요한 경우에는 LinkedBlockingDeque 또는 ConcurrentLinkedDeque를 사용하면 된다.

 

결과적으로 Stack은 코딩테스트에서도 쓰면 안되지만, 실무에서는 더더욱 쓰면 안된다.

 

---

4. 큐

큐는 가장 먼저 삽입된 엘리먼트가 가장 먼저 처리되는 FIFO 순으로 처리되는 추상자료형이다.

큐는 상대적으로 스택에 비해 쓰임새가 적다. 큐의 경우에는 Deque, Prioriy Queue같은 큐의 변형들이

여러 분야에서 매우 유용하게 쓰인다. 이 외에도 너비 우선 탐색(BFS)이나 캐시 등을 구현할 때도 널리 사용된다.

 

---

 

4. 우선 순위 큐

 

 

 

❒ 비형자료 구조

---

1.