[자료구조]리스트(List)

리스트

리스트에는 항목들이 차례대로 저장되어 있다.

리스트의 항목들은 순서 또는 위치를 가진다. 

앞서 살펴본 스택과 큐도 넓게 보면 리스트의 일종이다.

집합은 각 항목 간에 순서의 개념이 없기 때문에 리스트는 집합하고는 다르다.

 

리스트의 구현

리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다.

 

1. 배열을 이용한 구현

   배열을 이용하면 리스트를 가장 간단하게 구현할 수 있다.

   장점은 구현이 간단하고 속도가 빠르다는 것이다.

   단점은 리스트의 크기가 고정된다는 것이다.

   따라서 만약 데이터를 추가하고 싶은데 더 이상 남은 공간이 없다면 문제가 발생한다.

   또한 리스트 중간에 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터들을 이동하여야 한다.

 

   배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당된다.

   이것을 리스트의 순차적 표현(sequential representation)라고도 한다.

 

 

2. 연결 리스트를 이용한 구현

   포인터를 이용하여 연결 리스트를 만드는 방법이다.

   연결 리스트는 필요할 때마다 중간에 속지를 추가해서 사용할 수 있는 바인더 공책과 비슷하다.

   장점은 크기가 제한되지 않고, 중간에서 쉽게 삽입하거나 삭제할 수 있는 유연한 리스트를 구현할 수 있다는 것이다.

   단점은 구현이 복잡하고, 임의의 항목을 추출하려고 할 때는 배열을 사용하는 방법보다 시간이 많이 걸린다는 것이다.

   또한 데이터뿐만 아니라 포인터도 저장해야 하므로 메모리 공간을 많이 사용한다.