본문 바로가기
전공

자료구조_선형 구조

fldus 2024. 7. 9. 03:24

선형 구조

연결리스트의 개요

연결리스트의 정의 - 연결리스트(Linked List)는 데이터를 일렬로 저장하는 자료구조로, 각각의 노드(Node)가 데이터와 다음 노드를 가리키는 포인터(Pointer)로 구성되어 있다. 즉 하나의 노드에는 데이터를 담는 변수 하나와 다음노드를 가리키는 변수 하나가 있다.

 

배열과 연결리스트 비교

 - 배열 : 같은 타입(type)의 자료를 연속된 공간에 저장하기 위해 사용하는 선형 구조

 // 데이터 수가 자주 바뀌지 않고, 참조가 자주 일어날 때 배열을 사용하는 것이 유리하다.

 - 연결리스트 : 기억 공간에 물리적으로 흩어져 있는 자료들이 논리적인 순서를 갖도록 링크를 사용해 연결한 선형 구조

 // 데이터의 삽입과 삭제가 자주 일어나서 데이터의 수가 자주 바뀔 때 연결리스트를 사용하는 것이 유리하다.

구분 배열 연결리스트
검색 데이터에 직접 접근하므로 읽기 / 쓰기가 연결리스트에 비해 빠름 데이터에 순차 접근해야 하므로 읽기 / 쓰기가 배열에 비해 느림
데이터 / 구조 변경 데이터 추가/삭제 시 반복 이동이 필요함 노드 추가 / 삭제 용이
기억 공간 코딩 시 정해진 크기만큼 정적 할당 ( 연속 공간 ) 노드 필요 시 동적 할당하여 연결함 ( 불연속 공간 )
추가 기억 공간 추가 공간 없음 링크 필드 추가
소멸 지역 배열은 함수 종료 때
전역 배열은 프로그램 종료 때		 매 노드마다 free() 함수를 사용
데이터 접근 시간 복잡도 O(1) O(n)

*  연결리스트는 데이터의 동적인 관리와 삽입/삭제 연산의 효율성을 중시할 때 유용한 자료구조이다. 하지만 임의 접근이 필요한 경우나 메모리 공간을 절약해야 하는 상황에서는 배열을 사용하는 것이 더욱 효율적이다.

 

연결리스트의 종류

단순 연결리스트 ( Singly Linked List )

 - 일반적으로 연결리스트는 단순 연결리스트를 의미하며, 각 노드에는 다음 노드를 가리키는 포인터만 있다.

 // 단순 연결리스트의 기본 구조

 p -> [ data | link ] -> [ data | link ] -> [ data | link ] -> [ data | * ^ ]

*  ^ - NULL을 의미한다.

 

원형 연결리스트 ( Circular Linked List )

 - 단순 연결리스트와 유사하지만, 마지막 노드가 첫 번째 노드를 가리키는 구조이다.

 - 시작과 끝이 연결된 순환 구조로 되어 있어서 주로 순회하며 탐색하는 알고리즘에 자주 사용된다.

 // 원형 연결리스트의 기본 구조

 head -> [ NULL | link ] -> [ data | link ] -> [ data | link ] -> [ data | link ] -> (data가 NULL인 노드를 가리킴 )

*  원형 연결리스트는 순환적인 자료구조에 유용하게 사용된다. 하지만 구현이 복잡할 수 있으며, 순회 중에 무한 루프에 빠질 수 있는 잠재적인 위험이 있다.

 

이중 연결리스트 ( Doubly Linked List )

 - 각 노드에 이전 노드와 다음 노드를 모두 가리키는 포인터가 있다.

 - 단순 연결리스트와 원형 연결리스트의 특징을 조합한 형태로, 양방향으로 순차 접근과 역방향 탐색이 가능하다.

 - 순환 구조로 되어 있어서 순환적인 작업에 유용하다.

 - 이전 노드에 대한 참조가 필요한 적업에 유용하지만, 단순 연결리스트보다 더 많은 메모리를 사용한다는 단점이 있다.

 // 이중 연결리스트의 기본 구조

 p1 -> [ ^ | data | link ] <-> [ link | data | link ]  <-> [ link | data | link ]  <-> [ link | data | ^ ] <- p2

