'노드' 태그의 글 목록

노드

[자료구조] 연결 리스트 2021.04.20

[자료구조] 연결 리스트

2021. 4. 20. 16:38

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. 순서 리스트

- 원소들을 순서에 따라 배열한 리스트이다.

- (ex) days of week, months of year, ...

- C언어의 경우 같은 자료형으로 이루어져 있다.

- Array 배열

- 선언한 뒤 원소의 개수를 바꿀 수 없다.

-따라서 크기를 잘 설정하지 않으면 공간이 부족하거나 메모리 낭비가 발생할 수 있다.

- 메모리에서 연속적으로 할당되며, 인덱스로 접근한다.

- 중간에 원소를 추가하거나 제거하기도 어렵다.

- Linked list 연결 리스트

- 메모리에 분산된 장소로 저장되어 있다.

- 즉, 노드들이 메모리에 흩어져 있지만, 포인터로 연결되기 때문에 순서는 존재한다.

- 크기 조절이 가능하다.

- 중간에 원소 변경도 가능하다.

- 하지만, 관리를 잘못했을 때 overhead 등 심각한 오류가 발생할 수 있다.

- 사용자가 직접 연결 리스트의 노드를 실행 중에 관리하는 것을 '동적 메모리 관리'라고 한다.

2. 연결 리스트

- 특징

- 원소들은 메모리 상에서 물리적으로 분산되어 있다.

- 논리적으로는 포인터로 연속적으로 연결되어 있다.

- 원소들은 필요할 때 생성될 수 있다.

- 표현

- 연결 리스트의 원소는 '노드'라고 부르며 구조체로 선언된다.

- 데이터 필드 : 정보를 저장한다. 데이터 필드를 추가함으로써 구조체를 확장할 수 있다.

- 링크 포인터 필드 : 노드와 다음 노드를 연결하는 연결 포인터이다.

- 연결 리스트의 노드는 자신과 동일한 구조체 자료형을 참조하기 때문에 자기 참조형 구조체라고도 부른다.

- ex

#include <stdio.h>

typedef struct node_type * note_ptr;

struct node_type
{
    int data;
    note_ptr link;
};

void main()
{
    struct node_type node1, node2, node3;
    node1.data = 7;
    node2.data = 11;
    node3.data = 13;
    node1.link = &node2;
    node2.link = &node3;
    node3.link = NULL;
    printf("%d %d %d", node1.data, node2.data, node3.data);
}

3개의 노드가 링크로 연결된 연결 리스트 예제이다.

노드는 node_type 구조체형으로 선언되고, 링크 포인터는 구조체에 대한 포인터이며 node_ptr로 선언된다.

이 연결 리스트는 정적 메모리 공간에 노드 객체를 생성하여 연결한 경우이다.

따라서 실행 중에는 노드를 위한 공간을 할당할 수 없다.

- 연결 리스트 노드의 멤버에 접근할 때에는 ' -> ' 화살표 연산자를 사용한다.

- node1 -> data

- 필요 없는 노드는 free함수를 통해 해제하고 힙 공간으로 반환하는 것이 좋다.

따라서 위의 코드는 다음과 같이 나타낼 수 있다.

//node1.data = 7;
node1 -> data = 7;

//node2.data = 11;
node2 -> data = 11;

//node1.link = &node2;
node1 -> link = node2;

//node2.link = &node3;
node2 -> link = node3;

printf("node1 : %d", node1 -> data);

주소	값	변수	메모리
100	1000	node1	정적 메모리

110	1300	node2

120	1200	node3

1000	7	data	동적 메모리
	1200	link
1200	13	data
	NULL	link
1300	11	data
	1200	link

- 자료형으로 선언된 변수인 node1, node2, node3 은 정적 공간에 할당된 반면, malloc 함수에 의해 생성된 연결 리스트 노드들은 힙 메모리에 저장되어 있다.

3. 동적 메모리 할당

- 정적 메모리 : 컴파일 할 때 메모리가 할당된다. 자료형이 있고, 선언되는 모든 변수가 정적 메모리를 가진다.

- 동적 메모리 : 실행될 때 메모리가 할당된다.

3-1. Operators

- malloc

- 지정된 크기의 메모리 할당을 요청한다.

- 할당된 장소의 주소를 반환한다.

- malloc으로 할당된 메모리 공간은 free() 를 선언하기 전까지 사라지지 않는다.

