연결리스트 (Linked List)

Dayon·2023년 2월 5일

CS 자료구조

자료구조

목록 보기

7/10

💾 시작하기 전

메모리

Data Structure의 목표는 메모리의 효율적 사용이다.

리스트

기본적인 연산 : 삽입(insert), 삭제(remove), 검색(search) 등
리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결리스트

배열의 단점

크기가 고정되어 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다.

🧲 Linked List

연결 리스트(Linked List) 란?

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
각 노드는 데이터 필드와 다음 노드에 대해 참조를 포함하는 노드로 구성
링크 필드는 다음 노드의 주소를 저장 (첫번째 노드 주소는 따로 저장필요)
마지막 노드의 next필드는 NULL을 저장하여 연결리스트의 끝임을 표시한다.
다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능
길이의 제한이 없다 (동적 크기)
랜덤 엑세스가 불가능

단일 연결 리스트

앞쪽에 노드 추가

void push(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

특정 노드 다음에 추가

void insertAfter(struct Node* prev_node, int new_data){
    if (prev_node == NULL){
        printf("이전 노드가 NULL이 아니어야 합니다.");
        return;
    }

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;
    new_node->next = prev_node->next;

    prev_node->next = new_node;
}

끝쪽에 노드 추가

void append(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    struct Node *last = *head_ref;

    new_node->data = new_data;

    new_node->next = NULL;

    if (*head_ref == NULL){
        *head_ref = new_node;
        return;
    }

    while(last->next != NULL){
        last = last->next;
    }

    last->next = new_node;
    return;

원형 연결 리스트

head 포인터는 마지막 노드를 가르킨다
head는 마지막 노드를 , head의 link는 첫 노드를 가르켜서 리스트의 처음과 마지막에 노드를 삽입하는 연산이 편리해진다.
노드를 리스트의 첫 부분에 삽입하는 연산의 경우
1. node의 link를 head의 link로 할당
2. head의 link를 node로 할당
리스트의 뒷부분에 삽입하는 경우
1. node의 link를 head의 link로 할당
2. head의 link를 node로 할당
3. head를 node로 할당

#include <stdio.h>#include <stdlib.h>typedef int element;
typedef struct { 	// 노드 타입
	element data;
	struct ListNode *link;
} ListNode;

// 리스트의 항목 출력
void print_list(ListNode* head)
{
	ListNode* p;

	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (  p! = head );
	printf("%d->", p->data); // 마지막 노드
}
// 앞부분 삽입
ListNode* insert_first(ListNode* head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head =  node;
		node->link = head;
	}
	else {
		node->link =  head->link;
		head->link =  node;
	}
	return head;
}
// 뒷부분 삽입
istNode* insert_last(ListNode* head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head =  node ;
		node->link = head;
	}
	else {
		node->link =  head->link;
		head->link =  node;
		head =  node;
	}
	return head;	// 변경된 헤드 포인터 반환
}
// 메인
int main(void)
{
	ListNode *head = NULL;

	// list = 10->20->30->40
	head = insert_last(head, 20);
	head = insert_last(head, 30);
	head = insert_last(head, 40);
	head = insert_first(head, 10);
	print_list(head);
	return 0;
}
/* 실행결과
10->20->30->40->
*/

이중 연결 리스트

노드와 노드가 서로 연결되어있다
단순 연결 리스트와는 다르게 노드가 이전노드와 다음 노드로 구성되어 있다.
양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능하다

⚖️ Linked List vs Array List

배열의 경우 엘리먼트를 중간에 추가, 삭제를 할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리 이동이 필요하고, 따라서 배열은 추가, 삭제가 느리다.
연결 리스트의 경우 추가, 삭제가 될 엘리먼트의 이전, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다.