선형리스트

선형 리스트란?

선형리스트는 배열을 사용해 순차 자료구조 방식을 구현한다.
배열은 <인덱스,원소> 쌍으로 구성되어 메모리에 연속적으로 할당된다.
이때, 인덱스는 배열 원소의 순서를 나타낸다.

선형리스트를 간단하게 예를 들면 배열을 예로 들 수 있다.
int num[4] = {1,2,3,4};

선형리스트를 저장하는 방법은 행우선이냐, 열우선이냐에 따라서 다르게 저장된다.
예를들어, 다음과 같은 배열이 있다고 하자.

int num[2][4] = {{24,34,44,54},{17,27,37,47}}; 

행우선은 다음과 같이 저장된다.

24 [0][0]
34 [0][1]
44 [0][2]
54 [0][3]
17 [1][0]
27 [1][1]
37 [1][2]
47 [1][3]

열우선은 다음과 같이 저장된다

24 [0][0]
17 [1][0]
34 [0][1]
27 [1][1]
44 [0][2]
37 [1][2]
54 [0][3]
47 [1][3]

그렇다면, A[$n_i$][$n_j$]의 원소 위치를 계산하는 방법은 어떻게 될까?
시작 주소가 a이고, 원소 길이가 l이라면, i행 j열 원소, 즉 A[i][j] 의 위치는
행 우선순위 방법 : a+(i $\times$ $n_j$+j) $\times$ l
열 우선순위 방법 : a+(j$\times$ $n_i$+i) $\times$ l

선형 리스트의 연산과 알고리즘

삽입

선형 리스트는 순차 자료구조 방식으로 구현하므로, 삽입 후에 변경된 논리적 순서와 메모리에 연속 저장된 물리적 순서가 일치해야 한다. 무슨 말이냐하면, 만약에 선형 리스트에 중간에 삽입을 하려고 하면, 자리를 만들고나서 삽입을 해야한다. 자리를 만들기 위해서는 삽입하려고 하는위치 원소부터 한칸씩 모두 뒤로 옮겨야한다.
예를들어 index에 2,3,4,5,6,7 이 있었다. 4자리에 1을 삽입하려고 한다.
그렇다면 2,3,1,4,5,6,7이 되어야한다.

원소가 n+1개(1~n)인 선형리스트에서 k번 자리에 원소를 삽입하려면 k번부터 n번 총 n-k+1개의 원소를 뒤로 한칸씩 옮겨야한다.

삭제

선형리스트에서 원소를 삭제하면 그자리는 빈자리가 되고 빈자리를 뒤의 원소들을 떙겨와서 채워준다.

예를들어, index에 2,3,4,5,6,7이 있었는데 원소3을 삭제했다. 그렇다면 2,4,5,6,7이 된다.

구현

삽입
1.선형리스트L 에서 원소 크기 비교해서 삽입 원소x의 위치 k를 잡는다.
2.선형리스트L 안에 삽입 위치가 없는 경우, 즉 삽입 원소 x가 가장 큰 원소이면(if(i==n))마지막 원소의 뒤인 n이 삽입 위치 k가 된다.
3.삽입 위치 k를 빈자리로 만들기 위해 k번 원소부터 마지막 원소까지 한자리씩 뒤로 이동, 이때 k번부터 이동하면 덮어쓰기가 되어서 자리 이동이 안되므로 마지막에서부터 이동한다.
4.자리 이동으로 만든 k번 자리에 삽입 원소 x를 저장한다.

삭제
1. 선형리스트L에서 원소크기를 비교해 삭제 원소x의 위치 k를 찾는다.
2. K+1번 원소부터 마지막 원소까지 한 자리씩 앞으로 이동한다. 이때 k+1번 자리의 원소를 K번 자리로 이동하면서 덮어쓰기 되므로 삭제 위치인 K에 있던 원소는 없어진다.(삭제된다.)

[listS.h]

#pragma once
#define MAX 10

int insertElement(int L[], int n,int x);
int deleteElement(int L[], int n,int x)

[listS.c]

#include "listS.h"
int insertElement(int L[],int n,int x){ //삽입원소 x, 원소개수 n
	int i,k = 0,move = 0; // move는 자리이동 횟수 카운터

	// 원소를 비교하여 삽입 위치 k 찾기
	for(i = 0; i <n;, i++){
		if(L[i]<=x && x<=L[i+1]){
    		k = i+1;
        	break;
    	}
	}
	if(i == n) // 삽입원소가 가장 큰 원소인 경우
		k = n;

	//마지막 원소부터 K+1원소까지 뒤로 이동
	for(i = n; i > k; i--){
		L[i] = L[i-1];
    	move++;
	}

	L[k] = x;
	return move;

}

int deleteElement(int L[],int n,int x){
	int i,k=n,move=0; // move는 자리이동횟수 카운터
    //원소의 크기를 비교하여 삭제 위치 k 찾기
    for(i = 0; i < n; i ++){
    	if(L[i] == x){
        	k = i;
            break;
        }
    }
    
    if(i == n) move = n;
    
    //k+1부터 마지막 원소까지 앞으로 이동
    for(i = k; i < n-1; i++){
    	L[i] = L[i+1];
        move++;
    }
    return move;
}

[main.c]

#include <stdio.h>
#include "listS.h"

int main(void){
	int list[MAX] = {10,20,40,50,60,70};
    int i, move, size = 6; // size는 리스트에 있는 원소 개수
    printf("\n 삽입전 선형 리스트: ");
    for(i=0;i<size;i++)printf("%3d ",list[i]);
    printf("\n원소의 갯수: %d \n",size);
    
    move = insertElement(list,size,30);
    
    printf("\n삽입 후 선형 리스트:");
    for(i = 0; i<=size; i++)printf("%3d ",list[i]);
    printf("\n원소의 갯수: %d \n",++size);
    printf("\n자리 이동 횟수: %d \n",move);
    
    move = deleteElement(list,size,30);
    if(move == size)printf("\n 선형 리스트에 원소가 없어서 삭제할 수 없습니다.\n");
    else{
    	printf("\n 삭제 후 선형 리스트:")
        for(i=0;i<size-1;i++)printf("%3d ",list[i]);
        printf("\n원소의 개수:%d",--size);
        printf("\n자리이동 횟수:%d \n",move);
    }

	getchar(); return 0;

}

참조

• C로 배우는 쉬운 자료구조