연결 리스트

 

연결 리스트 기본 구조

자료 + 링크(포인터)

 

연결리스트

동적 자료구조라고 불린다. 그러므로 크기를 정할 필요가 없다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않다.

 

배열과의 비교

장점: 배열의 크기가 고정되는 것에 반하여, 연결리스트는 자료의 특성에 따라서 유동적이다.

단점: 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 때문에 임의로 접근하는 것이 불가능 하다. 그 말은 즉슨 데이터를 탐색할 때 순차적으로 접근해야 한다는 것 이다. 

 

배열과 연결리스트로 표현

배열로 나타낸 메모리 비교

연결리스트로 나타낸 메모리 비교

단방향 연결리스트

B노드와 C노드 사이에 D노드를 삽입

D노드를 삭제

양방향 연결리스트: 삽입 연산

 리스트 삽입(c언어)

data=50인 새로운 노드를 리스트 ptr의 node뒤에 삽입

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

// 연결 리스트 노드 구조체 정의
typedef struct list_node {
    int data;
    struct list_node* link;
} list_node;

typedef list_node* list_pointer;

#define IS_FULL(ptr) (!(ptr)) //주어진 포인터가 NULL인 경우를 검사하여 메모리가 가득 찼는지 확인

void insert(list_pointer* ptr, list_pointer node) { //list_node 포인터를 가리키는 별칭
    list_pointer temp;
    temp = (list_pointer)malloc(sizeof(list_node));

    if (IS_FULL(temp)) {
        fprintf(stderr, "The memory is full\n");
        exit(1);
    }

    temp->data = 50;

    if (*ptr) {
        temp->link = node->link;
        node->link = temp;
    } else {
        temp->link = NULL;
        *ptr = temp;
    }
}

int main() {
    // 예제에서는 노드를 생성하고 초기화하지 않았으므로 간단한 초기화 작업을 수행
    list_pointer head = NULL;
    list_node node1, node2;

    node1.data = 10;
    node1.link = NULL;

    node2.data = 20;
    node2.link = NULL;

    head = &node1;

    // insert 함수를 호출하여 노드를 삽입
    insert(&head, &node1);

    // 현재 노드 상태를 출력
    list_pointer current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->link;
    }
    printf("NULL\n");

    return 0;
}

결과

10 -> 50 -> NULL