Fascination
article thumbnail
Published 2021. 9. 7. 22:28
[DS] Linked List (연결 리스트) 와 Linked List Operator ( 연결 리스트 연산자) Study/Data Structure

1. 연결 리스트

# 연결 리스트와 배열의 비교

- 리스트: 동일한 자료형으로 된 원소(item)들의 모임으로 선형 리스트(linear list)와 연결 리스트(linked list)로 나뉨

  > 선형 리스트: 배열로 구현되는 순서 리스트(ordered list)로 원소들이 메모리에 연속적으로 저장되며 인덱스로 접근

     * 배열 원소의 개수는 선언 시점 이후에는 변경할 수 없음 → 크기를 잘못 예측하지 않도록 주의해야 함

     * 배열은 시스템에 의해 메모리 상에서 관리됨

  > 연결 리스트: 원소들이 프로그램 실행 중에 동적으로 생성되거나 삭제되므로 리스트의 크기를 미리 예측할 필요 X

                      원소들은 링크(link)를 통해 서로 연결되어 있음

                      논리적으로는 선형적이지만 물리적으로는 분산되어 있음

     * 동적 메모리 관리(dynamic memory management):

                                         연결 리스트는 사용자가 직접 연결 리스트의 노드를 실행 중에 관리해 주어야 함

 

 

# 연결 리스트의 표현

- node: 연결 리스트의 원소

> 구조체로 선언

> 자기 참조형 구조체: 링크 포인터가 자신과 동일한 구조체 자료형을 참조

- data 필드: 정보를 저장

- link 포인터 필드: 노드를 연결

 

 

# 연결 리스트의 생성

- 정적인 방식

  > 정적 메모리(static memory) 공간에 노드 객체를 생성하여 연결한 경우

  > 프로그램 실행 전에 노드를 위한 공간이 할당되고 실행 중에 할당은 이루어지지 않음

 

[코드]

#include <stdio.h>

typedef struct node_type * node_ptr; // node_ptr = struct node_type * 과 같은 의미
struct node_type{ // node 선언 -> 구조체
    int data;
    node_ptr link; // 구조체 포인터로 다음 node를 가리키며 자기와 같은 형식의 구조체를 가리키는 것
};

void main(){
    struct node_type node1, node2, node3; // 구조체 형식으로 세개의 노드 선언
    node1.data = 7;
    node2.data = 11;
    node3.data = 13;
    node1.link=&node2; // node 자체는 구조체이므로 &를 사용해 주소를 넘겨줌
    node2.link=&node3; // NULL 상수 값을 저장하여 마지막 노드임을 표시
    node3.link=NULL;
    printf("%d %d %d", node1.data, node2.data, node3.data);
}

 

[실행결과]

 

 

# 동적 메모리 할당

- 메모리 공간

정적 메모리 공간 명령어 코드, 변수
동적 메모리 공간 (힙 메모리) 실행중에 사용 됨

- DMA(Dynamic memory allocation): 동적 메모리 관리

  > 아래의 함수를 사용하기 위해서는 stdlib.h 헤더 파일 필요

