6. List#1 - LinearList

List는 크게 LinearList와 LinkedList로 분류할 수 있다. 이 중 오늘은 LinearList에 대해서 다루어 보고자 한다.

 

LinearList는 자료구조의 가장 단순한 나열 방식으로 순서를 가진 항목들의 모임이다. 다시 말해 일반적으로 쓰는 Array 배열과 같다고 생각하면 된다.

-> 장점 : 구현이 간단하다.

-> 단점 : 삽입, 삭제 시 오버헤드 항목의 개수 제한으로 비효율적이다.

 

LinearList를 구현할 기본 함수를 먼저 셋팅해 주었다.

 

 

※ 원소 삽입

중간에 원소가 삽입되면, 그 이후 원소들은 한 자리씩 자리를 뒤로 이동해서 물리적 순서를 논리적 순서와 일치시켜야 한다.

 

① 원소를 삽입할 빈자리를 만든다.

② 준비한 빈 자리에 원소를 삽입한다.

 

기존 배열

10

20

30

40

50

60

삽입을 위한 배열

10

20

새로운 값

30

40

50

60

          0                     1                    k                   k+1                k+2                 k+3                  n

 

이렇게 한 칸씩 미루어 삽입할 자리를 만들어 준다. 여기서 우리는 삽입할 자리를 만들기 위해 얼마나 이동을 해야 할까를 생각해 볼 수 있다.

(n+1)개의 원소로 이루어진 선형 리스트에서 k번째 자리에 원소를 삽입해야 한다면 인덱스 n번째 원소 부터 k번째 원소까지 총 n-k+1개의 원소를 이동시켜야 하는 것을 알 수 있다.

 

 

삽입함수를 구현해 주었다. 이 코드에서 가장 중요한 부분은 for문의 조건이라고 생각한다. 작은 인덱스부터 큰 인덱스로 증가시키면서 반복시켜 주게 되면 같은 값으로 계속 덮어쓰이게 되므로 반드시 큰 인덱스에서 작은 인덱스로 내려가면서 반복 시켜 주어야 한다.

또한 isFull함수를 사용하여 리스트가 가득 차 있는지 확인해 주어야 한다. 가득 찬 리스트에는 더이상 삽입할 수가 없다.

 

 

※ 원소 삭제

중간에 원소가 삭제되면, 그 이후의 원소들을 한 자리씩 앞으로 이동시켜 물리적 순서를 논리적 순서와 일치시켜야 한다.

 

기존 배열

10

20

30

40

50

60

70

삭제 배열

10

20

40

50

60

70

         0                     1                     k                   k+1                k+2                   ...                    n

 

위와 같이 30을 삭제시켜 주었다면 40~70 값들을 한 칸씩 앞으로 당겨 준다. 이를 통해 삭제 후, 빈 자리를 채우기 위한 이동 횟수를 살펴 볼 수 있다.

n+1개의 원소로 이루어진 선형 리스트에서 k번째 자리의 원소를 삭제한다면, k+1번째 원소부터 n번째 원소까지

총 n-(k+1) + 1 = n-k 개의 이동 횟수를 가지게 된다.

 

 

삭제 함수를 구현해 주었다. 이 함수에서 중요한 부분은 삽입 함수와 다르게 아래에서 부터 위로 증가시키면서 칸을 줄어들게 한다는 것과 삭제 위치의 요소값 반환을 위해 item 변수에 삭제 위치를 미리 입력시켜준다는 것이다.

또한 isEmpty 함수를 사용하여 리스트가 비어있는지를 확인해 주어야 한다. 삭제할 값이 없으면 삭제도 이루어질 수 없다.