[1주차 TIL] KnockOn Bootcamp 연결 리스트

💡 연결 리스트란?

일반적으로 사용하는 배열과 다르게 동적으로 각 칸(노드)들이 포인터를 통해 앞뒤로 사슬처럼 연결되어 있는 구조이다.

 

1차원 배열

 

연결리스트

배열 vs 연결리스트

항목	배열	연결 리스트
메모리 구조	연속적인 메모리 공간 사용	비연속적인 메모리 공간 포인터로 연결
메모리 할당	고정 크기(컴파일 또는 실행 시 결정)	동적 크기(필요할 때마다 malloc 가능)
삽입 / 삭제 속도	느림 (요소 이동 필요)	빠름 (포인터 변경만 하면 됨)
접근 속도	빠름 인덱스를 통해 접근 O(1)	느림 처음부터 순차적으로 접근 O(n)
메모리 효율성	메모리 낭비 가능 (미리 크게 할당 시)	필요한만큼 할당 (하지만 포인터 공간이 추가됨)
구현 난이도	쉬움	어려움 (구조체와 포인터를 활용)
용도	크기가 고정된 데이터 처리에 적합	데이터의 삽입과 삭제가 빈번한 경우 적합

 

🔎 연결 리스트의 구조

노드(Node)

위 그림과 같이 연결리스트의 각 노드는 두 부분으로 구성이 된다.

• 데이터 필드(Data Field) : 실제 데이터를 저장하는 부분
• 링크 필드(Link Field)  : 다음 노드의 주소를 저장하는 부분(포인터)

메모리에 연속적으로 저장되어 있는 배열과는 달리 각 노드들은 메모리의 아무 곳에나 존재할 수 있으며 노드의 주소가 연결된 순서와 동일하지 않을 수 있다.

마지막 노드의 링크 필드에는 NULL 값을 저장함으로써 마지막 노드라는 것을 표현한다.

🔎 연결 리스트 종류

단일 연결 리스트(Singly Linked List)

각 노드가 다음 노드만을 가리키고 있는 한 방향으로만 연결된 형태이다.

 

특징

• 구현이 간단하다.
• 앞에서부터만 탐색이 가능하다.
• 뒤에서 앞으로 갈 수 없다.

단일 연결 리스트

 

이중 연결 리스트(Doubly Linked List)

각 노드가 이전 노드와 다음 노드를 가리키고 있는 양방향으로 연결된 형태이다.

 

특징

• 양쪽으로 이동이 가능하다.
• 삭제나 삽입 시 유리하다.
• 포인터 관리가 조금 더 복잡하다.

이중 연결 리스트

 

원형 연결 리스트(Circular Linked List)

마지막 노드가 첫 번째 노드를 가리키고 있는 순환 구조로 연결된 형태이다.

다른 형태와 달리 순환 구조로 되어있어 끝이 없다는 특징이 있다.

 

특징

• 어떤 노드에서 시작해도 전체 리스트를 순회할 수 있다.
• 큐(Queue) 구현 시 자주 사용된다.

원형 연결 리스트

---

🎯 연결 리스트 구현 해보기

단일 연결 리스트

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

typedef struct Node
{
    int data;    // 데이터 필드
    struct Node* nextNode;    // 다음 노드 포인터
} Node;

// 노드 중간 삽입
void insertNode(Node* head, int data, int idx)
{
    Node* preNode = head;    // 현재 연결 리스트의 첫 노드
    Node* newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    newNode->data = data;    // 새 노드의 데이터 필드에 데이터 저장

    for(int i = 0; i < idx; i++)    // 삽입하려는 위치의 앞 노드까지 for문 실행
    {
        if(preNode->nextNode == NULL)    // 만약 삽입하려는 위치가 연결 리스트를 벗어날 경우 error
        {
            free(newNode);    // 새 노드 메모리 해제
            return;    // error
        }
        
        preNode = preNode->nextNode;    // 다음 노드로 이동
    }
    
    newNode->nextNode = preNode->nextNode;    // 새 노드의 링크 필드에 삽입하는 위치의 뒷 노드의 주소 저장
    preNode->nextNode = newNode;    // 삽입하는 위치의 앞 노드의 링크 필드에 새 노드 주소 저장
}