*  이중 연결리스트를 이용하면 데큐(Deque)나 양방향 큐(Doubly Ended Queue)를 쉽게 구현할 수 있다.

 

연결리스트의 운용

연결리스트 생성 / 연결리스트의 마지막에 새로운 노드 추가 / 노드 소멸

#include<stdio.h>
#include<stdlib.h>
// 노드 소멸 - 재귀 호출을 통해  연결된 역순으로 노드가 사라지게 함
void deleteLinkedList(struct node* p){
	if(p!=NULL){
    	deleteLinkedList(p->link);
        printf("%c.", p->data);
        free(p);
    }
}

int main(void){
	// 연결리스트 생성
	struct node{
    	char data;
        struct node* link;
    };
    struct node* head = (struct node*)malloc(sizeof(struct node));
    struct node* p;
    char input = ' ';
    head->data = input;
    head->link = NULL;
    p = head;
    
    printf("데이터 입력 : ");
    scanf_s("%c", &input, 1);
    getchar();
    
    while(input != '0'){
    	// p가 간접 소유한 노드 다음에 새로운 노드를 추가
    	p->link = (struct node*)malloc(sizeof(struct node));
        p = p->link;	// p는 다음 노드로 이동
        p->data = input;
        p->link - NULL;
        printf("데이터 입력 : ");
	    scanf_s("%c", &input, 1);
    	getchar();
    }
    
    printf("\n연결리스트 출력 : ");
    p = head->link;
    while(p != NULL){
    	printf("%c", p->data);
        p = p->link;
        if(p != NULL) printf(" -> ");
    }
    
    // 노드 소멸
    p = head;	// p를 맨 앞으로 이동
    deleteLinkedList(p);
    head = NULL;	// head는 NULL값을 갖게 되어 참조하는 노드 없게 됨.
    return 0;
}

*  구조체를 이용해 연결리스트를 생성하면 새로운 노드를 추가하거나 기존 노드를 삭제할 때 메모리를 효율적으로 사용할 수 있다.

*  'head'는 연결리스트의 시작을 나타내며, 노드 접근 및 첫 번째 노드를 가리키는 포인터로서 중요한 역할을 한다.

*  구조체를 이용해 동적으로 할당된 노드이므로, 삭제한 이후에는 노드의 메모리를 반드시 해제해야 메모리의 누수 현상을 방지할 수 있다.

 

노드 삽입

p 다음에 노드 삽입

// 현재 포인터 p가 가리키는 노드 다음에 새로운 노드(ins) 삽입
struct node* ins = (struct node*)malloc(sizeof(struct node));
ins->data = '0';
ins->link = p->link;	// 1. p가 현재 가리키는 link주소를 새로운 노드가 가리키도록 한다.
p->link = ins;	// 2. p의 link주소가 새로운 링크를 가리키도록 한다.

 

노드 삭제

p 다음 노드 삭제

// p가 현재 가리키는 노드 다음의 del 노드 하나 삭제
struct node* del = p->link;
p->link = del->link;	// 1. del 노드가 가리키는 주소를 p가 가리키도록 한다.
free(del);	// 2. del 노드의 메모리를 해제한다.

스택(Stack)의 개요

스택의 정의

 - 스택(Stack)은 자료를 보관할 수 있는 선형 구조(Linear Structure)이다.

 - 가장 마지막에 추가된 데이터가 가장 먼저 꺼내지는 구조인, 후입선출(LIFO, Last-In-First-Out) 방식을 따른다.

 - 데이터를 넣는(push) 동작과 데이터를 꺼내는(pop) 동작을 지원한다.

