리스트 (1) - 개요

1. List

List(리스트)는 순서가 있는 데이터를 나열한 것이다. 나열의 의미는 중간에 빈공간이 없어야한다는 것이고, 순서의 의미는 데이터가 무작위로 섞여있는 것이 아니라 차례대로 저장되었다는 의미이다. 

 

[그림] 리스트 자료구조

 

2. List(리스트) VS Array(배열) VS Set(집합)

리스트와 비슷한 자료구조로 배열과 집합이 있다. 배열은 같은 타입의 데이터가 고정된 사이즈로 저장된 자료구조이고, 리스트는 같은 타입의 데이터가 고정되지 않은 사이즈로 저장되는 자료구조이다. 즉, Array는 사이즈가 고정되어 사이즈를 넘어가면 대처가 불가능하지만, 리스트는 사이즈가 유동적이다.

 

집합의 경우 리스트와 다르게 순서가 없고 중복된 자료의 저장을 허용하지 않는다. 때문에, 리스트의 경우 [1, 2, 3]과 [2, 1, 3]이 다른 리스트로 평가되지만 집합의 경우 {1, 2, 3}과 {2, 1, 3}이 동일한 구조로 평가받으며, 집합의 경우는 Index를 사용하거나 N번째 원소를 뽑는 등의 작업을 수행할 수 없다. (순서가 없기 때문에)

 

 

---

List : [1, 2, 3, 4] $\neq$ [2, 1, 3, 4]

 

Set : {2, 1, 3} $=$ {1, 2, 3}

 

Array : Fixed Size Structure

 

---

 

3. List를 구현하는 방법

1) 배열리스트 (ArrayList) : 용량이 가득차면 새 배열을 만들고 옮겨 담는 방식

2) 연결리스트 (LinkedList) : 노드라는 포인터구조를 계속해서 이어서 사용