전용 함수 기능 사용 예
malloc() 요청된 크기의 힙 메모리 공간을 할당하고 그 시작 주소를 반환 ptr = (int *)malloc(sizeof((int));
free() 기존에 할당된 공간을 해제하여 힙 메모리에 반환 free(ptr);

  > malloc(): 공간 할당에 성공할 경우 메모리 주소가 반환되는데 형 변환(type casting)을

                 통하여 동일한 자료형의 포인터에 저장됨

  * 포인터의 역할: 할당된 공간에 대한 유일한 접근 수단

 

ptr = (int *)malloc(sizeof(int));

 

[코드]

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

void heap_test(){
    int *pi;
    float *pf;

    pi = (int *)malloc(sizeof(int)); // pi에 주소가 저장되고 공간 할당 시 4byte의 공간을 요청
    pf = (float*)malloc(sizeof(float));
    *pi = 1024; // 포인터로 접근
    *pf= 3.14;
    printf("%d, %f, %u\n",*pi,*pf,&pi);
    free(pi); // 할당된 공간을 해제하여 가용되게 함
    free(pf);
}

void main(){
    heap_test();
}

 

[실행결과]

 

 

 

 

- (int) pi: 1024가 저장된 공간의 주소를 가리키는 포인터 변수

- (int) pf: 3.14가 저장된 공간의 주소를 가리키는 포인터 변수

- 주소값 200을 가지는 공간: malloc 함수를 통해 생성되어 포인터 pi에 전달됨

- 주소값 210을 가지는 공간: malloc 함수를 통해 생성되어 포인터 pf에 전달됨

 

 

 

 

 

 

 

- 동적 메모리 할당으로 연결 리스트 생성

[코드]

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

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

void main(){
    node_ptr node1, node2, node3;
    node1 = (node_ptr)malloc(sizeof(struct node_type));
    node2 = (node_ptr)malloc(sizeof(struct node_type));
    node3 = (node_ptr)malloc(sizeof(struct node_type));

    node1->data=7;
    node2->data=11;
    node3->data=13;
    node1->link=node2;
    node2->link=node3;
    node3->link=NULL;

    printf("node1 : %d ", node1->data);
    printf("node2 : %d ", node2->data);
    printf("node3 : %d\n",node3->data);

    free(node1);
    free(node2);
    free(node3);
}

 

[실행결과]

 

  > 노드의 link pointer 필드에 NULL 상수 값을 저장하면 마지막 노드임을 확인할 수 있음

  > node1을 리스트 포인터라고 부르고 연결 리스트의 탐색 시작점이 됨

  > 연결 리스트 노드의 멤버에 접근할 때는 다음과 같이 화살표 연산자(arrow operator: ->)를 사용

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

  > 해제 없이 계속 할당하여 사용할 경우 힙 메모리 공간 부족 현상이 생길 수 있음

  > 연결 리스트의 노드들은 힙 메모리에 저장되어 있음

 

 

# 허상 참조

- malloc 함수에 의해 할당된 공간에 대한 포인터 변수: 공간에 접근할 수 있는 유일한 수단

- 이 포인터의 값이 변경된다면(다른 주소 값을 갖게 된다면) 이전에 갖고 있던 주소가 가리키는 공간에 대한 접근이 불가능해 짐

- 위와 같이 할당된 공간이 방치되는 상황을 허상 참조(dangling reference)라고 함

 

ptr1 = (int *)malloc(sizeof(int));
ptr2 = (int *)malloc(sizeof(int));
ptr1 = ptr2;

 

 

2.  단방향 연결리스트

# 단방향 연결 리스트

- 단방향 연결 리스트: 연결 리스트들의 노드들이 한쪽 방향으로만 연결된 경우

- 리스트 포인터: 첫 번째 노드를 참조하는 포인터로 이를 통하여 리스트 노드들을 탐색

- 선언

typedef struct list_node *list_ptr // struct list_node* 는 list_ptr과 같은 의미
struct list_node{
	char data[4];
    list_ptr link; // 자신과 같은 구조체 형식을 가리킴
};
list_ptr ptr = NULL;

 

- empty 리스트를 판별하는 매크로

#define IS_EMPTY (ptr) (!ptr) 
// ptr이 NULL이면 참이므로 isemty를 만족이고 NULL이 아니면 거짓이 되어 만족하지 않음

 

- node 초기화

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

 

# 연결 리스트의 노드 삽입

- 연결 리스트에 노드를 삽입하기 위해서는 리스트의 시작 포인터와 노드가 삽입될 위치를 포인터로 알려주어야 함

- 연결 리스트가 비어 있는 경우와 그렇지 않은 경우를 고려해야 함

- 힙 메모리는 유한하므로 molloc 함수로 새 노드 공간을 요청해도 가용 힙 메모리가 더 이상 없다면 주소 값 대신 NULL이 반환되므로 이 시점이 연결 리스트가 가득 찬 상태(full)에 도달함

연결 리스트에 노드 삽입 알고리즘
1. malloc 함수로 삽입할 노드를 생성하고 그 주소를 포인터 node에 할당
2. 생성된 노드의 data 필드에 값을 저장하고, link 필드에 NULL을 저장
3. 연결 리스트 포인터가 list라고 가정할 때,
 (1) 연결 리스트가 비어 있는 경우 (empty)
    - 삽입할 노드가 유일한 노드이므로 이 노드가 첫 노드가 되도록 리스트 포인터에 노드의 주소 값을 저장하고 종료
 (2) 연결 리스트가 비어 있지 않은 경우 (not empty) 다음 두 가지 경우로 다시 나누어 짐
   (2-1) 연결 리스트의 중간에 삽입되는 경우 (앞 노드가 있는 경우)
    - 앞 노드의 링크 필드(prev의 link) 값을 node의 link에 저장
    - 앞 노드의 링크 필드에 노드의 주소 값을 저장하고 종료
   (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 insert_node(node_ptr prev, int data);
void print_list(node_ptr list);

int main() {
    node_ptr node1, node2, node3;
    node1=(node_ptr)malloc(sizeof(struct node_type));
    node1->data=10;
    node1->link=NULL;
    list=node1;
    node2 = (node_ptr)malloc(sizeof(struct node_type));
    node2->data=20;
    node2->link=NULL;
    node1->link=node2;
    print_list(list);
    insert_node(node1,50);
    print_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){ // list가 null이 아니면
        printf("%d ",list->data);
        list = list->link;
    }
    printf("\n");
}

[실행결과]

 

 

# 연결 리스트의 노드 삭제

- 연결 리스트에서의 노드 삭제는 리스트에 노드가 존재하는 경우와 리스트가 비어있는 경우로 나누어 생각함

- 리스트에 노드가 존재하는 경우 삭제할 노드와 그 노드의 앞 노드를 함께 알려주어야 함

- 노드 삭제를 위해 링크 연결을 완료한 후 free 함수를 호출하여 메모리를 반환해야 함

연결 리스트의 노드 삭제 알고리즘
(1) 연결 리스트가 비어 있는 경우 (empty)
    - 그대로 종료함
(2) 연결 리스트에 노드가 존재하는 경우 (not empty)
  (2-1) 연결 리스트의 중간 노드를 삭제하는 경우
    - 삭제 노드의 앞 노드(prev)의 링크(link) 필드에 삭제할 노드(node)의 링크(link)를 저장
  (2-2) 연결 리스트의 맨 앞 노드를 삭제하는 경우
    - 연결 리스트 포인터(list)에 삭제할 노드(node)의 링크(link)를 저장함
(3) 노드를 삭제하고 종료

연결 리스트의 노드 삭제

 

[코드]

#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);

int main() {
    node_ptr node1, node2, node3;
    node1 = (node_ptr)malloc(sizeof(struct node_type));
    node1->data=10;
    node1->link=NULL;
    list=node1;
    node2 = (node_ptr)malloc(sizeof(struct node_type));
    node2->data = 50;
    node2->link=NULL;
    node1->link = node2;
    node3 = (node_ptr)malloc(sizeof(struct node_type));
    node3->data = 20;
    node3->link=NULL;
    node2->link = node3;
    print_list(list);
    delete_node(node1, node2);
    print_list(list);
    delete_node(0,node1);
    print_list(list);
}

void delete_node(node_ptr prev, node_ptr node){ // 앞 노드가 없을 경우 prev에 0넣기
    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 = list->link;
    }
    printf("\n");
}

 

