[자료구조] 연결구조(1)

연결구조

연결리스트(linked list)

순차 자료구조에서의 연산시간과 저장공간에 대한 문제를 개선하여 자료를 표현한 방법

자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조를 말함

• 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식임
  • 비순차적 저장(기억장소의 어느 곳에서든지)이 가능함
• 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
• 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현함
• 크기의 변경이 유연하고 더 효율적으로 메모리를 사용할 수 있음
• 순차적인 기억장소의 표현에서 발생하는 이동에 따른 연산 소요시간을 해결할 수 있음

배열 구조와 연결리스트 구조의 표현

순차 자료구조의 배열과 연결리스트 표현의 특징

배열구조	- 계산주소방법에 의해 배열 원소의 위치를 파악할 수 있음 - 순차적인 원소간의 관계에 대한 정보가 필요 없음
연결리스트 구조	- 순차 리스트의 원소를 찾기 위해 다음 원소에 대한 정보가 필요함(포인터 변수 이용, 추가기억공간을 요구) - 배열(임의처리, 직접처리)과 달리 임의의 원소를 처리하지 못하기 때문에 처음부터 연결을 따라 추적해야 함(시간소요) - 포인터를 사용함으로써 노드의 삽입/삭제가 용이함 - 연속적인 기억공간이 없어도 저장이 가능함 - 알고리즘 구현(프로그램 복잡성)이 복잡함 - 노드 탐색 시 무한반복에 빠질 수 있음

연결리스트의 표현

연결리스트 노드의 구조

데이터와 연결(link) 정보를 저장하기 위한 기억공간이 필요함

• 데이터 값 - 항목이 n개인 데이터 필드(1 < i < n)
  • 원소의 값을 저장 - 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성할 수 있음
• 연결 값 - 항목이 n개의 연결 필드(1 < i < n)
  • 다음 노드의 주소를 저장 - 포인터 변수를 사용하여 주소 값을 저장, 하나 이상의 연결로 구성할 수 있음
• 노드의 논리적 표현
• 연결리스트 구조의 논리적 표현

동적 기억장소의 할당/해제

동적 기억장소의 할당

동적 기억장소 할당 함수 - malloc()

배열의 문제점을 해결

• 각 자료 원소는 서로 인접해 있지 않고 기억장소 내에서 어디든지 흩어져 존재함
• 삽입/삭제 시 원소 이동이 없음
• 포인터를 이용하여 노드를 동적으로 생성하므로 기억장소를 미리 확보할 필요 없음
• 기억장소의 크기는 일정한 크기로 제한되어 있기 때문에 malloc() 함수를 사용하여 동적 기억장소를 무한히 할당하여 사용하지는 못함

함수 원형 - void *malloc(size_tsize);

• 동적 기억장소로 사용되는 힙(heap)으로부터 원하는 크기의 바이트를 할당 해주는 함수()
• 정상적으로 기억장소를 할당하는 경우에는 기억장소의 주소를 반환하고 비정상적인 경우에는 NULL을 반환함

int *pt;
pt = (int*) malloc(10); 
pt = (int*) malloc(15*sizeof(int)); // 15개의 int를 위한 기억 장소를
                                    // 할당해 그 시작 주소값을 반환함

동적 기억장소의 해제

동적 기억장소의 해제 함수 - free()

함수 원형 - void free(void*)

• 할당된 기억장소를 해제하여 힙(heap)에 반환함()

동적 기억장소의 할당과 해제의 구현

malloc()와 free()함수를 사용한 프로그램

#include <stdio.h>
#include <stdlib.h>
void main(){
    int* memory;
    memory = (int*)malloc(sizeof(int)*5); //할당된 기억공간의 주소 값을 저장
    memory[0] = 10;
    memory[1] = 20;
    memory[2] = 30;
    memory[3] = 40;
    memory[4] = 50;
    int i = 0;
    for (i = 0; i < 5; i++)
        printf("memory[%d] : %d\n", i, memory[i]);
    free(memory);
}

실행결과

memory[0] : 10
memory[1] : 20
memory[2] : 30
memory[3] : 40
memory[4] : 50

자유 공간리스트(free space list)

사용하기 전의 메모리나 사용이 끝난 메모리를 관리하기 위해 노드로 구성하여 연결한 리스트(리스트가 다 소모되어 없을 때는 malloc()을 사용)를 말함

자유 공간리스트를 사용하기 위해서는 자유 공간리스트로부터 새로운 공백 노드를 할당받고, 그 메모리 주소에 대한 참조값을 반환하는 getNode() 함수가 필요하다.

노드의 할당과 반환 알고리즘

getNode(){ //노드의 할당
    if (free == NULL) underflow; //언더플로우 처리
    new = free; //ⓐ
    free = free->link; //ⓑ
    return new; //ⓒ
}

returnNode() { //노드의 반환
    old->link = free; //ⓐ
    free = old; //ⓑ
}

단일 연결리스트(singly linked list)

연결리스트 자료구조의 종류

연결의 표현 방법에 의해 분류

• 단일 연결리스트
• 환형 연결리스트
• 이중 연결리스트
• 이중 환형 연결리스트

단일 연결리스트의 구조

노드가 하나의 연결 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결리스트를 의미함

• 노드 구조 - 데이터 필드와 1개의 연결 필드로 구성됨
• 자료 탐색은 한 방향으로만 진행

노드의 구현

구조체의 멤버 접근 연산자 프로그램

#include <stdio.h>
#include <stdlib.h>
struct list_node{//구조체 정의
    int i;
    struct list_node *link;
};