- free

- 할당된 메모리 공간을 해제하는 함수이다.

- 해제하지 않으면 메모리 고갈이 발생한다.

3-2. Example (dynamic memory == heap memory)

void heap_test()
{
    int *pi;
    float *pf;
    
    pi = (int *) malloc (sizeof(int));
    pf = (float *) malloc (sizeof(float));
    *pi = 1024;
    *pf = 3.14;
    
    printf("%d, %f, %u\n", *pi, *pf, &pi);
    free(pi);
    free(pf);
}

처음 *pi와 *pf는 정적 메모리 공간에 할당되었다.

pi = (int *) malloc (sizeof(int));
pf = (float *) malloc (sizeof(float));

이 두 문장으로 pi와 pf 에 각각 동적 메모리 공간을 가리키는 포인터를 할당하였다.

*pi = 1024;
*pf = 3.14;

이 두 문장은 각각의 포인터가 참조하는 공간에 해당하는 값을 저장하는 실행문이다.

따라서 메모리 공간이 아래와 같이 할당되었을 때, 프린트문을 실행하면 결과값은 다음과 같이 나온다.

1024, 3.14, 100

4. 단방향 연결 리스트

- 노드들이 한 방향으로만 연결된 경우를 단방향 연결 리스트라고 한다.

- 첫번째 노드를 참조하는 포인터를 '리스트 포인터'라고 한다.

- 이를 통해 리스트 노드들을 탐색한다.

- 노드 삽입

- malloc 함수로 삽입할 노드를 생성하고, 그 주소를 포인터 노드에 할당한다.

- 생성된 노드의 데이터 필드에 값을 저장하고, 링크 필드에 NULL을 저장한다.

- 연결 리스트 포인터가 list라고 가정할 때

1) 연결 리스트가 비어 있는 경우 (empty)

- 삽입할 노드가 유일한 노드이므로 이 노드가 첫 노드가 되도록 리스트 포인터(list)에 노드의 주소 값을 저장하고 종료한다.

2) 비어 있지 않은 경우

- 리스트 중간에 삽입되는 경우 (앞 노드가 있는 경우)

→ 앞 노드의 링크 필드 값을 노드의 링크에 저장한다.

→ 앞 노드의 링크 필드에 노드의 주소 값을 저장하고 종료한다.

- 리스트 맨 앞에 삽입되는 경우

→ 삽입할 노드의 링크 필드에 연결리스트 포인터 값 지정한다.

→ 연결리스트 포인터가 노드를 가리키도록하고 종료한다.

- malloc 함수로 새 공간을 요청해도 가용 힙 메모리가 더 이상 없다면 주소 값 대신 NULL 값이 반환된다.

- 선언

typedef struct list_node *list_ptr;
struct list_node {
    char data[4];
    list_ptr link;
};
list_ptr ptr = NULL;

- macro function for empty list

#define IS_EMPTY(ptr) (!ptr)

ptr이 NULL값이면 IS_EMPTY(ptr)은 1을 반환한다.

- 노드 초기화

ptr = (list_ptr) malloc (sizeof(struct list_node));
strcpy(ptr -> data, "com");
ptr -> link = NULL;

- 노드 삽입

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

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void insert_node(node_ptr prev, int data);
void print_list(node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    
    node1 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node1 -> data = 100;
    node1 -> link = NULL:
    list = node1;
    
    node2 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node2 -> data = 200;
    node2 -> link = NULL:
    list = node2;
    
    print_list(list);
    insert_node(node1, 150);
    printf_list(list);
}

void insert_node(node_ptr prev, int data)
{
    node_ptr node;
    node = (node_ptr) malloc (sizeof(struct node_type));
    if (!node) exit(1);
    node -> data = data;
    node -> link = NULL;
    
    if (!list) {
        list = node;
    }
    else if(prev) {
        node -> link = prev -> link;
        prev -> link = node;
    }
    else {
        node -> link = list;
        list = node;
    }
}

void print_list (node_ptr list) 
{
    while (list) {
        printf("%d ", list -> data);
        list = list -> link;
    }
    printf("\n");
         
}

- 노드 삭제

1) 리스트가 비어 있는 경우

- 그대로 종료한다.

2) 리스트에 노드가 존재하는 경우

2-1) 중간 노드 삭제

- 삭제 노드의 앞 노드의 링크 필드에 삭제할 노드의 링크를 저장한다.