[실행결과]

> 중간 노드 50이 삭제된 후 맨 앞 노드 10이 삭제된 것을 확인할 수 있음

 

 

3. 연결 리스트 연산자

# 연결 리스트의 길이 세기

- 연결 리스트의 길이는 노드의 수로 계산

- 단방향 연결 리스트의 길이 계산은 while문으로 할 수 있음

  1) while문에서 temp가 NULL이 아니면 count 변수 1 증가

  2) 링크를 따라 다음 노드로 이동

  3) temp 값이 NULL이 아닌 동안 1), 2) 과정을 반복

  4) 마지막 노드에서 tmep에 temp->link를 할당하면 NULL이 되어 while문을 빠져나오게 됨

 

[코드]

#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);

int 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 = 150;
   node2->link = NULL;
   node1->link = node2;
   node3 = (node_ptr)malloc(sizeof(struct node_type));
   node3->data = 150;
   node3->link = NULL;
   node2->link = node3;
   printf("list length is %d\n",length_list(list));
}

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

 

[실행결과]

 

 

# 리스트의 삭제

- 연결된 리스트 전체를 삭제하는 연산

 

[코드]

void deleteList(list_ptr *ptr){ // call by reference
	list_ptr temp;
    while(*ptr){ // ptr이 null이 아니면
    	temp = *ptr;
        *ptr = (*ptr)->link;
        free(temp);
    }
}

