[10] C review < 연결리스트의 개념 >

연결리스트 개념과 기본동작 

 

리스트

컴퓨터 프로그램은 대부분 리스트 

- 기본적인 연산 : 삽입(insert),삭제(remove),검색(search)등 

- 리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결 리스트 

 

배열은 랜덤엑세스가 가능한 자료구조다

랜덤엑세스 ? 

 배열은 각 칸의 타입이 같고 즉, 크기가 동일하다. 예를 들어 배열의 5번재 칸은 배열의 시작 주소 + 4*(1칸의 크기) n번째 칸에 대한 접근의 차이가 없다. > 랜덤엑세스 몇번째 칸이든 상관 없다.  >> 배열의 장점 

 

배열의 단점 

- 크기가 고정 - reallocation이 필요 

= 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야

 

연결리스트

- 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며,

- 길이의 제한이 없음 

- 랜덤 엑세스가 불가능 

 

 

배열과 연결리스트의 구조적 차이

연결리스트는 데이터와 다음 데이터의 주소를 묶어서 저장한다. 즉 105번지에 Monday와 2번째 데이터인 Tuesday의 주소값102가 묶여서 저장된 것을 알 수 있다. 

 

연결리스트의 삽입과 삭제.

각각의 노드는 필요한 데이터필드와 하나 혹은 그 이상의 링크필드로 구성된다. 

링크 필드는 다음 노드의 주소를 저장 

첫 번재 노드의 주소는 따로 저장해야 한다.

 

< 연결리스트의 생성 >

 

하나의 노드를 만들기 위한 구조체를 만들어야 한다. 

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

typedef struct node
{
    char *data;
    struct node *next;

} Node;

Node *head = NULL; // 연결리스트의 첫번째 노드의 주소를 저장할 포인터

int main()
{
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = "Tuesday";
    head->next = NULL;

    Node *q = (Node *)malloc(sizeof(Node));
    q->data = "Thursday";
    q->next = NULL;
    head->next = q;

    Node *k = (Node *)malloc(sizeof(Node));
    k->data = "Monday";
    k->next = head;
    head = k;

    Node *p = head;
    while (p != NULL)
    {
        printf("%s\n", p->data);
        p = p->next;
    }

    return 0;
}

 

코드의 흐름.