[c / c++ ] 단순 연결 리스트 ( Singly Linked List )

안녕하세요 ! 우디입니다.🚀

오늘은 단순 연결 리스트 (Singly Linked List)에 대해 알아봅시다 !

---

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

하나의 방향으로만 연결된 리스트 이다 .

 

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

하나의 노드는 데이터 필드 ( data field ) + 링크 필드 ( link field ) 로 구성되 있다.

 

헤드 포인터 ( head pointer )

첫번째 노드를 가르키는 포인터를 말한다.

연결리스트에 접근하기 위해 헤드 포인터 즉, 첫번째 노드를 가르키는 포인터 값만 알면 리스트 안의 모드 노드에 접근이 가능하다.

 

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

구조체를 이용해 데이터 필드와 링크 필드를 만들어 준다.

여기서 주의해야 할 건 링크 필드는 다음 노드의 주소가 들어가기 때문에 구조체 포인터를 사용한다.

xxxxxxxxxx
typedef int element; // 나중에 형변환 할때 유용하다
typedef struct ListNode{
    element data;          //데이터 필드
    struct ListNode *link; //링크 필드
}ListNode;

 

삽입

x
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node);

• phead : 헤드 포인터 (head) 에 대한 포인터 ( 여기에 head의 주소가 담긴다. )

• p : 삽입될 위치의 선행노드를 가르키는 포인터 ( p 노드 다음에 삽입된다 . )
• new_node : 새로운 노드를 가르키는 포인터

 

1. head 가 NULL 인 경우

: head가 NULL 이라면 현재 삽입하려는 노드가 첫번째 노드가 된다. 따라서 head 값만 변경하면 된다.

 

2. p가 NULL 인 경우

: new_node 를 리스트의 맨 앞에 삽입한다.

 

3. head 와 p 가 NULL 이 아닌 경우

: 가장 일반적인 경우이다.

 

< Total >

xxxxxxxxxx
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
    if(*phead == NULL)
    {
        new_node->link = NULL;
        *phead = new_node;
    }
    else if(p == NULL)
    {
        new_node->link = *phead;
        *phead = new_node;
    }
    else
    {
        new_node->link = p->link;
        p->link = new_node;
    }
}

 

삭제

x
void remove_node(ListNode **phead, ListNode *p, ListNode *removed);

• phead : 헤드 포인터 (head) 에 대한 포인터 ( 여기에 head의 주소가 담긴다. )

• p : 삭제될 위치의 선행노드를 가르키는 포인터 ( p 노드 다음에 삭제된다 . )
• removed : 삭제될 노드를 가르키는 포인터 ( ❗❗ 노드를 동적할당 받았으면 반드시 삭제할 노드는 연결리스트 변경 후 메모리 해제시켜주기❗❗ )

 

1. p 가 NULL 인 경우

: 연결리스트의 첫번째 노드를 삭제한다.

 

2. p가 NULL 인 경우

: 가장 일반적인 경우

 

< Total >

x
void remove_node(ListNode **phead, ListNode *p, ListNode *removed);
{
    if(p == NULL)
        *phead = *phead->link;
    else
        p->link = removed->link;
    free(removed);//노드 삭제할 때 노드를 동적할당으로 받았으면 반드시 메모리 해제 !
                  //메모리 해제를 안해주면 메모리 누수가 생김 !
}

 

역순

xxxxxxxxxx
ListNode *reverse_node(ListNode *head)
{
    ListNode *r,*q,*p;//r이 q를 q가 p를 따라감
    p = head;
    q = NULL;
    while(p!=NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;//q의 link를 전의 r의 노드로 바꿔줌 (역순 생성)
    }
    return q;//p가 아닌 이유는 p가 while문 안에서 NULL로 되고 빠져나오기 때문에
             //q를 return 해준다. ( 역순이니 q가 head가 되는 거다.)
}

 

탐색

x
ListNode *search_node(ListNode *head , int x )//x는 찾고자 하는 데이터
{
    ListNode *p = head;//굳이 또 해주는 이유는 head를 이용하면 head값이 변경됨.
    while(p!=NULL)
    {
        if(p->data == x) return(p);
        p=p->link;
    }
    return (p);//NULL
}

 

출력

x
void display_node(ListNode *head)
{
    ListNode *p = head;
    while(p!=NULL)
    {
        printf("%d -> ",p->data);
        p=p->link;
    }
}

 

---

노드 동적 생성 , 삽입, 삭제 , 초기화 , 역순 , 탐색 , 출력

#define _CRT_SECURE_NO_WARNINGS  // strcpy 컴파일 에러 방지
#include <stdio.h>
#include <string.h>
​
typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
}ListNode;
​
ListNode *create_node(element data, ListNode *link)
{
    ListNode *new_node;
    new_node = (ListNode *)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->link = link;
​
    return new_node;
}//노드 동적 생성
​
void init_node(ListNode **phead)
{
    *phead = NULL;
}//초기화
​
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
    if (*phead == NULL)
    {
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL)
    {
        new_node->link = *phead;
        *phead = new_node;
    }
    else
    {
        new_node->link = p->link;
        p->link = new_node;
    }
}
​
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
    if (p== NULL)
    {
        *phead = (*phead)->link;
    }
    else
    {
        p->link = removed->link;
    }
    free(removed);
}
​
void display_node(ListNode *head)
{
    ListNode *p;
    p = head;
    while (p != NULL)
    {
        printf("%d -> ", p->data);
        p = p->link;
    }
    printf("\n");
}
​
ListNode *search_node(ListNode *head, int x)
{
    ListNode *p = head;
    while (p != NULL)
    {
        if (p->data == x) return p;
        p = p->link;
    }
    return p;
}
​
ListNode *reverse(ListNode *head)
{
    ListNode *p, *q, *r;
    p = head;
    q = NULL;
    r = NULL;
    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    return q;
}
​
int main()
{
    ListNode *head = NULL;
    insert_node(&head, NULL, create_node(10, NULL));
    insert_node(&head, NULL, create_node(20, NULL));
    insert_node(&head, NULL, create_node(30, NULL));
    display_node(head);//30->20->10
    
    init_node(&head);
​
    display_node(head);//NULL
​
    insert_node(&head, NULL, create_node(10, NULL));
    insert_node(&head, NULL, create_node(20, NULL));
    insert_node(&head, NULL, create_node(30, NULL));
    remove_node(&head, search_node(head, 30), search_node(head, 20));
​
    display_node(head);//30->10
    
    head=reverse(head);
    display_node(head);//10->30
}
​
​