*  스택(Stack)은 먼저 들어간 데이터가 나중에 나오는 선입후출(FILO, First-In-Last-Out) 방식이기도 하다.

 

 // 스택에서 사용되는 용어

  • top : 데이터 상단 / -1로 초기화 ( underflow인지 확인하기 위해서 )
  • base : 스택의 시작 위치로 가장 아래쪽 ( 배열 인덱스 0 )
  • underflow : base를 벗어나면 발생 ( 배열 인덱스 -1 이하 )
  • limit : push 할 수 있는 한계 ( 배열의 끝 )
  • overflow : limit을 벗어나면 발생
  • push() : 스택에 데이터를 삽입하는 작업 / top++
  • pop() : 스택의 top에서 데이터를 꺼내는 작업 / top--

// 스택의 장점과 단점

스택의 장점 스택의 단점
 - 구현이 간단하고, 기본적인 연산이 빠르게 수행된다.
 - 재귀 알고리즘에 사용된다.
 - 자료를 역순으로 처리할  때 유용하게 사용된다.
 - 메모리 할당과 해제가 쉽다.		  - 가장 먼저 추가된 데이터르 먼저 처리할 때는 비효율적이다.
 - 스택은 고정된 크기를 가지기 때문에 미리 크기를 예측해서 메모리를 할당해야 한다.
 - 중간에 있는 데이터의 삭제가 어렵다.

*  웹 브라우저의 뒤로 가기 기능도 스택을 이용한다. / 사용자가 방문한 페이지의 기록을 스택에 저장하고, 이후 스택에서 페이지를 꺼내어 뒤로 가기를 구현한다.

 

스택의 특징 - 스택은 데이터를 저장하고 관리하는 자료구조 중 하나이다.

  • 후입선출(LIFO)
     - 가장 최근에 삽입된 데이터가 가장 먼저 삭제되는 구조이고, 이는 데이터의 입출력 순서가 역순으로 이루어지는 것을 의미한다.
     // 재귀 알고리즘 - 최근에 호출한 함수부터 종료됨
  • 함수 호출과 재귀 알고리즘
     - 함수 호출 시 호출된 함수의 정보를 스택에 저장하며, 함수 실행이 종료되면 스택에서 해당 정보를 꺼내어 이전 상태로 돌아간다. 같은 원리로 재귀 알고리즘에 스택이 사용된다.
  • 제한된 접근
     - 스택은 상단(top)에 대한 접근만 가능하며, 다른 요소에는 직접적으로 접근할 수 없다.
     // top으로 pop(), push() 접근
     - 스택에는 오직 상단의 요소만 확인 및 삭제 작업이 가능 -> 스택을 간단하고 직관적인 자료구조로 사용할 수 있다.
  • 메모리의 한정된 사용
    = 크기가 정해진 배열일 때만 해당 / 연결리스트는 해당 xx
     - 스택은 메모리 공간을 한정적으로 사용하므로, 스택에 저장할 수 있는 데이터의 요소도 제한되어 있다.
     - 스택이 가득 찬 상태에서 삽입 연산은 스택 * 오버플로우(Stack Overflow)로 이루어질 수 있다.
  • 삽입과 삭제가 상수 시간에 이루어짐
     - 스택은 가장 상단(top)에 있는 요소만 접근하여 데이터를 삭제할 수 있다.
     - 삽입과 삭제 연산의 시간 복잡도는 상수 시간 O(1)이다.

*  오버플로 - 주어진 공간 또는 범위를 넘어서 데이터가 저장되거나 처리되는 현상

// 미로 찾기에 활용된다.

 

배열과 연결리스트의 비교 - 스택은 후입선출(LIFO, Last-In-First-Out)의 기본 규칙만 따른다면 배열(Array)과 연결리스트(Linked List) 두 가지 방법으로 모두 구현할 수 있다.

배열로 스택 구현 연결리스트로 스택 구현
 - 구현이 간단하고 빠르게 접근이 가능
 - 배열은 크기를 미리 지정해야 하므로, 스택의 크기가 유동적일 때 메모리의 낭비가 발생
 - 스택이 꽉 찬 상황에서는 새로운 요소를 추가할 수 없음 (push() 불가능)		  - 크기에 대한 제약이 없어 메모리의 유연한 사용이 가능
 - 새로운 요소를 추가할 때마다 동적으로 메모리를 할당하므로, 효율적인 메모리 사용이 가능
 // 메모리의 크기는 정해져 있기 때문에 무한하지 않아서 동적할당이 유연해도 무한하게 사용X
 - 배열에 비해 접근 속도가 느리고 구현이 복잡

 