// 끝 부분에 노드 추가
void appendNode(Node* head, int data)
{
    while(head->nextNode != NULL)    // 연결 리스트의 마지막 노드까지 while문 실행
    {
        // 현재 노드가 마지막 노드가 아닐 경우 다음 노드로 이동
        head = head->nextNode;
    }
    
    Node* newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    head->nextNode = newNode;   // 현재 노드의 링크 필드에 새 노드의 주소 저장
    newNode->data = data;       // 새 노드의 데이터 필드에 데이터 저장
    newNode->nextNode = NULL;   // 새 노드의 링크 필드에 NULL을 저장하여 마지막 노드임을 표시
}

// 노드 삭제
void deleteNode(Node* head, int idx)
{
    Node* temp = head;    // 현재 연결 리스트의 첫 노드
    Node* target = NULL;  // 삭제할 노드를 임시 저장할 변수 선언
    
    for(int i = 0; i < idx; i++)    // 삭제할 노드의 앞 노드까지 for문 실행
    {
        temp = temp->nextNode;      // 삭제할 노드가 아닌 경우 다음 노드로 이동
    }
    
    target = temp->nextNode;    // 삭제할 노드의 정보 임시 저장
    temp->nextNode = target->nextNode;    // 삭제할 노드의 앞 노드에 삭제할 노드의 뒷 노드의 주소를 저장
    free(target);    // 노드 메모리 해제
}

// 모든 노드의 데이터 필드를 콘솔에 출력
void printList(Node* head)
{
    int idx = 0;
    Node* node;    // 노드를 담을 변수
    node = head->nextNode;    // 현재 연결 리스트의 헤드 노드의 다음 노드
    
    while(node != NULL)    // 연결 리스트의 마지막 노드까지 while문 실행
    {
        printf("%d %d\n", idx, node->data);    // 노드 데이터 콘솔 출력
        node = node->nextNode;    // 다음 노드로 이동
        idx++;
    }
    
    printf("\n");
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextNode = NULL;
    
    appendNode(head, 11);
    appendNode(head, 22);
    appendNode(head, 33);
    appendNode(head, 44);
    appendNode(head, 55);
    
    printList(head);

    insertNode(head, 66, 2);
    printList(head);

    deleteNode(head, 4);
    printList(head);
    
    return 0;
}

 

이중 연결 리스트

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

typedef struct Node
{
    struct Node* preNode;	// 이전 노드 포인터
    int data;	// 데이터 필드
    struct Node* nextNode;	// 다음 노드 포인터
} Node;

// 노드 중간 삽입
void insertNode(Node* head, int data, int idx)
{
    Node* preNode = head;	// 현재 연결 리스트의 첫 노드
    Node* afterNode = NULL;  // 삽입하려는 위치의 뒷 노드를 저장할 변수;
    Node* newNode = (Node*)malloc(sizeof(Node));	// 새 노드 생성
    newNode->data = data;	// 새 노드의 데이터 필드에 데이터 저장

    for(int i = 0; i < idx; i++)	// 삽입하려는 위치의 앞 노드까지 for문 실행
    {
        if(preNode->nextNode == NULL)	// 만약 삽입하려는 위치가 연결 리스트를 벗어날 경우 error
        {
            free(newNode);	// 새 노드 메모리 해제
            return; // error
        }
        
        preNode = preNode->nextNode;	// 다음 노드로 이동
    }
    
    afterNode = preNode->nextNode;   // 삽입하려는 위치의 뒷 노드 저장
    
    newNode->preNode = preNode;     // 새 노드의 이전 노드 포인터에 삽입하는 위치의 앞 노드의 주소 저장
    newNode->nextNode = afterNode;	// 새 노드의 다음 노드 포인터에 삽입하는 위치의 뒷 노드의 주소 저장
    preNode->nextNode = newNode;	// 삽입하는 위치의 앞 노드의 다음 노드 포인터에 새 노드 주소 저장
    afterNode->preNode = newNode;    // 삽입하는 위치의 뒷 노드의 이전 노드 포인터에 새 노드 주소 저장
}