2-2) 맨 앞 노드 삭제

- 리스트 포인터에 삭제할 노드의 링크를 저장한다.

- 노드를 삭제하고 종료한다.

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

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void delete_node (node_ptr prev, node_ptr node);
void print_list (node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    print_list(list);
    delete_node(node1, node2); // node1 : prev, node2 : delete
    print_list(list);
}

void delete_node(node_ptr prev, node_ptr node)
{
    if (prev) {
        prev -> link = node -> link;
    }
    else {
        list = node -> link;
    }
    free(node);
}

void print_list(node_ptr list)
{
    while(list) {
        printf("%d", list -> data);
        list = lsit -> link;
    }
    printf("\n");
}

5. 연결 리스트 연산자

5-1. 연결 리스트 길이

- 노드 수로 계산한다.

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

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int length_list(node_ptr list);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    printf("list lentgh is %d\n", length_list(list));
}

int lentgh_list (node_ptr list)
{
    int count = 0;
    node_ptr temp = list;
    while (temp)
    {
        count ++;
        temp = temp -> link;
    }
    return count;
}

5-2. 연결 리스트의 결합

- 두 개의 연결 리스트를 연결하여 하나로 합치는 것이다.

- 결합 연산은 앞 리스트의 노드 수에 비례하여 시간이 걸리므로, 시간복잡도는 O(첫번째 리스트의 길이) 가 된다.

- 첫 번째 리스트가 빈 리스트라면 두 번째 리스트를 그대로 반환하고 종료한다.

- 첫 번째 리스트가 빈 리스트가 아니라면 두 번째 리스트를 확인한다.

- 두 번째 리스트가 빈 리스트라면 첫 번째 리스트를 그대로 반환하고 종료한다.

- 두 번째 리스트가 빈 리스트가 아니라면 결합하기 위해 첫 번째 리스트의 마지막 노드를 탐색하고, 마지막 노드의 링크 필드에 두 번째 리스트 포인터(list2)를 저장한 후 첫 번째 리스트 포인터(list1)를 반환하고 종료한다.

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

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr concat_list(node_ptr list1, note_ptr list2);
void print_list(list1);

void main()
{
    node_ptr list1, list2, node1, node2;
    list1 = (node_ptr) malloc (sizeof(struct node_type));
    list1 -> data = 100;
    
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 150;
    node1 -> link = NULL;
    
    list1 -> link = node1;
    
    list2 = (node_ptr) malloc (sizeof(struct node_type));
    list2 -> data = 200;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 250;
    node2 -> link = NULL;
    
    list2 -> link = node2;
    
    print_list(list1);
    print_list(list2);
    list1 = concat_list(list1, list2);
    print_list(list1);
}

node_ptr concat_list (node_ptr list1, node_ptr list2)
{
    node_ptr temp;
    if (!list1)
        return list2;
    else {
        if (list2) {
            temp = list1;
            while (temp -> link)
                temp = temp -> link;
                
            temp -> link = list2;
        }
        return list1;
    }
}

void print_list(node_ptr list)
{
    while (list) {
        printf("%d", list -> data);
        list = list -> link;
    }
}

6. 순환 연결 리스트

- 연결 리스트의 마지막 노드의 링크가 NULL이 아니고, 그 리스트의 첫 노드에 다시 연결되어 있는 형태를 말한다.

- 시작 노드가 변경되어도 전체 노드들이 여전히 연결되어 있는 상태이기 때문에 시작 노드 변경이 용이하다.

- 순환 연결 리스트의 길이

- 시작노드로 다시 되돌아올 때가 전체 노드를 모두 탐색한 시점이다.

- do - while 문 사용

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

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int clist_length(node_ptr list);

void main() 
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 7;
    list = node1;
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = node1;
    
    printf("circular list length = %d", clist_length(list));
}

int clist_length(node_ptr list)
{
    node_ptr move;
    int num = 0;
    if (list) {
        move = list;
        do {
            num ++;
            move = move -> link;
        } while (move != list);
    }
    
    return num;
}

7. 역순 연결 리스트

- 리스트 노드의 연결 순서를 반대로 뒤집어서 리스트로 반환하는 형식이다.

- (ex) [7 - 11 - 13] → [13 - 11 - 7]

- 시간 복잡도는 리스트의 길이(노드의 개수)에 비례한다.