스택(stack)의 구현

배열로 구현 - 배열의 끝에서부터 데이터를 삽입(push)하고 삭제(pop)하면서 스택을 구현한다. 이때 스택에 데이터를 삽입할 위치를 가리키고 있는 변수 top의 초기값은 -1로 설정한다.

*  배열 - 대부분의 프로그래밍 언어에서 기본적으로 제공하는 자료구조이기 때문에, 스택을 배열로 구현하면 다른 프로젝트나 코드에서 재사용하기 용이하다.

#include<stdio.h>
#define SIZE 6
int stack[SIZE] = {0, };
int top = -1;

int push(int data){
	if(top == SIZE-1){
    	printf("stack overflow!\n");
        return -1;
    }
    stack[++top] = data;
    return 0;
}

int pop(void){
	if(top == -1){
    	printf("stack underflow!\n");
        return -1;
    }
    return stack[top--];
}

int main(void){
	// 정상적으로 push()됨
    push(10); push(20); push(30); push(40); push(50); push(60);
    // overflow 발생으로 push()되지 않고, 'stack overflow!'를 출력
    push(70);
    
    // 정상적으로 pop()됨
    printf("1st pop: %d\n", pop());
    printf("2nd pop: %d\n", pop());
    printf("3rd pop: %d\n", pop());
    
    // 정상적으로 push()됨
    push(80);
    
    // 정상적으로 pop()됨
    printf("4th pop: %d\n", pop());
    printf("5th pop: %d\n", pop());
    printf("6th pop: %d\n", pop());
    printf("7th pop: %d\n", pop());
    
    // top은 -1이므로 underflow 발생.
    // 'stack underflow!'를 출력하고 리턴받은 -1도 출력
    printf("8th pop: %d\n", pop());
    return 0;
}

 

연결리스트로 구현 - 연결리스트의 노드(Node)는 데이터 필드와 다음 노드를 가리키는 포인터로 구성되어 있다. 따라서 연결리스트의 맨 앞에 새로운 노드를 삽입하고, 삭제할 때는 맨 앞의 노드를 제거한다.

*  연결리스트 - 동적인 크기 조정과 유연한 메모리 관리가 필요한 상황에서 편리하다. 하지만 포인터를 사용하기 때문에 메모리 사용량이 더 많아지고 오버해드가 발생할 수 있다.

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

struct node{
	int data;
    struct node*link;
};
struct node* top = NULL;
int cnt=0;

int push(int data){
	struct node* addNode;
    if(cnt >= SIZE){
    	printf("Stack OVerflow!\n");
        return -1;
    }
    addNode = (struct node*)malloc(sizeof(struct node));
    addNode->data = data;
    addNode->link = top;
    top = addNode;
    cnt++;
    return 0;
}

int pop(vode){
	int data;
    struct node* delNode = top;
    if(top == NULL){
    	printf("Stack Underflow!\n");
        return -1;
    }
    data = top->data;
    top = top->link;
    free(delNode);
    cnt--;
    return data;
}

int main(void){
	struct node* freeNode;
    push(10); push(20); push(30);
    printf("POP: %d\n", pop());	// POP: 30
    push(40); push(50);
    printf("스택 유효 데이터(top에서 base까지) : \n");
    while(top!=NULL){	// 50, 40, 20, 10
    	printf("%d, ", top->data);
        freeNode = top;
        top = top->link;
        free(freeNode);
    }
    return 0;
}

큐(Queue)의 개요

큐의 정의

 - 큐는 자료구조의 일종으로, 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In-First-Out) 방식으로 작동한다.

 - 일반적으로 버퍼(Buffer)로 사용되며, 네트워크 운영체제, 멀티프로세스 환경 등에 많이 사용된다.

