연결리스트

✔️ 리스트(List)

---

데이터를 순서대로 저장한 자료구조

 

리스트는 배열과 연결리스트를 이용해 구현할 수 있다.

 

 

리스트 추상데이터타입

insert(list, pos, item) // pos 위치에 요소를 추가

insert_last(list, item) // 맨 끝에 요소를 추가
insert_first(list, item) // 맨 처음에 요소를 추가
delete(list, pos) // pos 위치의 요소를 제거
clear(list) // 리스트의 모든 요소를 제거
get(list, pos) // pos 위치의 요소를 반환
size() // 리스트의 길이를 반환
is_empty(list) // 리스트가 비었는지 검사
is_full(list) // 리스트가 꽉 찼는지 검사
print_list(list) // 리스트의 모든 요소를 표시

 

리스트는 ArrayList, Node를 활용한 List가 있다.

ArrayList는 말그대로 배열을 활용한 리스트이고

Node를 활용한 리스트는 Node 구조체를 활용한 List이다.

 

1. 배열로 구현

typedef struct {
    int* data;
    int size;
    int capacity;
} ArrayList;

void init_ArrayList(ArrayList* a) {
    a->capacity = 5;
    a->size = 0;
    a->data = (int*)malloc(a->capacity * sizeof(int)); // 동적 할당
}

int is_empty(ArrayList* a) {
    return a->size == 0;
}

int is_full(ArrayList* a) {
    return (a->size == a->capacity);
}

// 해당 위치의 데이터 Get
int get(ArrayList* a, int pos) {
    if (pos < 0 || pos > a->capacity)
        //error("위치 오류");
        return;

    return a->data[pos];
}

int size(ArrayList* a) {
    return a->size;
}

void print_list(ArrayList* a) {
    for (int i = 0; i < a->size; i++) {
        printf("%d->", a->data[i]);
    }
    printf("\n");
}

// 마지막 위치의 인덱스에 삽입
void insert_last(ArrayList* a, int item) {
    if (is_full(a)) {
        a->capacity *= 2;
        a->data = (int*)realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = item;

}

void insert(ArrayList* a, int pos, int item) {
    // 가득차지 않았고 삽입 위치가 배열범위 안이라면 삽입
    if (!is_full(a) && (pos >= 0) && pos <= a->size) {
        // 지정 위치에 넣기위해 기존 위치의 데이터들을 한칸씩 뒤로 미룬다.
        for (int i = (a->size - 1); i >= pos; i--) {
            a->data[i + 1] = a->data[i];
        }
        a->data[pos] = item;
        a->size++;
    }
    // 가득찼고 pos가 범위를 안벗어난다면 용량 확장 후 삽입
    else if (is_full(a) && (pos >= 0) && pos <= a->size) {
        a->capacity *= 2;
        a->data = (int*)realloc(a->data, a->capacity * sizeof(int));

        for (int i = (a->size - 1); i >= pos; i--) {
            a->data[i + 1] = a->data[i];
        }
        a->data[pos] = item;
        a->size++;
    }
}

int delete(ArrayList* a, int pos) {

    if (pos < 0 || pos >= a->size)
        //error("위치 오류");
        return;
    int item = a->data[pos];
    // 특정 위치의 데이터를 삭제하기 위해 미리 데이터를 꺼내놓고,
    // 그 위치를 채우기위해 뒤에서 앞으로 땡긴다.
    for (int i = pos; i < (a->size - 1); i++) {
        a->data[i] = a->data[i + 1];
    }
    a->size--;
    return item;
}

void clear(ArrayList* a) {
    free(a->data);
    init_ArrayList(a);
}

---

 

2. 리스트로 구현

리스트의 항목들을 노드(node)에 분산하여 저장

• 노드의 구성
  • 데이터 필드
    • 리스트의 원소, 즉 데이터 값을 저장하는 곳
  • 링크 필드
    • 다른 노드의 주소값을 저장하는 장소(포인터)

 

장점

• 삽입, 삭제가 용이
• 연속된 메모리 공간 필요 x
• 크기 제한 x

단점

• 구현이 어려움
• 오류가 발생하기 쉬움

 

 

연결 리스트의 종류

• 단순 연결 리스트 
• 원형 연결 리스트 (마지막 Null pointer가 없음)
• 이중 연결 리스트

 

노드 : [데이터 | 링크]  

링크또한 포인터이기 때문에 노드의 링크는 다음 노드라고 볼 수 있다.

head -> Node1 -> Node2 -> NULL

ListNode* p = head->link ;

p 는 현재 Node1을 가리키고 있다. 

 

 

head->link 의미

• 노드 node1
• head가 가리키는 link값

이게 중요하다. 이 다음에 포스팅할 이중 연결리스트에서 중간 삽입이나 중간 삭제할 때 매우 헷갈린다. 

이해하고 넘어가자.

 

 

 

 

typedef struct {
    int data;
    struct _ListNode* link;

} ListNode;

// 앞 삽입
ListNode* insert_first(ListNode* head, int value) {
    ListNode* p = (ListNode*)malloc(sizeof(ListNode)); // 1
    p->data = value;  // 2
    p->link = head;  // 3
    head = p; // 4
    return head;
}

// preNode -> afterNode
// 이 사이에 노드를 삽입
// 새로운 노드를 만들고 afterNode쪽으로 연결
// preNode의 link를 새로운 노드에 연결

// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, int value) {
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p->data = value;
    p->link = pre->link;
    pre->link = p;
    return head;
}
// 처음 노드 삭제
ListNode* delete_first(ListNode* head) {
    ListNode* removed;
    if (head == NULL) return NULL;
    removed = head;
    head = head->link;          // 처음 노드는 삭제할 것이니 head의 다음 노드를 head 로 지정
    free(removed);
    return head;
}
// 노드 pre의 다음 노드를 삭제
ListNode* delete(ListNode* head, ListNode* pre) {
    ListNode* removed;
    removed = pre->link; // pre 다음 노드를 삭제하므로 삭제노드에 pre 다음 노드를 담는다.
    pre->link = removed->link; // pre노드의 link는 삭제할 노드의 다음 노드이므로 연결
    free(removed);
    return head;
}

