연결리스트 (Linked List)

Dayon·2023년 2월 5일
0

자료구조

목록 보기
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)만 변경하면 되기 때문에 속도가 빠르다.


🔗 참조한 사이트

https://opentutorials.org/module/1335/8940

https://gyoogle.dev/blog/computer-science/data-structure/Linked List.html

https://opentutorials.org/module/1335/8821

https://yoongrammer.tistory.com/43

https://yjg-lab.tistory.com/120

profile
success is within reach, allow yourself time

0개의 댓글