연결 리스트 전체 삭제

 

 

# 연결 리스트의 결합

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

- 시간 복잡도: O(n)

  > 첫 번째 리스트의 길이에 따라 결정되기 때문

연결 리스트의 결합 알고리즘
1. 첫 번째 리스트(list1)가 빈 리스트라면 두 번째 리스트(list2)를 그대로 반환하고 종료함
2. 첫 번째 리스트(list1)가 빈 리스트가 아니라면 두 번째 리스트(list2)가 빈 리스트인지 확인함
 (2-1) 두 번째 리스트(list2)가 빈 리스트라면 첫 번째 리스트(list1)를 그대로 반환하고 종료함
 (2-2) 두 번째 리스트(list2)가 빈 리스트가 아니라면 연결하기 위하여 첫 번째 리스트의
        마지막 노드를 탐색하고 마지막 노드의 링크 필드에 두 번째 리스트 포인터(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, node_ptr list2);
void print_list(node_ptr list);

int main(){
    node_ptr list, list1, list2, node1, node2;

    list1 = (node_ptr)malloc(sizeof(struct node_type));
    list1->data =100;
    list1->link = NULL;

    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 =100;
    list2->link = NULL;

    node2 = (node_ptr)malloc(sizeof(struct node_type));
    node2->data =150;
    node2->link = NULL;
    list2->link = node2;

    print_list(list1);
    print_list(list2);
    list = concat_list(list1,list2);
    print_list(list);
}

node_ptr concat_list(node_ptr list1, node_ptr list2){
    node_ptr temp;
    if(!list1) // list1이 비어있는 경우 --> list2만 return 
        return list2;
    else{
        if(list2){ // 두 리스트 모두 노드가 있는 경우
                   // list1과 list2가 둘 다 null이 아님
            temp = list1;
            while(temp->link) // 앞 리스트의 마지막 노드 찾기
                              // temp의 link가 null이 아니면 (list의 끝을 찾는 과정)
                temp= temp->link;
            temp->link = list2; // 위에서 찾은 list1의 마지막 노드와 list2의 첫노드를 연결
        }
        return list1;
    }
}

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

 

[실행결과]

 

 

# 순환 연결 리스트

- 체인(chain): 연결 리스트의 마지막 노드의 링크에는 NULL값이 들어 있어서 끝을 확인할 수 있는 리스트

- 순환 연결 리스트(circular linked list): 마지막 노드의 링크가 NULL이 아니고 그 리스트의 첫 노드에 다시 연결되어 있는 형태

- 순환 연결 리스트는 리스트의 시작 노드가 변경되어도 전체 노드들이 연결되어 있기 때문에 시작 노드 변경이 용이하다는 장점이 있음

순환 연결 리스트

 

 

# 순환 연결 리스트의 길이

- 링크가 NULL인 마지막 노드가 없기 때문에 시작 노드로 다시 되돌아올 때가 전체 노드를 모두 탐색한 시점

- list가 NULL이 아니면 move 포인터가 이 리스트를 참조하도록 함

- 첫 번째 노드가 이미 NULL이 아니므로 do-while문을 사용하는 것이 좋음

- move 포인터가 이동하면서 노드의 수를 세고 move 포인터가 리스트 포인터 위치에 도달할 경우 작업을 멈춤

 

[코드]

#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);

int main() {
   node_ptr list, node1, node2, node3;
   node1 = (node_ptr)malloc(sizeof(struct node_type));
   node1->data = 7;
   node1->link = NULL;
   list = node1;
   node2 = (node_ptr)malloc(sizeof(struct node_type));
   node2->data = 11;
   node2->link = NULL;
   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;
}