*  큐는 데이터의 순차적인 처리와 작업의 조정을 위한 효율적인 자료구조로, 다양한 상황에서 유용하게 활용되고 있다.

// Level Order Traversal에 활용된다.


 // 큐에서 사용되는 용어

  • rear : 가장 최근에 추가한 데이터를 지시하는 포인터 또는 인덱스
  • front : 사용할 데이터를 지시하는 포인터 또는 인덱스
  • overflow : 끝까지 add()된 경우에 add()를 시도하면 발생 ( rear == SIZE-1 )
  • underflow : 더 이상 꺼낼 수 없는 경우에 delete()를 시도하면 발생 ( front < rear )
  • add() : 데이터를 추가하는 작업
  • delete() : 데이터를 꺼내 사용하는 작업

 

큐의 종류

 - 선형 큐(Linear Queue) : 가장 기본적인 큐 종류 중 하나로, 큐의 머리(front)와 꼬리(rear)를 가리키는 포인터 변수를 사용하여 데이터를 추가하고 제거한다.

*  선형 큐 - 가장 기본적이고 간단한 형태이지만, 일반적으로 배열을 사용해 구현해서 메모리 낭비 문제가 발생할 수 있다.

 

 - 환형 큐(Circular Queue) : 머리와 꼬리가 원형으로 연결되어 있으며, 큐의 가장 끝에 도달했을 때 배열의 처음으로 다시 돌아가 데이터를 저장할 수 있다.

*  환형 큐 - 메모리를 효율적으로 사용하면서도 크기 제한이 없어 더 유연한 구현이 가능하다.

 // 변수 rear, front가 반복적으로 계속 사용되어 int형의 최대 범위에 도달하게 되면 초기화하는 작업이 필요함.

 

 - 데큐(DeQueue / Double-ended Queue) : 큐의 앞과 뒤에서 모두 삽입과 삭제가 가능하다. 즉, 큐의 특징인 FIFO(First-In-First-Out)와 스택의 특징인 LIFO(Last-In-First-Out)를 모두 갖고 있다.

*  데큐 - 양방향으로 데이터를 처리할 수 있어, 스크롤링, 검색 등 양쪽 방향으로 데이터에 접근해야 하는 상황에 유용하다. 

 

- 우선순위 큐(Priority Queue)

 : 우선순위가 다른 다수의 큐를 동시에 운영하며, 데이터를 저장할 때는 데이터의 우선순위를 고려하여 해당 큐에 저장하고, 꺼낼 때는 우선순위가 가장 높은 데이터를 먼저 꺼내는 자료구조이다.

 : 긴급한 데이터일수록 우선순위가 높은 큐에 저장되며, 우선순위가 높은 큐부터 삭제 작업이 이루어진다.

 : 운영체제의 프로세스 작업 스케줄링 및 네트워크 패킷 스케줄링 등에 사용된다.

 // 비선점 스케줄링 - 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법

 // 선점 스케줄링 - 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

*  우선순위 큐 - 데이터에 우선순위를 할당하여 처리하는 큐이다. 각 데이터는 우선순위와 함께 큐에 추가되며, 우선선위가 높은 데이터가 먼저 처리된다.

*  우선순위가 낮은 큐에 있는 데이터는 무한정 대기해야 할 가능성이 있으므로 일정 시간이 경과하면 우선순위가 높은 큐로 이동시켜야 한다.

 

큐의 구현

배열로 구현 - 포인터를 사용해 큐에 데이터를 삽입(rear)하고 삭제(front)할 수 있다. 즉 포인터를 이용해 처음과 끝 인덱스를 추적하고, 추가 및 제거 작업은 인덱스를 조정하여 처리한다.

*  배열은 큐를 구현하는 데 있어서 편리하고 효율적인 자료구조이다. 하지만 크기가 고정되어 있기 때문에 크기를 동적으로 조정해야 하는 경우에는 별도로 배열 재할당과 데이터 이동 과정이 필요하다.

