[C][강의정리] 연결 리스트 개념과 기본 동작들 (1)

https://youtu.be/eTwYE-ercNM

 

리스트

기본적인 연산: 삽입, 삭제, 검색 등

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

 

배열의 단점

크기가 고정 - reallocation이 필요

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

배열의 장점

랜덤 엑세스가 가능

 

연결리스트

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

길이의 제한이 없음

하지만 랜덤 엑세스가 불가능

 

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

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

첫 번째 노드의 주소는 따로 저장해야

 

연결리스트의 첫 번째 노드의 주소는 따로 저장해야하며 절대 잊어버려서는 안됨.

마지막 노드의 넥스트 필드에는 널값을 저장하여 연결리스트의 끝임을 표시.

 

연결 리스트에서 하나의 노드를 표현하기 위한 구조체이다.

각 노드에 저장될 데이터는 하나의 문자열이라고 가정하자.

struct node
{
	char *data;
    // 다음 노드의 주소를 저장할 필드이다.
    // 이렇게 자신과 동일한 구조체에 대한 포인터를 멤버로 가진다는 의미에서 "자기참조형 구조체"라고 부르기도 함.
    struct node *next;
}

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