Big fan of Naruto

6 minute read

리스트의 이해

리스트는 데이터를 순차적으로 저장하고 관리할 수 있는 기본적인 자료구조이다. 데이터를 효율적으로 추가, 삭제, 검색하는 기능을 제공하며, 다양한 알고리즘과 프로그램에서 필수적인 역할을 한다.

리스트는 크게 순차 리스트와 연결 리스트 두 가지로 나눌 수 있으며, 두 리스트는 구조와 동작 방식에서 큰 차이를 보인다.

  • 순차 리스트(Array List) : 배열 기반의 자료구조로, 데이터를 연속된 메모리 공간에 저장한다.
    • 장점 : 임의 점근(Random Access)가 가능하여, 특정 위치의 데이터를 빠르게 검색할 수 있다.
    • 단점 : 크기가 고정되어 있어 데이터가 초과하면 메모리를 다시 할당해야 하며, 중간에 삽입/삭제 시 데이터를 이동해야 하므로 비효율적일 수 있다.
  • 연결 리스트(Linked List) : 연결 리스트는 데이터를 저장하는 노드(Node)와 각 노드가 다음 노드를 가리키는 포인터로 구성된다.
    • 장점 : 메모리가 동적으로 할당되며, 크기에 제한이 없다. 중간에 데이터를 삽입하거나 삭제할 때 데이터 이동이 필요하지 않아 효율적이다.
    • 단점 : 특정 데이터를 찾으려면 순차적으로 탐색해야 하므로 검색 속도가 느리다.(Random Access X)

리스트는 데이터 관리에 중요한 역할을 하며, 상황에 따라 적합한 리스트를 선택해야 한다. 데이터를 빠르게 검색해야 하는 경우 순차 리스트(Array List)가 적합하며, 삽입/삭제가 빈번하게 일어나는 경우 연결 리스트(Linked List)가 적합하다.

리스트의 ADT

 void ListInit(List *plist);
 - 초기화할 리스트의 주소 값을 인자로 전달한다.
 - 리스트 생성 후 제일 먼저 호출되어야 하는 함수

 void LInsert(List *plist, LData data);
 - 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

 int LFirst(List *plist, LData *pdata);
 - 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다.
 - 데이터의 참조를 위한 초기화가 진행된다.
 - 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

 int LNext(List *plist, LData *pdata);
 - 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
 - 순차적인 참조를 위해서 반복 호출이 가능한다.
 - 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
 - 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

 LData LRemove(List *plist);
 - LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
 - 삭제된 데이터는 반환된다.
 - 마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

 int LCount(List *plist);
 - 리스트에 저장되어 있는 데이터의 수를 반환한다.

배열을 기반으로 리스트 구현하기

헤더 파일의 정의

#ifndef __ARRAY_LIST_H_
#define __ARRAY_LIST_H_

#define TRUE 1
#define FALSE 0

#define LIST_LEN 20
typedef int LData; //LData에 대한 typedef 선언

typedef struct __ArrayList{//배열 기반 리스트를 정의한 구조체
    LData arr[LIST_LEN];//리스트의 저장소인 배열
    int numOfData;//저장된 데이터 수
    int curPosition;//데이터 참조위치를 기록
} ArrayList;

typedef ArrayList List;

void ListInit(List *plist); //초기화
void LInsert(List *plist, LData data);//데이터 저장

int LFirst(List *plist, LData *pdata);//첫 데이터 참조
int LNext(List *plist, LData *pdata);//두 번째 이후 데이터 참조

LData LRemove(List *plist);//참조한 데이터 삭제
int LCount(List *plist);//저장된 데이터의 수 반환

#endif

삽입과 조회

초기화 함수

void ListInit(List *plist){
    (plist->numOfData) = 0; //리스트에 저장된 데이터의 수 = 0
    (plist->curPosition) = -1; //현재 아무 위치도 가리키지 않음을 의미
}
  • 앞서 정의한 구조체 ArrayList를 보면 초기화할 대상이 무엇인지 파악할 수 있다. 구조체의 멤버 curPosition에는 배열의 인덱스 값이 저장된다. 그리고 이 변수에 저장된 값을 통해 LNext 함수와 LFirst 함수가 참조해야 할 배열의 위치를 알 수 있다. 그래서 curPosition은 0이아닌 -1로 초기화한 것이다. 즉 아직 데이터의 참조가 진행되지 않았다는 의미이다.

LInsert(데이터 삽입)

void LInsert(List *plist, LData data){
    if(plist->numOfData >= LIST_LEN){//더 이상 저장할 공간이 없음을 의미
        puts("저장이 불가능합니다.");
        return;
    }

    plist->arr[plist->numOfData] = data;//데이터 저장
    (plist->numOfData)++;//저장된 데이터의 수 증가
}
  • 우선 데이터의 수가 배열의 길이를 초과했는지 검사하고 초과하지 않았다면 일반적인 데이터의 저장 과정을 진행한다. 저장할 때는 앞에서부터 채워나간다.

LFirst LNext (데이터 조회 함수)

