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

학교의 자료 구조 수업을 들으면서 연결리스트라는 개념에 대해 배웠다.

처음에는 list나 vector와 같은 자료구조에 대해 어떤 알고리즘으로 이루어져있는지, 구현은 어떻게 하면 될 지에 대해 생각해 본 적이 없었는데, 수업을 듣다보니 호기심도 생기고, 구현 방법이 신기해서 재미있었던것같다.

 

연결리스트란?

 - 추상적 자료형인 배열을 구현한 자료구조이며, 데이터를 값과, 주소로 나누어 저장하는 구조를 말한다. 이 때 주소는 다음 노드의 주소를 가리키며, 이렇게 구현한 배열은 각 노드가 한 줄로 길게 연결되어있는 모양새를 가지게 된다.

아래의 그림은 노드 한 개의 모양과 연결리스트의 전체적인 모양을 나타낸 것이다.

연결리스트의 모양새

연결리스트와 일반 배열의 특징

배열

• 인덱스를 이용해서 주소에 직접 접근해서 속도가 빠르다. 
• 크기가 고정되어있어, 크기보다 작은 데이터를 넣으면 데이터를 낭비하게 된다.
• 메모리의 주소가 이어져 있어야 하므로, 배열의 크기가 크면 할당 받지 못하는 상황이 생긴다.
• 중간에 데이터를 삽입, 삭제하는 과정이 복잡하다.
  ( ex.중간에 데이터를 넣으면 데이터를 한 인덱스 씩 뒤로 밀어주어야한다.)

연결리스트

• 중간에 데이터를 삽입, 삭제하는 과정이 간편하다.
  ( ex.노드를 생성해 준 후 주소의 값만 변경해주면 된다.)
• 데이터에 접근하는 시간이 오래걸린다.
  (배열은 메모리가 인접해있어, 주소값을 계산해 접근이 가능하지만 연결리스트는 순차적으로 접근한다.)
• 주소값을 집어넣기 위한 메모리 공간이 추가로 필요하다.
• 배열의 크기가 길어도, 노드 하나 하나를 저장할 메모리만 있으면 되기 때문에, 메모리를 할당 받지 못하는 상황이 적다.

이제 C언어를 이용해 연결리스트를 구현해보자(공부 열심히 했는데 시험엔 안나와서 슬펐다.)

간단하게 추가, 삭제, 삽입, 크기확인, 전체출력, 데이터 1개 출력하는 기능들을 구현해 보았다.

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

typedef int Element; //데이터 별명
typedef struct NODE { //노드 생성
    Element data;
    struct NODE* link; //노드의 주소값을 저장 (*구조체의 자기참조)
} node;

node* head = NULL; //배열의 헤드 선언

void Add(Element e) { //배열 맨 뒤에 데이터 추가하는 함수
    if (head == NULL) { //배열에 처음 데이터를 집어 넣을 때
        head = (node*)malloc(sizeof(node));
        if (head != NULL) {
            head->data = e;
            head->link = NULL;
        }
    }
    else { //이미 배열 안에 데이터가 있을 때
        node* curr = head; //배열의 끝을 찾을 순회 노드 선언
        while (curr->link != NULL) { //배열의 끝을 찾음
            curr = curr->link;
        }
        curr->link = (node*)malloc(sizeof(node));
        if (curr->link != NULL) { //메모리 할당에 성공
            curr = curr->link;
            curr->data = e;
            curr->link = NULL;
        }
    }
}

Element deleteList(int index) { //배열 내 데이터 삭제
    if (head != NULL) { //배열이 비어있지 않을 경우
        node* curr = head; //배열 순회 노드 생성

        for (int i = 1; i < index; i++) { //삭제할 노드의 이전 노드에 접근
            curr = curr->link;
        }
        node* delFront = curr; //주소를 저장하기위해 따로 노드 저장
        curr = curr->link; //삭제할 노드로 이동
        node* delNode = curr; //삭제하기 전에 다음 이전 노드와 다음 노드를 잇기위해 따로 노드 저장
        curr = curr->link; //삭제할 노드 다음 노드로 이동
        free(delNode); //입력받은 인덱스의 노드 삭제
        delFront->link = curr; //삭제한 노드의 이전 노드와 다음 노드를 연결
    }
}

void insertList(Element data, int index) { //배열 중간에 데이터 삽입 함수
    node* curr = head; //배열 순회 노드
    node* insertNode = (node*)malloc(sizeof(node)); //새로 삽입 할 노드 할당

    if (insertNode != NULL) { //메모리 할당에 성공 했을 경우
        insertNode->data = data;

        for (int i = 1; i < index; i++) { //삽입해야 할 위치로 이동
            curr = curr->link;
        }

        node* insertFront = curr; //삽입 해야 할 위치의 이전 노드 저장
        curr = curr->link;
        insertNode->link = curr; //삽입 할 노드 내에 다음 노드주소 지정
        insertFront->link = insertNode; //이전 노드 내에 삽입한 노드 주소 지정
    }
}

int sizeList() { //배열의 크기 구하는 함수
    node* curr = head; //배열 순회 노드 생성
    int cnt = 0;

    while (curr != NULL) { //배열의 끝까지 순회
        cnt++; //노드의 개수 ++
        curr = curr->link;
    }

    return cnt;
}

void printListAll() { //배열 전체 출력 함수
    node* curr = head; //배열 순회 노드 생성

    while (curr != NULL) { //배열의 끝까지 순회
        printf("%d ", curr->data); //노드의 데이터 출력
        curr = curr->link;
    }
}

Element printOne(int index) { //원하는 인덱스의 데이터 출력 함수
    node* curr = head; //배열 순회 노드 생성

    for (int i = 0; i < index; i++) {
        curr = curr->link;
    }

    return curr->data;
}

int main() {

    Add(1);
    Add(2);
    Add(3);
    Add(4);
    Add(5);
    printListAll();
    printf("\nsize = %d \n",sizeList());
    printf("printOne(2) = %d\n\n", printOne(2));

    insertList(10, 2);
    printf("insertList(10,2) = ");
    printListAll();
    printf("\nsize = %d \n", sizeList());

    printf("\n");
    deleteList(2);
    printf("deleteList(2) = ");
    printListAll();
    printf("\nsize = %d \n", sizeList());

    return 0;
}

실행 결과