[Java] 컬렉션(ArrayList, LinkedList, Queue) # 6

  목  차

• 배열과 ArrayList
• LinkedList
• Queue
• 그 외 컬렉션들

 

 

---

 

  ArrayList

 

  Javascript의 배열은 동적 배열이다. 그래서 Java 에서는 Arrays 를 통해서 사용해야 하는 배열 메서드들을 직접적으로 사용할 수 있다. 그러한 Javascript 배열의 Java 버전 이라고 생각하면 쉽다. 

 

 

  동작원리

내부구조: ArrayList 는 내부적으로 배열을 사용하여 데이터를 저장한다. 그리고 필요에 따라서 배열의 길이가 조절된다.

요소추가: 새 요소를 추가할 때 배열이 가득 차 있으면, 더 큰 배열을 생성하고 기존 배열을 복사한다. 

요소제거: 요소를 제거하면 그 뒤에 있는 요소들이 한 칸씩 이동된다. 배열의 연속성을 위해서 이다.

 

 

동적인 배열이 필요할 경우, 그리고 다양한 배열 메서드를 활용하기 위해서 ArrayList 를 많이 사용하기도 하고 컬렉션 중에서 가장 만만한 컬렉션이기도 하다.

 

 

 

---

 

  LinkedList

 

  요소들이 포인터를 통해 서로 연결된 리스트 이다.

 

Java LinkedList 에 대한 설명

 

 

  동작원리

내부구조: LinkedList, 각 노드는 자신의 데이터, 이전 노드의 참조(노드의 주소), 다음 노드의 참조(노드의 주소) 를 가진다.

영어로 되어 있지만 위 그림이 많은 것을 설명해 주고있으니 살펴보면 많은 도움이 될 것이다.

요소추가: 해당 요소를 특정 위치에 추가하고, 그 이전 노드와 다음 노드의 참조값을 바꾸어 주면 된다. ArrayList 와는 다르게 굉장히 빠르게 진행이 된다.

요소제거: 이전 노드와 다음 노드의 참조값을 바꾸어 주면된다. 이 작업 역시 굉장히 빠르다.

요소접근: ArrayList 는 배열이기에 인덱스로 접근이 가능했지만 LinkedList 는 처음부터 시작해서 원하는 요소까지 탐색해야 한다. 이로 인해서 시간이 걸린다.

 

 

알고리즘 문제를 풀다 보면 BFS 를 구현하기 위해서 Queue 인터페이스를 사용해야 할 경우가 많은데, 이 Queue 를 LinkedList 를 통해서 구현하기에 알아둘 필요가 있다.

 

 

 

---

 

  Queue

 

Queue 는 간단히 말해서 FIFO(선입선출) 방식으로 데이터를 처리하는 자료구조 이다.

 

Queue 의 구현은 다음과 같다.

Queue<타입> queue = new LinkedList<>();

 

 

보다싶히 LinkedList를 생성해서 사용하는 것을 볼 수 있다.

이제 우리가 알고있는 Queue 처럼 사용하면 된다. 

 

 

 

---

 

  그 외 컬렉션들

 

그 외에 Set 과 Map 이 존재한다. 여기서는 간단하게만 설명하고자 한다.

 

 

Set: 중복요소를 저장할 수 없고, 순서를 보장하지 않는다.(단, LinkedHastSet 의 구현체는 순서 유지를 할 수 있다.)

 

Map: Javascript 의 객체라고 할 수 있다. key-value 이 한 쌍을 이루는 데이터를 저장하는 구조이다. 각 key는 유일해야 하고, value 는 중복이 가능하다.