// 끝 부분에 노드 추가
void appendNode(Node* head, int data)
{
    while(head->nextNode != NULL)	// 연결 리스트의 마지막 노드까지 while문 실행
    {
        // 현재 노드가 마지막 노드가 아닐 경우 다음 노드로 이동
        head = head->nextNode;
    }
    
    Node* newNode = (Node*)malloc(sizeof(Node));	// 새 노드 생성
    head->nextNode = newNode;	// 현재 노드의 링크 필드에 새 노드의 주소 저장
    newNode->data = data;		// 새 노드의 데이터 필드에 데이터 저장
    newNode->preNode = head;	// 새 노드의 이전 노드 포인터에 현재 노드 저장
    newNode->nextNode = NULL;	// 새 노드의 다음 노드 포인터에 NULL을 저장하여 마지막 노드임을 표시
}

// 노드 삭제
void deleteNode(Node* head, int idx)
{
    Node* tempPre = head;	  // 현재 연결 리스트의 첫 노드
    Node* tempNext = NULL;
    Node* target = NULL;  // 삭제할 노드를 임시 저장할 변수 선언
    
    for(int i = 0; i < idx; i++)	// 삭제할 노드의 앞 노드까지 for문 실행
    {
        tempPre = tempPre->nextNode;		// 삭제할 노드가 아닌 경우 다음 노드로 이동
    }
    
    target = tempPre->nextNode;    // 삭제할 노드의 정보 임시 저장
    tempNext = target->nextNode;   // 삭제할 노드의 뒷 노드
    tempPre->nextNode = target->nextNode;	// 삭제할 노드의 앞 노드에 삭제할 노드의 뒷 노드의 주소를 저장
    tempNext->preNode = tempPre;      // 삭제할 노드의 뒷 노드에 삭제할 노드의 앞 노드의 주소를 저장
    free(target);	// 노드 메모리 해제
}

// 모든 노드의 데이터 필드를 순방향, 역방향으로 콘솔에 출력
void printList(Node* head)
{
    int idx = 0;
    Node* node;	// 노드를 담을 변수
    node = head->nextNode;	// 현재 연결 리스트의 헤드 노드의 다음 노드
    
    // 순방향 출력
    while(node != NULL)
    {
        printf("%d %d\n", idx, node->data);	// 노드 데이터 콘솔 출력
        
        if(node->nextNode == NULL)    // 다음 노드 없을 경우 while문 종료
        {
            break;
        }
        
        node = node->nextNode;
        idx++;
    }
    
    printf("\n");
    
    // 역방향 출력
    while(node != NULL)	// 연결 리스트의 첫 노드까지 while문 실행
    {
        printf("%d %d\n", idx, node->data);	// 노드 데이터 콘솔 출력
        
        if(node->preNode == head)    // 첫 노드일 경우 경우 while문 종료
        {
            break;
        }
        
        node = node->preNode;
        idx--;
    }
    
    printf("\n");
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->preNode = NULL;
    head->nextNode = NULL;
    
    appendNode(head, 11);
    appendNode(head, 22);
    appendNode(head, 33);
    appendNode(head, 44);
    appendNode(head, 55);
    
    printList(head);

    insertNode(head, 66, 2);
    printList(head);

    deleteNode(head, 4);
    printList(head);
    
    return 0;
}

 

원형 연결 리스트

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

