공부

우선 List는 무엇인가?

List란 어떤 순서가 있는 데이터의 집합이다. 

그렇다면 List의 종류는 어떤것이 있을까?

1. Array List
2. Linked List 

두 종류가 있다.

1. Array List 

위 그림과 같이 Array List 는 연속적인 공간에 순차적으로 데이터를 저장한다. Array List 의 장점은 Indexing이 가능 하다는 것이다. 단점은 추가/ 삭제가 어렵다는 것이다. 사이즈가 고정되어 있다. 

2. Linked List 

위 그림과 같이 Linked List 는 비연속적인 공간에 순서대로 데이터를 저장한다. Linked List 의 장점은 추가/ 삭제가 쉽다는 것이다. 단점은 위치 탐색을 할때 오래 걸린다는 것이다. 같은 데이터가 들어있으면 Linked List 의 메모리가 좀 더 많다.

두 자료구조의 공통점은 둘 다 순서가 있다는 것이다. 

Array 와 List 의 차이는 무엇일까?

우선 Array란

연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조다. [ ] 를 사용하여 인덱스를 활용할 수 있다. 

인덱스를 사용하면 사이즈가 얼마나 크던지 원하는 자료에 접근할때 걸리는 시간이 동일하다.

List 는 무엇일까?

순서를 가지며 추가, 삭제, 탐색이 가능한 ADT(Abstract Data Type) 이다. Array에 비해서 추상적이다 내부적으로 어떻게 동작하는지 알려주지 않는다. 

* ADT는 구조의 속성과 행위를 설명한다. 

따라서 

• add
• remove
• get
• contains

같은 operation을 사용 가능하다.

List는 어떻게 구현할 수 있을까?

• Array (= ArrayList)
• Linked node (= LinkedList) 

크게 두 가지를 사용하여 구현 가능하다. 

구현에 관점에서 List 는 ADT이고 안에 있는 ArrayList나 LinkedList 등이 자료구조라고 할 수 있다.

큐는 

• Last In Last Out : LILO
• First In First Out : FIFO

구조를 가지고 있다.

큐는 순서를 보장한다. 그렇다면 어떤 곳에 사용할 수 있을까? 

은행 창구 번호표 처리, 메신저의 메신저 함, 티켓팅 시스템 등등 순서 보장이 필요한 곳에서 사용할 수 있을것 같다.