큐, 스택, Arraylist, Linkedlist란

1. 스택이란

스택 구조

 LIFO(Last-in, First-out)의 자료구조. 삽입, 삭제가 항상 위치가 정해져있기 때문에 O(1)이다. 다만 특정 데이터를 찾기 위해서는 순차적으로 검색해나가야하기 때문에 O(n)이다.

 

2. 큐란

큐 구조

FIFO(First-in, First-out)의 자료구조. 스택과 마찬가지로 삽입, 삭제의 위치가 항상 정해져 있기 떄문에 O(1)이지만 검색은 O(n)이다.

 

3. Arraylist란?

배열과 거의 유사하다. 하지만 배열과는 다르게 선언할때 크기를 확정 짓지 않아도 된다는 큰 장점이 있다. Arraylist에 값을 하나하나 추가해나갈때마다 메모리가 부족하다면 알아서 확장시키기 때문이다. 배열과 똑같이 index를 통해서 특정 요소 값을 찾을 수 있으므로 검색 속도는 O(1)이다. 하지만  특정 위치 값을 추가하거나 삭제할때 그 근처에 있는 요소값들을 다 복사해서 땡기거나 뒤로 미뤄주는 작업들을 해야하기 때문에 O(n)이 된다.

 

즉, 배열의 크기를 정하지 않고 검색, 변경을 빠르게 하고 싶을떄는 Arraylist를 사용하자. 요소 삭제나 추가해야한다면 Arraylist를 피하자.

 

4. Linkedlist란

 

linkedlist구조

이런 사슬형태의 자료구조를 가진다. 삽입과 삭제에서 굉장히 큰 장점을 가진다. 그냥 노드의 포인터들만 살짝 바꿔주기만 하면 되기 때문에 삭제와 삽입이 굉장히 빠르다 O(1). 다만 원하는 특정 위치를 찾아가는 과정에서 O(n)일 수 있다.(index를 통해 한번에 찾아갈 수 없으므로 순차적으로 찾아가야한다). 다만 제일 처음이나 제일 끝인 경우에는 바로 찾아갈 수 있기 때문에(head와 tail 부분) O(1)이다. 검색은 마찬가지로 index가 존재하지 않기 때문에 O(n)이다.

 

즉, 처음이나 끝에 삽입과 삭제를 자주 해야한다면 linkedlist를 사용하자. 검색이나 변경을 위해 순차탐색이 필요하다면 linkedlist를 피하자.

 

5. 참고한 페이지들

https://girawhale.tistory.com/8

ArrayList와 LinkedList의 차이, 선택하기

https://coding-factory.tistory.com/552

[Java] 자바 LinkedList 사용법 & 예제 총정리

https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

스택, 큐 (Stack, Queue)