- 리스트가 비어있거나 노드가 1개만 있는 경우 그대로 리스트 포인터(one)를 반환하고 종료한다.

- 리스트에 노드가 2개 이상인 경우 2개의 임시 포인터 변수(two, three)를 더 사용하여 연결 순서를 변환한다.

- 노드 포인터(three)가 노드 포인터(two)를 참조하게 한다.

- 노드 포인터(two)가 노드 포인터(one)를 참조하게 한다.

- 노드 포인터(one)를 다음 노드로 이동시킨다.

- 노드 포인터(two)의 링크 필드에 노드 포인터(three) 값을 저장하여 두 노드를 연결 시킨다.

- 노드 포인터(one)가 NULL이 아닐 때까지 반복한다.

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

typedef struct node_type * node_ptr;
struct node_type 
{
    int data;
    node_ptr link;
};

node_ptr reverse_list(node_ptr);
void print_list(node_ptr);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 7;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = NULL;
    
    print_list(list);
    list = reverse_list(list);
    print_list(list);
}

node_ptr reverse_list(node_ptr one)
{
    node_ptr two, three;
    two = NULL;
    while (one) {
         three = two;
         two = one;
         one = one -> link;
         two -> link = three;
    }
    return two;
}

void print_list(node_ptr list)
{
    while(list) {
        printf(%d ", list -> data);
        list = list -> link;
    }
}

8. 양방향 연결 리스트

- 각 노드가 자신의 이전과 이후 노드에 대한 링크 포인터를 가지고 있다.

- 노드 삽입 또는 삭제 시 앞 노드를 추가로 알려줄 필요가 없기 때문에 편리하다.

- 대표적으로 이진 트리에 사용된다.

- node == node -> llink -> rlink == node -> rlink -> llink

- 단방향 연결 리스트와 달리 모든 노드의 링크 필드 값을 채워야 한다.

- 따라서 삭제할 수 없는 head 노드가 사용된다.

- 시작 노드의 llink 필드는 head 노드를 참조하도록 초기화된다.

// 양방향 연결 리스트의 선언

typedef struct node_type * node_ptr;
struct node_type 
{
    node_ptr llink;
    int data;
    node_ptr rlink;
};

- 노드 삽입

- 노드의 llink를 prev 노드로 연결한다.

- 노드의 rlink를 prev 다음 노드로 연결한다.

- prev 다음 노드의 llink가 노드를 참조하도록 연결한다.

- prev 노드의 rlink가 노드를 참조하도록 연결한다.

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

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void insert_dll (dll_node_ptr prev, dll_node_ptr node);
void print_dll_list (dll_node_ptr list1);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node2 -> rlink = head;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = NULL;
    node3 -> rlink = NULL;
    head -> llink = node2;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

- 노드 삭제

- head 노드는 삭제가 불가능하다.

- 일반 노드의 삭제일 경우 삭제할 노드의 이전 노드의 rlink에 삭제할 노드의 다음 노드 주소를 저장한다.

- 삭제할 노드의 다음 노드의 llink에 노드 이전 노드를 복사한다.

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

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void delete_dll (dll_node_ptr head, dll_node_ptr node);
void print_dll_list (dll_node_ptr head, dll_node_ptr list);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = node2;
    node3 -> rlink = head;
    node2 -> rlink = node3;
    head -> llink = node3;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

저작자표시 변경금지

'Software > Data Structures' 카테고리의 다른 글

[Python] 1. Introduction (0)	2022.03.08
[자료구조] 탐색 (0)	2021.04.20
[자료구조] 선형 자료구조 (0)	2021.04.18
[자료구조] 알고리즘 성능 분석 (0)	2021.04.17
[자료구조] Recursion 재귀 호출 (0)	2021.04.17

PREV 이전 1 NEXT 다음

gnuykob_sw

노드

[자료구조] 연결 리스트

1. 순서 리스트

2. 연결 리스트

3. 동적 메모리 할당

3-1. Operators

3-2. Example (dynamic memory == heap memory)

4. 단방향 연결 리스트

5. 연결 리스트 연산자

5-1. 연결 리스트 길이

5-2. 연결 리스트의 결합

6. 순환 연결 리스트

7. 역순 연결 리스트

8. 양방향 연결 리스트

'Software > Data Structures' 카테고리의 다른 글

+ Recent posts

티스토리툴바