// 요소 찾기
ListNode* search_list(ListNode* head, int x) {
    ListNode* p = head;
    while (p != NULL) {
        if (p->data == x) return p;
        p = p->link;
    }
    return NULL;  // 탐색 실패
}

// 두 연결리스트를 연결
ListNode* concat_list(ListNode* head1, ListNode* head2) {
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    else {
        ListNode* p;
        p = head1;
        while (p->link != NULL) {
            p = p->link;
        }
        p->link = head2;
        return head1;

    }
}


// 역순환으로 head->Node -> NULL 을 NULL<- Node <- head 이렇게 변경
ListNode* reverse(ListNode* head) {
    ListNode* p, * q, * r;

    p = head;
    q = NULL;
    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;

    }

    return q;

}

// 노드 메모리 해제 및 NULL 반환
ListNode* clear(ListNode* head) {
    ListNode* p = head;
    ListNode* pre;

    while (p != NULL) {
        pre = p;
        p = p->link;
        free(pre);
    }

    return NULL;

}

void print_list(ListNode* head) {
    for (ListNode* p = head; p != NULL; p = p->link) {
        if (p == NULL) {
            printf("->NULL");
            break;
        }
        printf("%d->", p->data);
    }
    printf("NULL\n");
}

 

 

// 사용

int main(void) {

    ListNode* head = NULL;
    
    for (int i = 0; i < 5; i++) {
        head = insert_first(head, i);
        print_list(head);
    }
    for (int i = 0; i < 5; i++) {
        head = delete_first(head);
        print_list(head);
    }

    head = insert_first(head, 1);
    head = clear(head);
    print_list(head);

    head = insert_first(head, 1);
    print_list(head);


    return 0;


}

 

 

실행결과

 

 

 

 

 

 

 

 

리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은? 

배열이다. 배열은 요소들이 연속된 메모리에 있기때문에 여기저기 퍼져있는 노드들을 구성한 리스트보다 더 빠르게 찾을 수 있다.

 

🔖 참고자료

---

• C로 쉽게 풀어쓴 자료구조 - 생능출판사

 

• 본 그림들은 참고자료를 바탕으로 작성자가 직접 그린 그림입니다.