[JAVA] 자료구조 - ArrayList, LinkedList, Stack, Queue

자료구조(Data Structure)란?

• 하나의 데이터가 아닌 여러 데이터를 담을 때 사용하는 것이 자료구조.
• 배열도 여러 데이터를 담을 수 있으므로 자료구조라고 말할 수 있음.
• 자바의 자료구조는 크게 'List', 'Set', 'Queue', 'Map' 4가지로 분류할 수 있음.
• 'Set', 'List', 'Queue'는 Collection 인터페이스를 구현하고 있고,
• 'Map'은 별도의 인터페이스로 선언되어 있음.

 

---

 

Collection

• Collection인터페이스를 구현한 자료구조는 Set(클래스), List(클래스), Queue(인터페이스) .
• Collection인터페이스는 java.util패키지에 선언되어 있고, 여러 개의 객체를 하나의 객체에 담아 처리할 때 공통으로 사용되는 여러 메서드들을 선언해 놓음.
• Collection을 살펴보면, iterator()라는 메서드를 정의해놓은 Iterable이라는 인터페이스를 확장.
• Collection 인터페이스를 구현한 자료구조는  iterator()가 반환하는 Iterator 인터페이스를 사용가능.

*Iterator 인터페이스에 정의 된 메서드

  hasNext() : 추가 element가 있는지 확인하는 메서드

  next() : 다음 element를 리턴하는 메서드

  remove() : element를 삭제하는 메서드

 

 

 

---

 

List 

• List인터페이스를 구현한 자료구조는 ArrayList(클래스), LinkedList(클래스), Vector(클래스), Queue(인터페이스).
• 순서가 있는 데이터의 집합. 데이터의 중복을 허용함.

 

---

 

ArrayList

• ArrayList는 List인터페이스를 구현하기 때문에, 순서가 유지되고 중복을 허용함.
• ArrayList는 기존의 Vector를 개선한 것으로 거의 동일하지만, Vector는 동기화를 지원하고, ArryList는 동기화를 지원하지 않음.
• ArrayList는 LinkedList와 비교하였을 때 읽기가 빠르고 맨 뒤의 데이터를 추가하거나 삭제할 경우는 빠름.(맨처음 데이터나 중간데이터를 추가하거나 삭제할 경우 뒤의 데이터들을 이동시켜야하기 때문.)

*ArrayList가 구현한 6개의 인터페이스

Serializable : 원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정.

Cloneable : Object클래스의 clone()메서드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미함.

Iterable :  객체가 'forEach'문장을 사용할 수 있음을 지정.

Collection : 여러개의 객체를 하나의 객체에 담아 처리할 때의 메서드 지정.

List : 목록형 데이터를 처리하는 것과 관련된 메서드 지정.

RandomAccess : 목록형 데이터에 보다 빠르게 접근할 수 있도록 임의로 접근하는 알고리즘이 적용된다는 것을 지정.

 

 

---

 

LinkedList

• LinkedList는 불연속적(비순차적)으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있음.
• LinkedList는 삭제가 간담함. (삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 되므로 삭제가 간담함)
• LinkedList는 새로운 데이터 추가하는 처리속도가 매우 빠름. (새로운 요소를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면됨)
• LinkedList는 ArrayList와 비교했을 때 데이터를 추가/변경할 때 유리함.

 

종류	설명
Linked List (링크드 리스트)	단방향. (다음요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어려움) LinkedList의 각 요소들은 자신과 연결된 다음 요소에 대한 참조와 데이터로 구성됨.
Doubly Linked List (이중 연결리스트)	양방향 참조.  링크드 리스트의 접근성을 더 향상시킴. 링크드 리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능함. Java에서 구현된 LinkedList 형태.
Doubly Circular Linked List (이중 원형 연결리스트)	이중 연결리스트의 접근성을 더 향상시킴. 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시킴으로써, 마지막요소의 다음요소가 첫번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 됨.

 

---

 

Stack

• 클래스로 구현되어 있으므로 상속받으면 사용가능.
• Stack은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어 있음.
• Stack은 순차적으로 데이터를 추가하고 삭제하는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합.

 

 

---

 

Queue

• 인터페이스로 구현되어 있으므로 Queue를 직접 구현하거나, Queue를 구현한 클래스(ex.LinkedList)를 사용하면 됨.
• Queue는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)의 구조로 되어 있음.
• Queue는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, 데이터의 추가/삭제가 쉬운 LinkedLiis로 구현하는 것이 적합함.

 

 

 

 

 

 

 

 

 

 

 

 

참고 :

onsil-thegreenhouse.github.io/programming/java/2018/02/21/java_tutorial_1-23/

, 자바의 정석[남궁성 지음 / 도우출판] (교재)