[자료구조] 연결 리스트(Linked List) 실습 (feat. 연결 리스트)

연결 리스트의 기본 원리

"필요할 때마다 구조체 변수를 하나씩 *동적 할당해서 이들을 연결"

*동적 할당 : malloc(메모리의 동적 할당) 함수를 사용

연결 리스트의 개념이 궁금하다면?

[자료구조] 연결 리스트(Linked List)

 

✔️ 노드(Node) 구조

노드는 데이터를 담는 데이터 필드(Data)와 다음 노드를 가리키는 링크(Link)로 구성되어 있다.

 

 

연결 리스트 소스 코드

---

📌LinkedList.c

//출처 : 윤성우의 열혈 자료구조
//LinkedList.c
#include<stdio.h>
#include<stdlib.h>

typedef struct LinkedListNode {
    int data;
    struct LinkedListNode *next;
} Node;

int main(void)
{
    Node * head = NULL;
    Node * tail = NULL;
    Node * cur = NULL;
    
    Node * newNode = NULL;
    int readData;
    
    /* 데이터를 입력 받는 과정 */
    while(1)
    {
    	printf("자연수 입력: ");
        scanf("%d", &readData);
        if(readData < 1)
        	break;
           
        //노드의 추가과정
        newNode = (Node*)malloc(sizeof(Node));
        newNode->data = readData;
        newNode->next = NULL;
        
        if(head == NULL)
        	head = newNode;
        else
        	tail->next = newNode;
        
        tail = newNode;
    }
    printf("\n");
    
    /* 입력 받은 데이터의 출력 과정 */
    printf("입력 받은 데이터의 전체출력! \n");
    if(head == NULL)
    {
    	printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else
    {
    	cur = head;
        printf("%d ", cur->data);	//첫 번째 데이터 출력
        
        while(cur->next != NULL)	//두 번째 이후의 데이터 출력
        {
            cur = cur->next;
            printf("%d ", cur->data);
        }
    }
    printf("\n\n");
    
    /* 메모리의 해제과정 */
    if(head == NULL)
    {
    	return 0;	//해제할 노드가 존재하지 않는다.
    }
    else
    {
    	Node * delNode = head;
        Node * delNextNode = head->next;
        
        printf("%d을(를) 삭제합니다. \n", head->data);
        free(delNode);		//첫 번째 노드 삭제
        
        while(delNextNode != NULL)	//두 번째 이후 노드 삭제
        {
            delNode = delNextNode;
            delNextNode = delNextNode->next;
            
            printf("%d을(를) 삭제합니다. \n", delNode->data);
            free(delNode);
        }
    }
    
    return 0;
}

 

데이터 삽입

---

📌구조체 변수 만들기

typedef struct LinkedListNode {
    int data;				//실제 데이터가 저장된 멤버 변수
    struct LinkedListNode *next;	//다음 연결 정보(링크)를 나타내는 멤버 변수
} Node;					//Node라는 이름의 구조체 변수

먼저 노드의 역할을 하는 구조체 변수를 만들어준다.

※data : 구조체 멤버 data는 실제 데이터가 저장되는 공간이다. (입력한 값이 여기에 저장 됨)

※next : 구조체 멤버 next는 Node형 구조체 변수의 주소 값을 저장할 수 있는 포인터 변수이다. (다음 노드를 가리킴)

구조체 변수 Node의 생김새(?)

 

📌포인터 변수 선언

Node * head = NULL;
Node * tail = NULL;
Node * cur = NULL;

연결 리스트에서 주요한 역할을 하는 포인터 변수들을 선언한다.

연결 리스트의 초기 상태

 

📌리스트 생성

newNode = (Node*)malloc(sizeof(Node));	//노드의 생성
newNode->data = readData;		//노드에 데이터 저장
newNode->next = NULL;			//노드의 next를 NULL로 초기화

readData에 사용자가 입력한 값이 2라고 가정하면 위의 세 문장을 실행한 결과는 아래와 같다.

⭐편의상 NULL은 사선으로 표기하겠습니다!

2값을 가진 노드 생성

 

📌head → 첫 번째 노드를 가리키게 함

if(head == NULL)		//첫 번쨰 노드라면!
	head = newNode;		//첫 번째 노드를 head가 가리키게 함
else
	tail->next = newNode;

head의 첫 번째 값은 NULL이니 위의 구문이 실행된다! 따라서 아래 그림과 같이 head가 첫 번째 노드를 가리키게 된다.

※헤더 노드(Header Node) : 실제 데이터를 저장하는 것이 아닌 노드를 연결하기 위해 사용하는 더미(dummy) 노드

 

📌tail → 마지막 노드를 가리키게 함

tail = newNode;		//노드의 끝을 tail이 가리키게 함

tail은 리스트의 꼬리를 나타낸다. 현재는 값이 2밖에 없어서 2를 가리키지만 값이 추가 될 때마다 마지막 노드를 가리키게 된다.

 

📌노드의 추가

while(1)
{
    //일부 생략
    newNode = (Node*)malloc(sizeof(Node));
    newNode->data = readData;
    newNode->next = NULL;
    
    if(head == NULL)
    	head = newNode;
    else
    	//tail은 항상 새로 생성되는 노드를 가리킨다.
    	tail->next = newNode;

	tail = newNode;
}

이제 노드의 값이 추가될 때마다 head는 첫 번째 노드를, tail은 마지막 노드를 가리킨다.

readData에 2, 4, 6, 8이라는 값을 입력했다고 하면 결과는 아래처럼 나올 것이다.

 

 

 

데이터 조회

---

if(head == NULL)
{
	printf("저장된 자연수가 존재하지 않습니다. \n");
}
else
{
    cur = head;				//cur이 리스트의 첫 번째 노드를 가리킨다.
    printf("%d", cur->data);		//첫 번째 데이터 출력
    
    while(cur->next != NULL)		//연결된 노드가 존재한다면
    {
    	cur = cur->next;		//cur이 다음 노드를 가리키게 한다.
        printf("%d ", cur->data);	//cur이 가리키는 노드를 출력한다.
    }
}

 

📌 첫 번째 데이터 조회

cur = head;

연결 리스트에 2, 4, 6, 8이 저장된 상태라고 가정하고 else 구문에 다음 문장이 실행되면 cur은 2가 저장된 연결리스트의 첫 번째 노드를 가리키게 된다.

 

📌 다음 데이터 출력

cur = cur->next;

반복문에서 위의 문장을 통해 cur은 아래 사진처럼 모든 노드를 가리키며 이동하게 된다.

 

 

 

데이터 삭제

---

if(head == NULL)
{
	return 0;	//삭제할 노드가 존재하지 않는다.
}
else
{
	Node * delNode = head;
    Node * delNextNode = head->next;
    
    printf("%d을(를) 삭제합니다. \n", head->data);
    free(delNode);		//첫 번째 노드 삭제
    
    while(delNextNode != NULL)	//두 번째 노드 삭제
    {
    	delNode = delNextNode;
        delNextNode = delNextNode->next;
        
        printf("%d을(를) 삭제합니다. \n", delNode->data);
        free(delNode);
	}
}

 

📌 첫 번째 데이터 삭제

Node * delNode = head;
Node * delNextNode = head->next;

head가 가리키는 노드의 삭제를 위해서 두 개의 포인터 변수를 추가로 선언했다.

delNode(dN) / delNextNode(dNN)

 

delNode(dN)은 head가 가리키는 노드를 삭제하고 delNextNode(dNN)은 삭제될 노드가 가리키는 다음 노드의 주소 값을 저장한다. (head가 가리키는 노드를 그냥 삭제해버리면, 그 다음 노드에 접근이 불가능하다.)

위 그림처럼 4가 저장된 노드의 주소 값을 아는 것은 2가 저장된 노드가 유일한데, 이 노드를 그냥 삭제하면 4가 저장된 노드의 주소 값은 어디에도 존재하지 않게 된다. 즉, 4가 저장된 노드는 이제 어떠한 방법을 통해서도 접근이 불가능하다. 그래서 삭제될 노드가 가리키는 다음 노드의 주소 값을 별도로 저장하는 것이다. (delNextNode를 선언한 이유)

 

free(delNode);	//첫 번째 노드 삭제

해당 문장이 실행되면 첫 번째 노드가 소멸되어 다음의 상태가 된다.

delNode(dN)가 가리키는 첫 번째 노드가 삭제된다.

 

📌 다음 데이터 삭제

delNode = delNextNode;
delNextNode = delNextNode->next;

free 함수호출 이후(첫 번째 노드 삭제 후) 반복문 내에서 위의 두 문장을 실행한다.

포인터 변수 delNode(dN)와 delNextNode(dNN)가 가리키는 대상이 한 칸씩 오른쪽으로 이동되고 반복문 끝에 free 함수의 호출을 통해 delNode가 가리키는 대상을 소멸하여 위의 사진과 같이 되는 것이다.

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788996094067 

윤성우의 열혈 자료구조 - 교보문고