int LFirst(List *plist, LData *pdata){// 첫번 째 조회
    if(plist->numOfData == 0) //저장된 데이터가 없으면 FALSE
        return FALSE;
    
    (plist->curPosition) = 0;//참조 위치 초기화 : 첫 번째 데이터의 참조를 의미
    *pdata = plist->arr[0];//pdata가 가리키는 공간에 데이터 저장
    return TRUE;
}

int LNext(List *plist, LData *pdata){ // 두 번째 이후의 조회
    if(plist->curPosition >= (plist->numOfData)-1)//더 이상 참조할 데이터가 없다면 FALSE
        return FALSE;
    
    (plist->curPosition)++;
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}
  • 두 함수의 차이점은 다음 한 문장에 있다.
    • LFirst : (plist->curPosition) = 0;
    • LNext : (plist->curPosition)++;
  • LFrist 함수는 curPosition에 저장된 값을 0으로 재설정함으로써 데이터의 참조가 앞에서부터 다시 진행되도록 하는 역할을 한다.
  • LNext 함수는 curPosition 값을 증가시켜서 순서대로 데이터를 참조할 수 있도록 한다.

삭제(Remove)

LData LRemove(List *plist){
    int rpos = plist->curPosition;//삭제할 데이터의 인덱스 값 참조
    int num = plist->numOfData;
    int i;
    LData rdata = plist->arr[rpos];//삭제할 데이터를 임시로 저장
    
    //삭제를 위한 데이터의 이동을 진행하는 반복문
    for(i=rpos; i<num-i; i++)
        plist->arr[i] = plist->arr[i+1];
    
    (plist->numOfData)--;//데이터의 수 감소
    (plist->curPosition)--;//참조 위치를 하나 되돌림
    return rdata;//삭제된 데이터의 반환
}
  • LRemove 함수는 현재 참조 위치(curPosition)의 데이터를 삭제하고, 배열을 유지하기 위해 나머지 데이터를 한 칸씩 이동한다.

Alt text

  • 다음 참조 위치 수정을 해줘야한다.
(plist -> curPosition)--; //참조위치를 하나 앞으로(배열 기준 왼쪽으로)옮긴다.
  • 리스트의 참조 위치를 옮기는 이유는 curPosition은 최근에 참조가 이뤄진 데이터의 인덱스 정보를 담고 있어야한다. 그런데 삭제로 인해 비는 공간을 메우려 데이터를 한 칸씩 앞으로 이동시키면, 아래 그림 첫번째에서 보이듯이 curPosition은 아직 참조가 이뤄지지 않은, 뒤에서 한 칸 앞으로 이동한 데이터를 가리키게 된다. 따라서 curPosition을 앞으로 한 칸 왼쪽으로 이동시켜야 한다.

Alt text

전체 코드

ArrayList.c

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

void ListInit(List *plist){
    (plist->numOfData) = 0; //리스트에 저장된 데이터의 수 = 0
    (plist->curPosition) = -1; //현재 아무 위치도 가리키지 않음을 의미
}

void LInsert(List *plist, LData data){
    if(plist->numOfData >= LIST_LEN){//더 이상 저장할 공간이 없음을 의미
        puts("저장이 불가능합니다.");
        return;
    }

    plist->arr[plist->numOfData] = data;//데이터 저장
    (plist->numOfData)++;//저장된 데이터의 수 증가
}

int LFirst(List *plist, LData *pdata){
    if(plist->numOfData == 0) //저장된 데이터가 없으면 FALSE
        return FALSE;
    
    (plist->curPosition) = 0;//참조 위치 초기화 : 첫 번째 데이터의 참조를 의미
    *pdata = plist->arr[0];//pdata가 가리키는 공간에 데이터 저장
    return TRUE;
}

int LNext(List *plist, LData *pdata){
    if(plist->curPosition >= (plist->numOfData)-1)//더 이상 참조할 데이터가 없다면 FALSE
        return FALSE;
    
    (plist->curPosition)++;
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}

LData LRemove(List *plist){
    int rpos = plist->curPosition;//삭제할 데이터의 인덱스 값 참조
    int num = plist->numOfData;
    int i;
    LData rdata = plist->arr[rpos];//삭제할 데이터를 임시로 저장
    
    //삭제를 위한 데이터의 이동을 진행하는 반복문
    for(i=rpos; i<num-i; i++)
        plist->arr[i] = plist->arr[i+1];
    
    (plist->numOfData)--;//데이터의 수 감소
    (plist->curPosition)--;//참조 위치를 하나 되돌림
    return rdata;//삭제된 데이터의 반환
}

int LCount(List *plist){
    return plist->numOfData;
}

ListMain.c

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

