리스트(List)의 추상 자료형

리스트란

리스트 (또는 선형 리스트)는 항목들이 차례로 정리된 선형 자료구조를 의미한다. 순서가 있기 때문에 리스트는 집합과 다르다.

리스트는 스택이나 큐와 달리 중간에 데이터를 삽입하거나 삭제할 수 있다. 대신 그만큼 구현시에 고려해야 할 점들도 많다.

Untitled

리스트의 추상 자료형

리스트는 배열로 만들 수도 있고 연결 리스트로 만들 수도 있다. 배열로 리스트를 만들면 간편하지만, 크기의 제한 문제도 있고 항목을 중간에 추가 하거나 삭제할 때 요소들의 이동이 발생하기 때문에 성능이 떨어지는 문제도 있기 때문에 대부분의 경우 연결 리스트를 이용하여 리스트를 구현한다.

배열로 구현한 리스트

데이터 멤버

리스트를 가장 간단하게 구현할 수 있는 방법은 배열을 이용하는 것이다. 배열을 이용하여 리스트를 만들 때는 배열의 크기를 나타내는 변수 MAX_LIST_SIZE와 현재 리스트에 저장된 요소의 개수를 나타내는 변수 length가 필요하다.

Untitled

모든 요소들은 배열의 첫 번째 위치부터 차곡차곡 저장되어야 하고 중간에 비어 있는 항목이 없어야 하는 것이 배열을 이용한 리스트의 기본 가정이다. length 변수는 새로운 요소가 리스트의 맨 뒤에 추가될 때 삽입되어야 하는 위치를 나타낸다. 리스트가 처음 만들어지면 length는 0이 된다.

Untitled

주요 연산

삽입 연산

리스트 중간에 요소를 삽입하려는 경우, 바로 삽입하면 해당 위치에 있는 다른 요소가 사라지게 되므로, 해당 위치 이후의 모든 요소들을 먼저 뒤로 이동 시킨 후에 삽입하려는 요소를 삽입한다.

Untitled

삭제 연산