선형 리스트 원소 삽입

선형 리스트(Linear List)는 데이터를 순차적으로 저장하는 자료구조이며 일반적으로 배열(Array) 형태로 구현된다.

선형 리스트에서 삽입(Insertion)이란 새로운 데이터를 특정 위치에 추가하는 과정을 의미한다.

배열 기반 선형 리스트에서는 중간 삽입 시 뒤에 있는 원소들을 이동시켜 공간을 만든 후 데이터를 삽입해야 한다.

삽입 알고리즘 전체 흐름

  1. 삽입 위치 탐색
  2. 뒤 원소 이동
  3. 데이터 삽입
  4. 리스트 크기 증가

1. 삽입위치 탐색

새로운 원소가 들어갈 삽입 위치 k를 찾는다.

예를 들어 다음과 같은 정렬된 리스트가 있다고 가정한다.

10 20 40 50 60 70

여기에 30을 삽입하려면

10 20 30 40 50 60 70

이 되어야 하므로 20과 40 사이가 삽입 위치가 된다.

2. 뒤 원소 이동

배열은 중간에 빈 공간이 없기 때문에 삽입 위치 이후의 원소들을 한 칸씩 뒤로 이동시켜야 한다.

삽입 전

10 20 40 50 60 70
      ↑
   30 삽입 위치

원소 이동 과정

10 20 _ 40 50 60 70

이 과정에서 뒤에 있는 원소들이 뒤에서부터 한 칸씩 이동하게 된다.

3. 새로운 원소 삽입

공간이 확보되면 해당 위치에 새로운 값을 삽입한다.

10 20 30 40 50 60 70

4. 리스트 크기 증가

삽입이 완료되면 리스트의 원소 개수를 1 증가시킨다.

insertElement

int insertElement(int L[], int n, int x){
    //원소의 크기를 비교하여 삽입 위치 k 찾기
	for (i = 0; i < n; i++)
	{
		if (L[i] <= x && x <= L[i + 1])
		{
			k = i + 1;
			break;
		}
	}

    // 삽입 원소가 가장 큰 경우
	if (i == n)
		k = n;

    // 삽입 원소가 가장 큰 경우
	if (i == n)
		k = n;

    // 삽입 위치에 원소 삽입
    L[k] = x; 
	return move;
}

정리

배열 기반 선형 리스트는 구조가 단순하고 접근 속도가 빠르다는 장점이 있지만, 삽입이나 삭제 연산 시 기존 데이터를 이동해야 한다는 단점이 존재한다.

이러한 이유로 데이터 삽입과 삭제가 빈번하게 발생하는 경우에는 연결 리스트(Linked List) 와 같은 자료구조를 사용하는 것이 더 효율적일 수 있다.

댓글남기기

참고