[실행결과]

 

 

# 리스트 재활용

- 재활용 리스트에 사용이 끝난 node를 저장하고 새로운 공간을 malloc 해야 할 때 다시 꺼내 사용

  > 빈번한 malloc() 또는 free() 함수의 호출이 프로그램 실행 시 부담이 될 수 있음

- get_node() 함수로 재활용할 list가 있는지 검사하고 있으면 리스트를 재활용함

  > 없다면 malloc() 함수로 새로 할당해야 함

 

- recycle_node()

list_ptr avail = NULL;

void recycle_node(list_ptr ptr){
	ptr->link = avail;
    avail = ptr;
}

recycle node / 재활용 노드

- get_node()

list_ptr get_node()
{
	list_ptr node;
	if (avail) { 
		node = avail;
		avail = avail->link ;
	}
	else { // avail이 NULL이면 재활용 할 노드가 없음
		node = (list_ptr) malloc (sizeof(list_node)); // 노드를 할당하여 반환
	}
	if (IS_FULL(node)) {
		printf("heap is full\n");
		exit(1);
	}
return node;

 

- recycle_circluar()

  > 리스트를 통째로 재활용

void recycle_circular(list_ptr *ptr){ // *ptr -> 재활용해야 할 대상
	if(*ptr){
    	list_ptr temp;
        temp = (*ptr)->link; // temp에 다음 node 저장
        (*ptr)->link = avail; // ptr에 재활용할 list의 시작 포인터 넘기기
        avail=temp;
        *ptr=NULL;
     }
}

 

 

# 역순 연결 리스트

- 리스트 노드의 연결 순서를 반대로 뒤집어서 리스트로 반환하는 연산

- 시간 복잡도: O(length) // 리스트의 길이(노드의 개수)에 비례 

역순 연결 리스트

알고리즘 연순 연결 리스트
1. 리스트가 비어 있거나 노드가 1개만 있는 경우 그대로 리스트 포인터(one)을 반환하고 종료
2. 리스트에 노드가 2개 이상인 경우 2개의 임시 포인터 변수(two, three)를 사용하여 연결 순서를 변환
  (2-1) 노드 포인터(three)가 노드 포인터(two)를 참조하게 함
  (2-2) 노드 포인터(two)가 노드 포인터(one)을 참조하게 함
  (2-3) 노드 포인터(one)를 다음 노드로 이동시킴
  (2-4) 노드 포인터(two)의 링크 필드에 노드 포인터(three) 값을 저장하여 두 노드를 연결 시킴
  (2-5) 노드 포인터(one)가 NULL이 아닐 때까지 (2-1)번 과정부터 반복

역순 연결리스트 만들기

 

[코드]

#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 one);
void print_list(node_ptr list);

int main() {
        node_ptr list, node1, node2, node3;
        node1 = (node_ptr)malloc(sizeof(struct node_type));
        node1->data = 7;
        node1->link = NULL;
        list = node1;
        node2 = (node_ptr)malloc(sizeof(struct node_type));
        node2->data = 11;
        node2->link = NULL;
        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;
    }
    printf("\n");
}

 

[실행결과]

저작자표시 비영리 변경금지

'Study > Data Structure' 카테고리의 다른 글

[DS] 자료구조 개념 및 구현 Chapter 5 연습문제  (0) 2021.09.02
[DS] A Maze Problem (스택으로 미로 문제 풀기)  (2) 2021.09.02
[DS] Deque (Double-ended-queue)  (0) 2021.09.02
[DS] Evaluation of expression (수식의 평가)  (0) 2021.09.02
[DS] Queue(큐) & Circular Queue(순환 큐)  (0) 2021.08.31
profile

Fascination

@euna-319

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그

RANK
문제풀이
리눅스
구조
Linux
눈송이
c++
해커
언어
호출
구현
DreamHack
공부
C
개념
hacker
data
데이터
백준
BOJ
개론
데사개
알고리즘
랭크
science
사이언스
자료
spring
문제
풀이

티스토리툴바