[자료구조] 순차 자료구조 - 선형 리스트.

문제를 해결하기 위해 추상적으로 정의한 자료와 연산자는 구체적으로 구현되

어 실행되어야 하는데, 연산자의 구현은 처리할 자료를 표현하는 방법에 의해..

결정된다.

따라서 처리할 문제에 대한 자료를 가장 효율적인 방법으로 표현하는 것이 중

요하다.

자료구조에서 기본적인 자료 표현 방법으로는 순차 자료구조와 연결 자료구조

가 있다..

여기서는 순차 자료 구조를 알아보자..

가장 기초적인 자료를 표현하는 방법은 나열 하는 것이다. 동물이면 동물,

식물, 음식, 지리 등등을 나열한 목록을 list 라고 한다..

list 나열한 원소들 간에 순서를 가지고 있는 list를 선형 list 또는 순서 list라고

한다.

리스트를 표현하는 일반적인 방법은 다음과 같다..

list 이름 = ( 항목1, 항목2, 항목 3 )

선형 list는 원소들 같의 논리적인 수서와 메모리에 저장하는 물리적인 순서가

같은 구조로 되어잇는데, 이러한 구조를 순차 자료구조라고 한다..

따라서 순차 자료구조에서는 원소의 논리적인 순서대로 메모리에 연속적으로

저장된다..

즉, 순차 자료구조에서는 원소들이 순서대로 연속 저장되기 때문에 시작 위치

와 원소의 길이를 알면, 특정 원소의 위치를 알 수 있다.

시작 위치가 a고, 원소의 길이가 L 인 list에서 두번째 원소의 길이는

a + L 이고, 세번째 원소의 위치는 a + 2L 이다. 따라서 i 번째 원소의 위치는

a + (i -1 ) * L 이 된다..

 그렇다면, 선형 list 에서의 원소 삽입에 대해 알아보자...

 밥을 먹으로 갔는데, 밥집에 줄이 서있다....

일단 기다린다.. 그런데 누군가 새치기를 했다... (물론 이런경우는 없을 것이지

만 예를 들면이다..)

그렇다면 순번은 한칸씩 뒤로 밀린다...

이 것이 바로 선형 list 에서의 원소 삽입이다...

무언가 list에 순서대로 자료가 저장되어 있지만, 가운데 원소를 하나 집어 넣으

려면, 먼저 삽입할 자리를 만든 후에 그 자리에 원소를 삽입해야 된다..

그렇게 하려면, 메모리에 연속해서 저장되어 있는 자료들을, 한칸씩 뒤로 밀어

야 하겠다..

(n+1) 개의 원소로 이루어진 선형 list 에서 k번 자리에 원소를 삽입하려면,

k번 원소부터 마지막 원소인 n번째  원소까지 n - k + 1 개의 원소를 모두 한자

리씩 뒤로 밀어야 하므로 빈자리를 만들기 위한 이동 횟수는 n - k + 1 이 된다.

그렇다면 반대로 선형 list에서의 원소 삭제를 알아보자.

이번에는 반대로 차례대로 밥집의 줄을 서있는데, 갑자기 앞에 사람이 어디로

가버렸다.. 그렇다면 순서는 한칸씩 앞으로 당겨지게 된다...

이번에는 코드 상으로는 빠진 부분의 값은 뒤의 값이 덮어 버리면 되기 때문에

바로 값이 빠진 곳 부터 한칸씩 앞으로 값을 땡기기만 하면 된다...

이 것을 식으로 쓰면, (n+1)개의 원소로 이루어진 선형 list 에서 k번 자리의

원소를 삭제했다면 k+1번 원소부터 마지막 n번 원소까지 n - ( k + 1 ) + 1개의

원소를 모두 한자리씩 앞으로 옮겨야 하므로 필요한 이동 횟수는 n - ( k + 1 ) +
1 이 되어 정리하면, n - k 가 된다...