int main(){
    struct list_node node1; //구조체 변수 선언 - 메모리가 할당됨
    struct list_node *node2=malloc
    (sizeof(struct list_node)); //구조체
                                //포인터에 메모리 할당
    struct list_node *node3=malloc(sizeof(struct list_node));

    node1.i=100;
    node2->i=200;
    node2->link=&node1;
    node3->link=&node1;

    printf("node1의 i값 = %d\n", node1.i); 
    printf("node1의 주소값= %0x\n", &node1); 
    printf("node2의 주소값= %0x\n", &node2); 
    printf("node2의 i값 = %d\n", node2->i); //주소를 통해 그 값에 접근하는 것을
    // 역참조(dereference)라함
    printf("node2의 i값 = %d\n", (*node2).i); //node2->i와 같음
    printf("node3의 link값= %0x\n", (*node3).link);
    return 0;
}

실행결과

node1의 i값 = 100
node1의 주소값= 62fe00
node2의 주소값= 62fdf8
node2의 i값 = 200
node2의 i값 = 200
node3의 link값= 62fe00

단일 연결리스트의 노드 탐색

노드의 삽입/삭제 시 특정 노드를 찾고자 할 때 리스트의 노드를 처음부터 하나식 순회하면서 노드의 데이터 필드 값과 x(찾고자 하는 노드)를 비교하여 일치하는 노드를 찾을 필요가 있음

노드의 생성과 출력 구현

단일 연결리스트의 생성과 노드들의 출력 프로그램

#include <stdio.h>
#include <stdlib.h>
struct node{
    int num; //데이터 영역
    struct node *nextptr; //연결 영역
}*stnode;

void createNodeList(int n){ //연결리스트의 생성
    struct node *fnNode, *tmp;
    int num, i;
    stnode = (struct node*)malloc(sizeof(struct node));
    if(stnode == NULL){ //stnode가 NULL인지 검사
        printf("메모리가 할당될 수 없음.");
    }
    else{ //노드의 데이터 입력
        printf("1번째 노드의 데이터 입력:");
        scanf("%d",&num);
        stnode->num = num;
        stnode->nextptr = NULL;//연결을 NULL로 할당
        tmp = stnode;
        for(i=2; i<=n; i++){ //n개의 노드를 생성하여 리스트에 추가
            fnNode = (struct node*)malloc(sizeof(struct node));
            if(fnNode == NULL){//새로운 공간을 할당
                printf("메모리가 할당될 수 없음.");
                break;
            }
            else{
                printf("%d n번째 노드의 데이터 입력:",i);
                scanf("%d", &num);
                fnNode->num = num;
                fnNode->nextptr = NULL;
                tmp->nextptr = fnNode;
                tmp = tmp->nextptr;
            }
        }
    }
}

void displayList(){
    struct node *tmp;
    if(stnode == NULL){
        printf("리스트가 비었음.");
    }
    else{
        tmp = stnode;
        while(tmp != NULL){
            printf("데이터 = %d\n", tmp->num); //현재 노드의 데이터 출력
            tmp = tmp->nextptr; //현재 노드의 위치를 다음 노드로 변경
        }
    }
}

int main(){
    int n;
    printf("\n\단일 연결리스트 생성/출력\n");
    printf("------------------------\n");
    printf("노드의 수를 입력:");
    scanf("%d",&n);
    createNodeList(n);
    printf("\n리스트의 데이터를 출력:\n");
    displayList();
    return 0;
}

실행결과

단일 연결리스트 생성/출력
------------------------------
노드의 수를 입력: 3 
1번째 노드의 데이터 입력: 10 
2번째 노드의 데이터 입력: 20 
3번째 노드의 데이터 입력: 30
리스트의 데이터를 출력:
데이터 = 10
데이터 = 20
데이터 = 30

노드의 삽입/삭제 구현

단일 연결리스트의 삽입/삭제 프로그램

#include <stdio.h>
#include <stdlib.h>

struct Node{//노드의 생성
    int item;
    struct Node* next;
}

void insertAtBeginning(struct Node** ref, int data){// 리스트 처음에 삽입
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->item = data;//데이터 삽입
    new_node->next = (*ref);
    (*ref) = new_node;//새로운 노드를 헤드로 연결
}

void insertAfter(struct Node* node, int data){//중간에 삽입
    if(node == NULL){
        printf("이전의 노드는 NULL이 될 수 없음.");
        return;
    }

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->item = data;
    new_node->next = node->next;
    node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data){//마지막에 삽입
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *ref;
    new_node->item = data;
    new_node->next = NULL;
    if(*ref == NULL){
        *ref = new_node;
        return;
    }
    while(last->next != NULL)//마지막 원소까지 이동
        last = last->next;
    last->next = new_node;
    return;
}

void deleteNode(struct Node** ref, int key){//노드의 삭제
    struct Node *temp = *ref, *prev;
    if(temp != NULL && temp->item == key){
        *ref = temp->next;
        free(temp);
        return;
    }
    while(temp != NULL && temp->item != key){//삭제될 원소를 찾음
        prev = temp;
        temp = temp->next;
    }
    if(temp == NULL) return; //찾는 데이터가 없으면
    prev->next = temp->next; // 해당 노드를 삭제
    free(temp);
}

void printList(struct Node* node){//노드 출력
    while (node != NULL){
        printf(" %d ", node->item);
        node = node->next; 
    }
}

int main(){
   struct Node* head = NULL;
    insertAtEnd(&head, 1);
    insertAtBeginning(&head, 2); insertAtBeginning(&head, 3);
    insertAtEnd(&head, 4); insertAfter(head->next, 5);
    printf("연결리스트: ");
    printList(head);
    printf("\n삭제 이후의 연결리스트: ");
    deleteNode(&head, 4);
    printList(head); 
}

실행결과

연결리스트: 3 2 5 1 4
삭제 이후의 연결리스트: 3 2 5 1