[자료구조] 단순 연결 리스트(singly linked list), 이중 연결리스트(double linked list) - 컴도리돌이

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

 

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

-하나의 링크 필드를 이용하여 연결

-마지막 노드의 링크 값은 NULL

 

연결 리스트로 구현한 리스트 (삽입, 삭제 연산 예시 && 코드)

 

 

연결 리스트로 구현한 리스트 - 구조체, 헤드 포인터

 

 

 

연결 리스트 구조체는 int형 data와 포인터 링크로 구성되어 있으며 전역 변수로 포인터 head가 NULL값으로 설정해 놓습니다. 전역 변수를 포인터 head을 사용할 경우 삽입 삭제할 때 전 노드를 찾아야 할 경우가 있기 때문에 get_entry 함수로 따로 만들어놔야 합니다. 굳이 만들지 않고 삽입 삭제 안에서 설정해놓아도 되는데 코드 길이가 길어지기 때문에 함수를 임의로 만들어 놓았습니다.

 

 

연결리스트로 구현한 리스트 - 삽입 예시

연결리스트로 구현한 리스트 - 삽입 c언어 코드

 

삽입 연산에서는 prev와 new_node라는 두 개의 포인터 변수를 설정하여, new_node는 현재 삽입할 값을 가진 노드이고 prev는 삽입할 연산의 전 노드를 가리키는 포인터 변수입니다.

만약 삽입할 pos가 0일 경우 new_node를 head와 간단히 연결시키면 되고 만약 그렇지 않을 경우 prev 노드의 위치를 처음에 언급한 get_entry 함수로 찾아야 합니다. 찾고 나서 prev가 null 값이 아닐 경우 insert_next 함수로 prev와 new_node를 입력받아 새로운 노드의 링크를 prev 링크로 연결시키고 prev 링크를 새로운 노드로 설정하면 삽입 연산은 끝이 납니다.

 

 

연결리스트로 구현한 리스트 - 삭제 예시

연결리스트로 구현한 리스트 - 삭제 c언어 코드

 

삭제 연산에서는 삽입 연산과 마찬가지로 prev와 삭제할 노드 removed를 포인터 변수로 설정하여 , 만약 pos이고 리스트가 비워있지 않을 경우  헤드 위치에 있는 노드를 삭제하는 것이기 때문에 헤드를 헤드 링크로 설정해놓고 , 아닐 경우 prev의 위치를 get_entry로 찾고 나서 prev가 NULL값이 아닐 경우 removed_next 함수에 넣어서 prev의 링크를  prev의 링크의 링크로 걸어 놓고 removed를 free 시켜 놓으면 값이 삭제가 되면서 연산이 끝이 납니다.

 

---

전역변수 head 포인터를 사용하지 않을 경우 - c언어

*전역 변수를 head포인터를 사용하지 않고 org라는 전역 변수를 사용할 경우입니다.*

---

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

#define Element int
typedef struct LinkedNode
{
    Element data;
    struct LinkedNode* link;
}Node;

Node org;

void insert_next(Node *prev, Node *n)
{
    if(n !=NULL)
    {
        n->link = prev->link;
        prev->link = n;
    }
}

Node * remove_next(Node *prev)
{
    Node* removed = prev->link;
    if(removed !=NULL)
        prev->link = removed->link;
    return removed;
}

void init_list() {org.link = NULL;}
Node* get_head() {return org.link;}
int is_empty() {return get_head() == NULL;}

Node* get_elem(int pos)
{
    Node* n = &org;
    int i = -1;
    for(i= -1;i<pos; i++,n = n->link)
        if(n == NULL)break;
    return n;
}

Node* find(Element val)
{
    Node*p;
    for(p=get_head();p!=NULL;p=p->link)
        if(p->data==val)return p;
    return NULL;
}

int size()
{
    Node* p;
    int count = 0;
    for(p=get_head();p !=NULL;p=p->link)
        count++;
    return count;
}

void replace(int pos,Element val)
{
    Node* node = get_elem(pos);
    if(node != NULL)
        node->data = val;
}

void insert(int pos,Element val)
{
    Node* new_node;
    Node* prev= get_elem(pos-1);
    if(prev != NULL)
    {
        new_node = (Node*)malloc(sizeof(Node));
        new_node->data = val;
        new_node->link = NULL;
        insert_next(prev,new_node);
    }
}

