[1주차 TIL] KnockOn Bootcamp Pre.Rev : 연결리스트

연결리스트란

연결리스트

추상적 자료형인 리스트를 구현한 자료구조로서, 메모리에 저장될 때 데이터와 그 다음 데이터의 주소를 가리키는 포인터를 가진 노드가 서로 연결되어 있는 리스트이다.

배열 VS 연결리스트

구분	배열	연결리스트
메모리구조	연속적	비연속적
삽입 / 삭제	높음 위치탐색 : O(n)	낮음 위치 탐색 : O(n) 삭제 : O(1) 노드 연결 끊음
접근속도	빠름 O(1) 연속된 메모리, 인덱스를 활용하여 접근	느림 O(n)
메모리 효율	추가 공간 필요 없음.	포인터 메모리 추가 필요
특징	고정크기, 빠른 접근	가변크기, 잦은 삽입, 삭제

단일연결리스트

단일 연결리스트는 데이터와 다음 노드를 가리키는 포인터만 존재한다.

이중연결리스트

이중연결리스트는 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 연결리스트로서, 양방향으로 검색이 되고 순회가 가능해진다는 특징이 있다.

원형연결리스트

원형 연결리스트는 마지막 노드가 첫번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결리스트이다.

실습

이번 실습 간에는 헤더파일을 이용하여 이중연결리스트와 원형연결리스트를 C언어로 구현했다.

내용은 주요한 부분에 대해서만 설명하겠다.

이중연결리스트

main.c

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextLink = NULL;   // 이중연결리스트이고, 최초 head는 다음 포인터 지정을 안한 NULL 상태
    appendNode(head, 11);    // appendNode : 리스트 맨 마지막에 추가
    appendNode(head, 22);
    appendNode(head, 33);
    appendNode(head, 44);
    appendNode(head, 55);
    printList(head);
    insertNode(head, 66, 2); // insertNode : 리스트 중간에 추가
    printList(head);
    deleteNode(head, 4);     // 원하는 index의 리스트 삭제
    printList(head);
    return 0;
}

link_list.h

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

typedef struct NODE {       // 이중연결리스트는 preLink-data-nextLink로 구성
    struct NODE* preLink;   // 이전 노드를 가리키는 주소
    int data;               // 데이터
    struct NODE* nextLink;  // 다음 노드를 가리키는 주소
} Node;

void insertNode(Node* head, int data, int idx) {
    Node* preNode = head;   // preNode라는 head와 동일한 주소를 가리키는 노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    for (int i = 0; i < idx; i++) {      // idx값은 새 노드를 넣기 위한 index를 의미
        if (preNode->nextLink == NULL) { // 현재노드의 nextLink가 NULL이면 메모리 반납
            free(newNode);
            return;
        }
        preNode = preNode->nextLink;  // NULL이 아닐경우 index-1까지 이동
    }
    newNode->preLink = preNode;      // 새 노드의 preLink는 현 노드를 넣기
    newNode->nextLink = preNode->nextLink; // 새 노드의 다음 노드 주소에는 현 노드의 nextLink
    preNode->nextLink = newNode; // 현 노드의 nextLink에는 새 노드 주소
}

void appendNode(Node* head, int data) { // 리스트 제일 마지막에 넣는 함수
    while (head->nextLink != NULL) {
        head = head->nextLink;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->preLink = head;
    newNode->nextLink = NULL;  // 새 노드의 다음 주소는 NULL
    newNode->data = data;
    head->nextLink = newNode;
}

void deleteNode(Node* head, int idx) {
    Node* temp = head;
    Node* target = NULL;
    for (int i = 0; i < idx; i++) { // 원하는 idx의 -1까지 temp 이동
        temp = temp->nextLink;
    }
    target = temp->nextLink;       // temp의 다음 주소, 즉 삭제하려는 index의 주소 설정
    temp->nextLink = target->nextLink;  // 삭제하려는 노드 다음 주소를 temp의 다음주소로 바꿈
    if (target->nextLink != NULL) {     // target의 다음주소가 NULL이 아니면
        target->nextLink->preLink = temp; // target의 다음 주소 즉, temp->nextLink의 preLink를 temp로 설정
    }
    free(target);
}

void printList(Node* head) {
    int idx = 0;
    Node* node;
    node = head->nextLink;
    while (node != NULL) {
        printf("%d %d \n", idx, node->data);
        printf("pre: %p, node: %p, next: %p \n", node->preLink, node,node->nextLink);
        node = node->nextLink;
        idx++;
    }
    printf("\n");
}

결과

원형연결리스트

main.c

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

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextLink = head;      // 원형 연결리스트는 초기 head의 다음노드를 자기 자신으로 가리킴
    appendNode(head, 11);
    printList(head);
    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;
}

circle_list.h

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

typedef struct NODE {
    int data;
    struct NODE* nextLink;
} 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++) {
        if (preNode->nextLink == head) {  // 중간에 노드를 넣는데 다음 노드가 head 이면 리스트 끝이기 때문에 free해서 메모리 반납
            free(newNode);
            return;
        }
        preNode = preNode->nextLink;
    }
    newNode->nextLink = preNode->nextLink;
    preNode->nextLink = newNode;
}

void appendNode(Node* head, int data) {
    Node* temp = head;
    while (temp->nextLink != head) {
        temp = temp->nextLink;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->nextLink = head;  // 새 노드의 다음 노드는 없으므로 head를 가리켜야 함
    newNode->data = data;
    temp->nextLink = newNode;
}

void deleteNode(Node* head, int idx) { // idx에 해당하는 노드를 삭제
    Node* temp = head;
    Node* target = NULL;
    for (int i = 0; i < idx; i++) {
        temp = temp->nextLink;
    }
    target = temp->nextLink;            // target은 temp의 다음 노드(idx-1까지 수행되었음)
    temp->nextLink = target->nextLink;  // 삭제하려는 노드 다음 주소를 temp의 다음주소로 바꿈
    free(target);
}

void printList(Node* head) {
    int idx = 0;
    Node* node = head->nextLink;

    do {
        printf("Index: %d, Data: %d\n", idx, node->data);
        printf("Node: %p, Next: %p\n", (void*)node, (void*)node->nextLink);
        node = node->nextLink;
        idx++;
    } while (node != head);   // node가 head가 아닐때 즉, 리스트가 head 제외 1개 이상일 때 출력
    printf("\n");
}

결과

끝.