// 배열로 선형 큐 구현
#include <stdio.h>
#define SIZE 6
int queue[SIZE] = {0, };
int rear = -1, front = 0;

int add(int data){
	if(rear == SIZE -1){
    	printf("Queue is full!\n");
        return -1;
    }
    queue[++rear] = data;
    return 0;
}

int delete(void){
	if(front < rear){
    	printf("Queue is empty!\n");
        return -1;
    }
    return queue[front++];
}

int main(void){
	add(10); add(20);
    printf("%d\n", delete());	// 10
    printf("%d\n", delete());	// 20
    printf("%d\n", delete());	// Queue is empty!	-1
    add(30); add(40); add(50); add(60);
    add(70);	// Queue is full!
	printf("%d\n", delete());	// 30
    printf("%d\n", delete());	/ 40
    add(80);	// Queue is full!
    return 0;
}
// 배열로 환형 큐 구현
#include <stdio.h>
#define SIZE 6
int cqueue[SIZE];
int rear = -1, front = 0, cnt = 0;

int add(int data){
	if(cnt == SIZE){
    	printf("Circular Queue is Full!\n");
        return -1;
    }
    cnt++;
    cqueue[++rear % SIZE] = data;
    return 0;
}

int delete(void){
	if(cnt == 0){
    	printf("Circular Queue is Empty!\n");
        return -1;
    }
    cnt--;
    // delete()호출문 종료 직후 front 1 증가
    return cqueue[front++ % SIZE];
}

int main(void){
	add(10); add(20); add(30);
    printf("%d\n", delete());	// 10
    printf("%d\n", delete());	// 20
    printf("%d\n", delete());	// 30
    printf("%d\n", delete());	// Queue is Empty!	-1
    add(40); add(50); add(60); add(70); add(80); add(90);
    add(100);	// Queue is Full!
    return 0;
}

 

연결리스트로 구현 - front와 rear를 가리키는 두 개의 포인터를 이용해 연결리스트 상에서의 삽입과 삭제 연산이 발생할 때 위치값을 조정하며 처리한다.

*  큐를 연결리스트로 구현하면, 큐의 앞이나 뒤에 요소를 추가하거나 삭제하는 경우 연결리스트가 해당 노드의 연결을 조정함으로써 삽입 및 삭제 작업을 상수 시간 O(1)에 수행할 수 있다.

// 연결리스트를 사용해 선형 큐를 구현
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6

struct node{
	int data;
    struct node * link;
};
struct node* rear - NULL, *front - NULL;
int cnt=0;

int add(int data){
	if(cnt -- SIZe){
    	printf("!ueue is Full!\n");
        return -1;
    }
    if(rear == NULL){
    	rear = (struct node*)malloc(sizeof(struct node));
        front = rear;
    }
    else{
    	rear->link =(strct node*)malloc(sizeof(struct node));
        rear = rear->link;
    }
    rear->data = data;
    cnt++;
    return 0;
}

int delete(void){
	int value;
    struct node* del = front;
    if(cnt==0){
    	prinf("Qudue is Empty!\n");
        return -1;
    }
    value = front->data;
    front = front->link;
    if(front == NULL) rear = NULL;
    free(del);
    cnt--;
    return value;
}

int main(void){
	add(10); add(20); add(30);
    printf("%d\n", delete());	// 10
    printf("%d\n", delete());	// 20
    printf("%d\n", delete());	// 30
    printf("%d\n", delete());	// Queue is Empty!	-1
    add(40); add(50); add(60); add(70); add(80); add(90);
    add(100);	// Queue is Full!
    return 0;
}

 

'전공' 카테고리의 다른 글

Java_예외 처리, 스레드  (0) 2024.10.08
Java_컬렉션 제네릭  (7) 2024.10.08
파이썬_변수, 자료형 / 제어문, 반복문 / 함수  (0) 2024.07.10
자료구조_비선형 구조  (0) 2024.07.09
자료구조_자료구조와 알고리즘  (0) 2024.07.09

'전공' Related Articles

티스토리툴바