int main(void){
    List list;
    int data;
    ListInit(&list);

    LInsert(&list, 11); LInsert(&list, 22);
    LInsert(&list, 33); LInsert(&list, 44);
    LInsert(&list, 55);

    printf("현재 데이터의 수 : %d \n", LCount(&list));

    if(LFirst(&list, &data)){
        printf("%d ", data);

        while(LNext(&list, &data))
            printf("%d ", data);
    }
    printf("\n\n");

    if(LFirst(&list, &data)){
        if(data==22)
            LRemove(&list);

        while(LNext(&list, &data)){
            if(data==22)
                LRemove(&list);
        }
    }

    printf("현재 데이터의 수 :  %d \n", LCount(&list));

    if(LFirst(&list, &data)){
        printf("%d ", data);

        while(LNext(&list, &data))
            printf("%d ", data);
    }

    printf("\n\n");
    return 0;
}

리스트에 구조체 변수 저장하기

  • 위에서는 리스트에 단순히 정수를 저장하였다. 그런데 실제로는 구조체 변수를 비롯해서 각종 데이터들이 저장 가능하다.

구조체 정의 코드

Point.h

#ifndef __POINT_H__
#define __POINT_H__

typedef struct _point {
	int xpos;
	int ypos;
} Point;

// Point 변수의 xpos, ypos 값 설장
void SetPointPos(Point* ppos, int xpos, int ypos);

// Point 변수의 xpos, ypos정보 출력
void ShowPosition(Point* ppos);

// 두 Point 변수의 비교
int PointComp(Point* pos1, Point* pos2);

#endif

Point.c

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

void SetPointPos(Point* ppos, int xpos, int ypos) {
	ppos->xpos = xpos;
	ppos->ypos = ypos;
}

void ShowPosition(Point* ppos) {
	printf("[%d, %d] \n", ppos->xpos, ppos->ypos);
}

int PointComp(Point* pos1, Point* pos2) {
	if (pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
		return 0;
	else if (pos1->xpos == pos2->xpos)
		return 1;
	else if (pos1->ypos == pos2->ypos)
		return 2;
	else
		return -1;
}

PointListMain.c

#include <stdio.h>
#include <stdlib.h>
#include "ArrayList.h"
#include "Point.h"

int main(void) {
	List list;
	Point comPos;
	Point* ppos;

	ListInit(&list);

	// 4개의 데이터 저장
	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 2, 1);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 2, 2);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 3, 1);
	LInsert(&list, ppos);

	ppos = (Point*)malloc(sizeof(Point));
	SetPointPos(ppos, 3, 2);
	LInsert(&list, ppos);

	// 저장된 데이터의 출력
	printf("현재 데이터의 수는 : %d \n", LCount(&list));

	if (LFirst(&list, &ppos)) {
		ShowPosition(ppos);

		while (LNext(&list, &ppos)) {
			ShowPosition(ppos);
		}
	}
	printf("\n");

	// xpos가 2인 모든 데이터 삭제
	comPos.xpos = 2;
	comPos.ypos = 0;

	if (LFirst(&list, &ppos)) {
		if (PointComp(ppos, &comPos) == 1) {
			ppos = LRemove(&list);
			free(ppos);
		}

		while (LNext(&list, &ppos)) {
			if (PointComp(ppos, &comPos) == 1) {
				ppos = LRemove(&list);
				free(ppos);
			}
		}
	}

	// 삭제 후 남은 데이터 전체 출력
	printf("현재 데이터의 수는 : %d \n", LCount(&list));

	if (LFirst(&list, &ppos)) {
		ShowPosition(ppos);

		while (LNext(&list, &ppos)) {
			ShowPosition(ppos);
		}
	}
	printf("\n");

	return 0;
}

You may also enjoy

[소프트웨어 공학] System modeling(2)

5 minute read

Behavioral Models(행위 모델) Behavioral models는 시스템이 실행 중일 때 나타나는 동적(dynamic) 동작을 표현한다. 이러한 모델은 시스템이 외부로부터 자극(stimulus)을 받았을 때, 무슨 일이 일어나는지, 또는 어떻게 반응하는지를 시각적으로 ...

[컴퓨터 구조] 부동 소수점 (Floating Point)

4 minute read

Floating Point - 부동 소수점 컴퓨터는 정수뿐만 아니라 실수(real number)도 표현할 수 있어야 한다. 특히 과학 계산, 그래픽스, 신호 처리와 같은 분야에서는 아주 크거나 아주 작은 수를 정확하게 표현하는 것이 중요하다.

[소프트웨어 공학] System modeling(1)

11 minute read

System modeling 소프트웨어 시스템을 설계하고 구축하는 과정에서 우리는 그 시스템을 다양한 관점에서 이해하고 설명할 필요가 있다. 단순히 코드나 기능의 나열만으로는 전체 시스템의 구조와 동작을 포괄적으로 파악하기 어렵기 때문이다. 이때 중요한 도구가 바로 시스템 모델링(...

[OS] 파일 시스템 - File Systems

11 minute read

Introduction 현대의 컴퓨터 시스템에서 파일 시스템(file system)은 저장 장치 위에 있는 데이터를 체계적으로 관리하고 접근할 수 있도록 도와주는 핵심적인 소프트웨어 계층이다. 사용자와 운영체제 사이에서 데이터를 어떻게 저장하고, 읽고, 수정하며, 삭제할지를 결정짓...