리스트의 개념 (p71)

자료를 순서와 상관없이 무작위로 저장하는 집합과는 달리

리스트(list)는 순서에 따라 차레대로 저장하는 자료 구조를 말한다.

 

집합 이미지

 

리스트에 각 자료는 이웃하는 원소들과 한 개씩만 대응되기

때문에 선형 리스트라고도 한다.

 

이러한 리스트는 자료를 메모리에 저장하는 방법에 따라

순차 리스트와 연결 리스트로 구분한다.

 

 

순차 리스트는 배열을 이용하여 구현하기 때문에

첨자를 이용한 자료 접근 속도가 빠르며, 자료들이 나열되어

있는 논리적 순서와 실제 기억 고간에 저장되는

물리적 순서가 같다.

 

그러나 자료의 삽입이나 삭제 연산 시 원소들을 일일이

이동 시켜야 하는 배열의 문제점도 그대로 지니고 있다.

 

순차 리스트

 

연결 리스트는 물리적인 저장 공간 내에 각각 흩어져 있는

자료들이 링크로 서 연결되어 있는 구조를 말한다.

선행 자료에는 후속 자료를 가리키는 주소가 포함되어

한 방향으로 연결된다. 연결 방식에 따라 단순 연결 리스트

와 원형, 이중 연결 리스트로 나뉜다.

 

연결 리스트