typedef struct Node
{
    int data;    // 데이터 필드
    struct Node* nextNode;    // 다음 노드 포인터
} Node;

// 노드 중간 삽입
void insertNode(Node* head, int data, int idx)
{
    Node* preNode = head;    // 현재 연결 리스트의 첫 노드
    Node* newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    newNode->data = data;    // 새 노드의 데이터 필드에 데이터 저장

    for(int i = 0; i < idx; i++)    // 삽입하려는 위치의 앞 노드까지 for문 실행
    {
        if(preNode->nextNode == head)    // 만약 삽입하려는 위치가 연결 리스트를 순회하고 다시 처음으로 돌아가는 경우
        {
            free(newNode);    // 새 노드 메모리 해제
            return;    // error
        }
        
        preNode = preNode->nextNode;    // 다음 노드로 이동
    }
    
    newNode->nextNode = preNode->nextNode;    // 새 노드의 링크 필드에 삽입하는 위치의 뒷 노드의 주소 저장
    preNode->nextNode = newNode;    // 삽입하는 위치의 앞 노드의 링크 필드에 새 노드 주소 저장
}

// 끝 부분에 노드 추가
void appendNode(Node* head, int data)
{
    Node* headNode = head;	// 헤더 노드 저장
    
    while(head->nextNode != headNode)    // 연결 리스트의 마지막 노드까지 while문 실행
    {
        // 현재 노드가 마지막 노드가 아닐 경우 다음 노드로 이동
        head = head->nextNode;
    }
    
    Node* newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    head->nextNode = newNode;   // 현재 노드의 링크 필드에 새 노드의 주소 저장
    newNode->data = data;       // 새 노드의 데이터 필드에 데이터 저장
    newNode->nextNode = headNode;   // 새 노드의 링크 필드에 헤더 노드 포인터 저장
}

// 노드 삭제
void deleteNode(Node* head, int idx)
{
    Node* temp = head;    // 현재 연결 리스트의 첫 노드
    Node* target = NULL;  // 삭제할 노드를 임시 저장할 변수 선언
    
    for(int i = 0; i < idx; i++)    // 삭제할 노드의 앞 노드까지 for문 실행
    {
        temp = temp->nextNode;      // 삭제할 노드가 아닌 경우 다음 노드로 이동
    }
    
    target = temp->nextNode;    // 삭제할 노드의 정보 임시 저장
    temp->nextNode = target->nextNode;    // 삭제할 노드의 앞 노드에 삭제할 노드의 뒷 노드의 주소를 저장
    free(target);    // 노드 메모리 해제
}

// 모든 노드의 데이터 필드를 콘솔에 출력
void printList(Node* head)
{
    int idx = 0;
    int loop = 0;
    Node* node = head;    // 헤더 노드부터 순회 시작
    Node* headNode = head;    // 순회를 체크하기 위해 헤더 노드 저장
    
    while(1)    // 연결 리스트를 3번 순회하면서 출력(순회 가능한 구조임을 확인)
    {
    	if(node == headNode)    // headNode일 경우 다음 루프를 위해 초기화
        {
            if(loop < 3)
            {
                loop++;
                idx = 0;
                printf("\nloop: %d\n", loop);
                node = node->nextNode;
            
                continue;
            }
            else
            {
                break;
            }
        }
    
        printf("%d %d\n", idx, node->data);    // 노드 데이터 콘솔 출력
        node = node->nextNode;    // 다음 노드로 이동
        idx++;
    }
    
    printf("\n");
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextNode = head;	// 현재 헤드 노드 하나뿐이므로 자기 자신을 가리킴
    
    appendNode(head, 11);
    appendNode(head, 22);
    appendNode(head, 33);
    appendNode(head, 44);
    appendNode(head, 55);
    
    printList(head);

    insertNode(head, 66, 2);
    printList(head);

    deleteNode(head, 4);
    printList(head);
    
    return 0;
}