void delete(int pos)
{
    Node* prev= get_elem(pos-1);
    Node* removed = remove_next(prev);
    free(removed);
}

void clear_list()
{
    while(is_empty() == 0)
        delete(0);
}
void print_list(char* msg)
{
    Node* p;
    printf("%s[%d}: ",msg,size());
    for(p=get_head();p!=NULL;p=p->link)
        printf("%2d ", p->data);
    printf("\n");
}

이중 연결 리스트(double linked list) 

 

이중 연결리스트 - 구조 예시

 

이중 연결 리스트 - 구조

 

 

 

이중 연결 리스트는 구조체 안에 data 값과 prev와 next를 가리키는 구조체 포인터로 설정하고, 요번에는 전역 변수를 org라는 포인터 구조체가 아닌 일반 변수로 설정하였습니다. 

 

 

 

 

이중 연결리스트 - 삽입 예시

이중 연결리스트 - 삽입 c언어 코드

 

삽입할 경우 prev와 new_node를 포인터 구조체로 설정하여 prev를 get_entry함수로 찾습니다. 그리고 새로운 노드의 값을 설정하고 prev와 next를 NULL값으로 설정합니다. insert_next에는 prev와 새로운 노드를 받아와서 새로운 노드의 prev를 prev로 설정하고 새로운 노드의 next를 prev의 next로 설정합니다. 만약 prev 노드의 next가 NULL값이 아닐 경우 prev의 next의 prev를 새로운 노드로 설정하고 prev의 next를 새로운 노드로 설정하면 삽입 연산이 마무리가 됩니다.

 

삽입 예시 그림 번호를 보면서 이해하시는 게 도움이 될 거예요!

 

이중 연결리스트 - 삭제 예시

이중 연결리스트 - 삭제 c언어 코드

 

삭제 연산은 삭제할 노드의 위치만 확인하면 됩니다. 삭제할 노드를 확인할 경우 remove_curr 함수에 들어가서 삭제할 노드의 prev의 next를 삭제할 노드의 next로 설정하고 삭제할 노드의 next의 prev를 삭제할 노드의 prev로 설정하면 삭제 연산은 비교적으로 쉽게 마무리가 됩니다!!

 

삭제 연산도 그림 예시를 보면서 이해하시는 게 도움이 될 거예요

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

typedef int Element;
typedef struct DLinkedNode
{
    Element data;
    struct DLinkedNode* prev;
    struct DLinkedNode* next;
}Node;

Node org;

void init_list(){ org.next = NULL;}
Node* get_head() {return org.next;}
int is_empty() {return get_head() == NULL;}

Node* get_entry(int pos)
{
    Node* n = &org;
    int i = -1;
    for(i = -1; i<pos; i++,n=n->next)
        if(n==NULL) break;
    return n;
}
void replace(int pos,Element val)
{
    Node* node = get_entry(pos);
    if(node != NULL)
        node->data = val;
}
int size()
{
    Node* p;
    int count= 0;
    for(p = get_head();p !=NULL; p = p->next)
        count++;
    return count;
}

Node* find(Element val)
{
    Node* p;
    for(p=get_head(); p != NULL; p= p->next)
        if(p->data == val) return p;
    return NULL;
}

void print_list(char* msg)
{
    Node* p;
    printf("%s[%d}: ",msg,size());
    for(p=get_head();p!=NULL;p=p->next)
        printf("%2d ", p->data);
    printf("\n");
}

void insert_next(Node* before,Node* n)
{
    n->prev = before;
    n->next = before->next;
    if(before->next != NULL) before->next->prev = n;
    before->next = n;
}

void insert(int pos,Element val)
{
    Node* new_node,*prev;

    prev = get_entry(pos-1);
    if(prev !=NULL)
    {
        new_node = (Node*)malloc(sizeof(Node));
        new_node->data = val;
        new_node->prev = NULL;
        new_node->next = NULL;

        insert_next(prev,new_node);
    }
}

void remove_curr(Node *n)
{
    if(n->prev !=NULL) n->prev->next = n->next;
    if(n->next !=NULL) n->next->prev = n->prev;
}

void delete(int pos)
{
    Node* n = get_entry(pos);
    if(n != NULL)
        remove_curr(n);
}

void clear_list()
{
    while(is_empty() == 0)
        delete(0);
}