(Data Structure) 선형 리스트

선형 리스트(Linear List)

순서가 있는 집합이며, 기억 공간에 연속적으로 저장되는 자료구조 형태이다.

(a₁, a₂, a₃, …) 처럼 순서대로 저장된 구조이다.

이러한 선형 리스트에는 다음과 같은 연산이 가능하다.

1. length - 리스트 길이 구하기
2. access - 리스트 내의 원소 위치 찾기
3. search - 리스트 내의 i번째 원소 찾기
4. modify - i번째 위치의 값을 새로운 값으로 변경
5. insert - i번째 위치에 새로운 원소 삽입
6. delete - i번째 위치의 원소 제거

선형 리스트에서는 모든 원소가 순서대로 저장되어 있어, 연속적인 특성을 가진다.

위에서 언급한 연산을 수행 할때도 연속적인 특성을 계속 유지하게 된다.

앞서 말한 연산들 중에서도 1~4 번 연산은 리스트의 인덱스 값을 이용해 순조롭게 사용이 가능하다.

그러나 5, 6번 연산은 연속성을 유지하려는 선형리스트의 특성 때문에 많은 작업시간을 소모하게 된다.

새로운 원소를 삽입하거나 특정 원소를 제거하는 작업은 원소들의 이동이 많아지기 때문이다.

가령 n개의 자료들로 이루어진 선형 리스트에서 i번째 위치에 새로운 원소를 삽입하려 할때,

i번째 위치에 한개의 원소가 들어감으로써 i번째 위치보다 뒤에 위치한 원소들이 모두 한칸씩 뒤로 이동해야 한다.

새로운 원소가 들어갈 자리를 마련하기 위해 기존에 있던 다수의 원소들이 이동하는 것이다.

즉, 새로운 한 원소를 삽입할때는 n - i 번의 원소 위치 이동이 필요하다.

비슷한 방법으로 생각하면 i번째 위치의 원소를 삭제할 때는 n - i -1번의 원소 위치 이동이 필요함을 알 수 있다.

이러한 선형 리스트의 구조를 통해

• 선형 리스트는 자료구조 중 가장 간단한 구조이다
• 자료 영역을 넓히고 싶을때 연속 공간이 요구된다.
• 삽입, 삭제시 원소의 이동이 매우 많다.
• 연속된 구조이므로 기억 공간의 밀도는 1, 효율이 좋다.

이와 같이 생각해 볼 수 있었다.